Igor Shinkar

According to our database, Igor Shinkar authored at least 41 papers between 2012 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Erratum: Multitasking Capacity: Hardness Results and Improved Constructions.

Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner

SIAM J. Discret. Math., 2024

On the Power of Interactive Proofs for Learning.

Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Matrix Multiplication Reductions.

Ashish Gola, Igor Shinkar, Harsimran Singh

Proceedings of the Approximation, 2024

2023

On mappings on the hypercube with small average stretch.

Lucas Boczkowski, Igor Shinkar

Comb. Probab. Comput., March, 2023

Derandomization of Cell Sampling.

Alexander Golovnev, Tom Gur, Igor Shinkar

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

2022

Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.

Alessandro Chiesa, Tom Gur, Igor Shinkar

SIAM J. Comput., 2022

Meyniel Extremal Families of Abelian Cayley Graphs.

Fatemeh Hasiri, Igor Shinkar

Graphs Comb., 2022

Quantum Worst-Case to Average-Case Reductions for All Linear Problems.

Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian

Electron. Colloquium Comput. Complex., 2022

Worst-Case to Average-Case Reductions via Additive Combinatorics.

Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2022

2020

Multitasking Capacity: Hardness Results and Improved Constructions.

Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku

SIAM J. Discret. Math., 2020

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality.

Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar

Electron. Colloquium Comput. Complex., 2020

Relaxed Locally Correctable Codes with Improved Parameters.

Vahid R. Asadi, Igor Shinkar

Electron. Colloquium Comput. Complex., 2020

2019

On percolation and -hardness.

Huck Bennett, Daniel Reichman, Igor Shinkar

Random Struct. Algorithms, 2019

On Local Testability in the Non-Signaling Setting.

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Electron. Colloquium Comput. Complex., 2019

Sorting Networks on Restricted Topologies.

Indranil Banerjee, Dana Richards, Igor Shinkar

Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019

String Matching: Communication, Circuits, and Learning.

Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar

Proceedings of the Approximation, 2019

2018

An Entropy Lower Bound for Non-Malleable Extractors.

Tom Gur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2018

Probabilistic Checking against Non-Signaling Strategies from Linearity Testing.

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Electron. Colloquium Comput. Complex., 2018

Testing Linearity against Non-Signaling Strategies.

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Electron. Colloquium Comput. Complex., 2018

On Lipschitz Bijections Between Boolean Functions.

Shravas Rao, Igor Shinkar

Comb. Probab. Comput., 2018

2017

Direct Sum Testing.

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

SIAM J. Comput., 2017

On Axis-Parallel Tests for Tensor Product Codes.

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Electron. Colloquium Comput. Complex., 2017

Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem.

Alexander Golovnev, Daniel Reichman, Igor Shinkar

CoRR, 2017

A graph-theoretic approach to multitasking.

Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan D. Cohen, Tom Griffiths, Biswadip Dey, Kayhan Özcimder

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

2016

Two-sided error proximity oblivious testing.

Oded Goldreich, Igor Shinkar

Random Struct. Algorithms, 2016

A Tight Upper Bound on Acquaintance Time of Graphs.

Omer Angel, Igor Shinkar

Graphs Comb., 2016

An Õ(n) Queries Adaptive Tester for Unateness.

Subhash Khot, Igor Shinkar

Electron. Colloquium Comput. Complex., 2016

On Coloring Random Subgraphs of a Fixed Graph.

Igor Shinkar

CoRR, 2016

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.

Subhash Khot, Igor Shinkar

CoRR, 2016

A Graph-Theoretic Approach to Multitasking.

Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Özcimder, Daniel Reichman, Igor Shinkar, Tal Wagner

CoRR, 2016

On Percolation and NP-Hardness.

Huck Bennett, Daniel Reichman, Igor Shinkar

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

On Percolation and NP-Hardness.

Daniel Reichman, Igor Shinkar

Electron. Colloquium Comput. Complex., 2015

On Hardness of Approximating the Parameterized Clique Problem.

Subhash Khot, Igor Shinkar

Electron. Colloquium Comput. Complex., 2015

2014

Acquaintance Time of a Graph.

Itai Benjamini, Igor Shinkar, Gilad Tsur

SIAM J. Discret. Math., 2014

Zero-Fixing Extractors for Sub-Logarithmic Entropy.

Gil Cohen, Igor Shinkar

Electron. Colloquium Comput. Complex., 2014

The Complexity of DNF of Parities.

Gil Cohen, Igor Shinkar

Electron. Colloquium Comput. Complex., 2014

Greedy Random Walk.

Tal Orenshtein, Igor Shinkar

Comb. Probab. Comput., 2014

A Note on Subspace Evasive Sets.

Avraham Ben-Aroya, Igor Shinkar

Chic. J. Theor. Comput. Sci., 2014

2013

On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors.

Irit Dinur, Igor Shinkar

Electron. Colloquium Comput. Complex., 2013

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball.

Itai Benjamini, Gil Cohen, Igor Shinkar

Electron. Colloquium Comput. Complex., 2013

2012

Two-Sided Error Proximity Oblivious Testing - (Extended Abstract).

Oded Goldreich, Igor Shinkar

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012