Igor Shinkar

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 55

Top Topics

Query Complexity

Worst Case Analysis

Boolean Functions

Top Venues

Electron. Colloquium Comput. Complex.

Comb. Probab. Comput.

Publications

Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
On the Power of Interactive Proofs for Learning. STOC (2024)
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
On the Power of Interactive Proofs for Learning. CoRR (2024)
Ashish Gola, Igor Shinkar, Harsimran Singh
Matrix Multiplication Reductions. CoRR (2024)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. SODA (2024)
Lucas Boczkowski, Igor Shinkar
On mappings on the hypercube with small average stretch. Comb. Probab. Comput. 32 (2) (2023)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. SOSA (2023)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-case to average-case reductions via additive combinatorics. STOC (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-Case to Average-Case Reductions via Additive Combinatorics. Electron. Colloquium Comput. Complex. 29 (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. Electron. Colloquium Comput. Complex. (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
Worst-Case to Average-Case Reductions via Additive Combinatorics. CoRR (2022)
Fatemeh Hasiri, Igor Shinkar
Meyniel Extremal Families of Abelian Cayley Graphs. Graphs Comb. 38 (3) (2022)
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. CoRR (2022)
Alessandro Chiesa, Tom Gur, Igor Shinkar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SIAM J. Comput. 51 (6) (2022)
Vahid R. Asadi, Igor Shinkar
Relaxed Locally Correctable Codes with Improved Parameters. ICALP (2021)
Alexander Golovnev, Tom Gur, Igor Shinkar
Derandomization of Cell Sampling. CoRR (2021)
Vahid R. Asadi, Igor Shinkar
Relaxed Locally Correctable Codes with Improved Parameters. Electron. Colloquium Comput. Complex. 27 (2020)
Alessandro Chiesa, Tom Gur, Igor Shinkar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SODA (2020)
Tom Gur, Igor Shinkar
An Entropy Lower Bound for Non-Malleable Extractors. IEEE Trans. Inf. Theory 66 (5) (2020)
Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality. CoRR (2020)
Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality. Electron. Colloquium Comput. Complex. 27 (2020)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
Testing Linearity against Non-signaling Strategies. ACM Trans. Comput. Theory 12 (3) (2020)
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku
Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. 34 (1) (2020)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
On Axis-Parallel Tests for Tensor Product Codes. Theory Comput. 16 (2020)
Alessandro Chiesa, Tom Gur, Igor Shinkar
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
On Local Testability in the Non-Signaling Setting. ITCS (2020)
Vahid R. Asadi, Igor Shinkar
Relaxed Locally Correctable Codes with Improved Parameters. CoRR (2020)
Lucas Boczkowski, Igor Shinkar
On Mappings on the Hypercube with Small Average Stretch. CoRR (2019)
Indranil Banerjee, Dana Richards, Igor Shinkar
Sorting Networks on Restricted Topologies. SOFSEM (2019)
Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar
String Matching: Communication, Circuits, and Learning. APPROX-RANDOM (2019)
Huck Bennett, Daniel Reichman, Igor Shinkar
On percolation and -hardness. Random Struct. Algorithms 54 (2) (2019)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. ITCS (2019)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
On Local Testability in the Non-Signaling Setting. Electron. Colloquium Comput. Complex. 26 (2019)
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku
Multitasking Capacity: Hardness Results and Improved Constructions. CoRR (2018)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
Testing Linearity against Non-Signaling Strategies. Computational Complexity Conference (2018)
Shravas Rao, Igor Shinkar
On Lipschitz Bijections Between Boolean Functions. Comb. Probab. Comput. 27 (3) (2018)
Tom Gur, Igor Shinkar
An Entropy Lower Bound for Non-Malleable Extractors. CoRR (2018)
Tom Gur, Igor Shinkar
An Entropy Lower Bound for Non-Malleable Extractors. Electron. Colloquium Comput. Complex. 25 (2018)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
Testing Linearity against Non-Signaling Strategies. Electron. Colloquium Comput. Complex. 25 (2018)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
Probabilistic Checking against Non-Signaling Strategies from Linearity Testing. Electron. Colloquium Comput. Complex. 25 (2018)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
On Axis-Parallel Tests for Tensor Product Codes. Electron. Colloquium Comput. Complex. 24 (2017)
Alexander Golovnev, Daniel Reichman, Igor Shinkar
Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem. CoRR (2017)
Alessandro Chiesa, Peter Manohar, Igor Shinkar
On Axis-Parallel Tests for Tensor Product Codes. APPROX-RANDOM (2017)
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
Direct Sum Testing. SIAM J. Comput. 46 (4) (2017)
Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan D. Cohen, Tom Griffiths, Biswadip Dey, Kayhan Özcimder
A graph-theoretic approach to multitasking. NIPS (2017)
Oded Goldreich, Igor Shinkar
Two-sided error proximity oblivious testing. Random Struct. Algorithms 48 (2) (2016)
Subhash Khot, Igor Shinkar
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness. CoRR (2016)
Subhash Khot, Igor Shinkar
On Hardness of Approximating the Parameterized Clique Problem. ITCS (2016)
Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Özcimder, Daniel Reichman, Igor Shinkar, Tal Wagner
A Graph-Theoretic Approach to Multitasking. CoRR (2016)
Subhash Khot, Igor Shinkar
An ~O(n) Queries Adaptive Tester for Unateness. APPROX-RANDOM (2016)
Omer Angel, Igor Shinkar
A Tight Upper Bound on Acquaintance Time of Graphs. Graphs Comb. 32 (5) (2016)
Igor Shinkar
On Coloring Random Subgraphs of a Fixed Graph. CoRR (2016)
Huck Bennett, Daniel Reichman, Igor Shinkar
On Percolation and NP-Hardness. ICALP (2016)
Gil Cohen, Igor Shinkar
The Complexity of DNF of Parities. ITCS (2016)
Subhash Khot, Igor Shinkar
An Õ(n) Queries Adaptive Tester for Unateness. Electron. Colloquium Comput. Complex. 23 (2016)
Indranil Banerjee, Dana Richards, Igor Shinkar
Sorting Networks On Restricted Topologies. CoRR (2016)
Daniel Reichman, Igor Shinkar
On Percolation and NP-Hardness. Electron. Colloquium Comput. Complex. 22 (2015)
Shravas Rao, Igor Shinkar
On Lipschitz Bijections between Boolean Functions. CoRR (2015)
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
Direct Sum Testing. ITCS (2015)
Daniel Reichman, Igor Shinkar
On Percolation and NP-Hardness. CoRR (2015)
Gil Cohen, Igor Shinkar
Zero-Fixing Extractors for Sub-Logarithmic Entropy. ICALP (1) (2015)
Subhash Khot, Igor Shinkar
On Hardness of Approximating the Parameterized Clique Problem. Electron. Colloquium Comput. Complex. 22 (2015)
Gil Cohen, Igor Shinkar
The Complexity of DNF of Parities. Electron. Colloquium Comput. Complex. 21 (2014)
Tal Orenshtein, Igor Shinkar
Greedy Random Walk. Comb. Probab. Comput. 23 (2) (2014)
Avraham Ben-Aroya, Igor Shinkar
A Note on Subspace Evasive Sets. Chic. J. Theor. Comput. Sci. 2014 (2014)
Itai Benjamini, Igor Shinkar, Gilad Tsur
Acquaintance Time of a Graph. SIAM J. Discret. Math. 28 (2) (2014)
Itai Benjamini, Gil Cohen, Igor Shinkar
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. FOCS (2014)
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
Direct Sum Testing. Electron. Colloquium Comput. Complex. 21 (2014)
Gil Cohen, Igor Shinkar
Zero-Fixing Extractors for Sub-Logarithmic Entropy. Electron. Colloquium Comput. Complex. 21 (2014)
Itai Benjamini, Igor Shinkar, Gilad Tsur
Acquaintance Time of a Graph CoRR (2013)
Itai Benjamini, Gil Cohen, Igor Shinkar
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. Electron. Colloquium Comput. Complex. 20 (2013)
Irit Dinur, Igor Shinkar
On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors. Electron. Colloquium Comput. Complex. 20 (2013)
Itai Benjamini, Gil Cohen, Igor Shinkar
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. CoRR (2013)
Omer Angel, Igor Shinkar
A Tight Upper Bound on Acquaintance Time of Graphs. CoRR (2013)
Avraham Ben-Aroya, Igor Shinkar
A Note on Subspace Evasive Sets. Electron. Colloquium Comput. Complex. 19 (2012)
Oded Goldreich, Igor Shinkar
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). APPROX-RANDOM (2012)
Tal Orenshtein, Igor Shinkar
Greedy random walk CoRR (2011)
Irit Dinur, Igor Shinkar
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. APPROX-RANDOM (2010)