Publications
2024
-
Matrix Multiplication Reductions
Ashish Gola, Igor Shinkar, Harsimran Singh
RANDOM 2024
Available at arXiv:2404.08085, 2024 [arXiv]
-
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
STOC 2024
Available at arXiv:2404.08158, 2024 [arXiv]
-
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian
QIP 2023
SODA 2024
Available at ECCC TR22-177, 2022 [ECCC]
2023
-
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
SOSA 2023
Available at arXiv:2108.05970, 2018 [arXiv]
-
On Mappings on the Hypercube with Small Average Stretch
Lucas Boczkowski, Igor Shinkar
Combinatorics, Probability and Computing, (32) 2, 334-348, 2023
Available at arXiv:1905.11350, 2019 [arXiv]
2022
-
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar
STOC 2022
Available at ECCC TR22-020, 2022 [ECCC]
-
Meyniel Extremal Families of Abelian Cayley Graphs
Fatemeh Hasiri, Igor Shinkar
Graphs and Combinatorics, 38(3), 1435--5914, 2022
Available at arXiv:1909.03027, 2019 [arXiv]
2021
-
Relaxed Locally Correctable Codes with Improved Parameters
Vahid R. Asadi, Igor Shinkar
ICALP 2021
Available at ECCC TR20-142, 2020 [ECCC]
2020
-
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar
Available at ECCC TR20-144, 2020 [ECCC]
-
Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Yu
SIAM Journal on Discrete Mathematics, 34(1), 885–903, 2020
Available at arXiv:1809.02835, 2018 [arXiv]
-
On Local Testability in the Non-Signaling Setting
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2020
Available at ECCC TR19-070, 2019 [ECCC]
-
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Alessandro Chiesa, Tom Gur, Igor Shinkar
SODA 2020
SIAM Journal on Computing, 51(6), 1839-1865, 2022
Available at ECCC TR19-113, 2020 [ECCC]
2019
-
An Entropy Lower Bound for Non-Malleable Extractors
Tom Gur, Igor Shinkar
IEEE Transactions on Information Theory, 66(5), 2904-2911, 2019
Available at ECCC TR18-008, 2018 [ECCC]
-
String Matching: Communication, Circuits, and Learning
Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar
RANDOM 2019
Available at arXiv:1709.02034, 2017 [arXiv]
-
Sorting Networks On Restricted Topologies
Indranil Banerjee, Dana Richards, Igor Shinkar
SOFSEM 2019
Available at arXiv:1612.06473, 2016 [arXiv]
-
Probabilistic Checking against Non-Signaling Strategies from Linearity Testing
Alessandro Chiesa, Peter Manohar, Igor Shinkar
ITCS 2019
Available at ECCC TR18-1237, 2018 [ECCC]
2018
-
Testing Linearity against Non-Signaling Strategies
Alessandro Chiesa, Peter Manohar, Igor Shinkar
CCC 2018
ACM Transactions on Computation Theory, 12(3), Article 16, 2020
Available at ECCC TR18-067, 2018 [ECCC]
2017
-
A Graph-Theoretic Approach to Multitasking
Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan D. Cohen, Thomas L. Griffths, Biswadip Dey, Kayhan Özcimder
NIPS 2017
Available at arXiv:1611.02400, 2017 [arXiv]
-
On Lipschitz Bijections between Boolean Functions
Shravas Rao, Igor Shinkar
Combinatorics, Probability and Computing, 27(3), 411-426, 2018
Available at arXiv:1501.03016, 2015 [arXiv]
-
On Axis-Parallel Tests for Tensor Product Codes
Alessandro Chiesa, Peter Manohar, Igor Shinkar
RANDOM 2017
Available at ECCC TR17-110, 2017 [ECCC]
2016
-
On Coloring Random Subgraphs of a Fixed Graph
Igor Shinkar
Available at arXiv:1612.04319, 2016 [arXiv]
-
An Õ(n) Queries Adaptive Tester for Unateness
Subhash Khot, Igor Shinkar
RANDOM 2016
Available at ECCC TR16-126, 2016.[ECCC]
-
On Percolation and NP-hardness
Huck Bennett, Daniel Reichman, Igor Shinkar
ICALP 2016
Random Structures & Algorithms, 2018
Available at ECCC TR15-132, 2015 [ECCC]
-
A Counterexample to Monotonicity of Relative Mass in Random Walks
Oded Regev, Igor Shinkar
Electronic Communications in Probability, Volume 21 (2016), paper no. 8
Available at arXiv:1506.08631, 2015 [arXiv]
-
On Hardness of Approximating the Parameterized Clique Problem
Subhash Khot, Igor Shinkar
ITCS 2016
Available at ECCC TR15-013, 2015 [ECCC]
-
The Complexity of DNF of Parities
Gil Cohen, Igor Shinkar
ITCS 2016
Available at ECCC TR14-099, 2014 [ECCC]
-
A Tight Upper Bound on Acquaintance Time of Graphs
Omer Angel, Igor Shinkar
Graphs and Combinatorics, 32(5), 1667--1673, 2016
Available at arXiv:1307.6029, 2013 [arXiv]
-
Excited Random Walk with Periodic Cookies
Gady Kozma, Tal Orenshtein, Igor Shinkar
Annales de l'Institut Henri Poincare, 52(3), 1023-1049, 2016
Available at arXiv:1311.7439, 2013 [arXiv]
2015
-
Zero-Fixing Extractors for Sub-Logarithmic Entropy
Gil Cohen, Igor Shinkar
ICALP 2015
Available at ECCC TR14-160, 2014 [ECCC]
-
Direct Sum Testing
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar
ITCS 2015
SIAM Journal on Computing, 46(4), 1336-1369, 2017
Available at ECCC TR14-002, 2014 [ECCC]
2014
-
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball
Itai Benjamini, Gil Cohen, Igor Shinkar
FOCS 2014
Israel Journal of Mathematics, 212(2), 677-703, 2016
Available at ECCC TR13-138, 2013 [ECCC]
-
Acquaintance Time of a Graph
Itai Benjamini, Igor Shinkar, Gilad Tsur
SIAM Journal on Discrete Mathematics, 28(2), 767-785, 2014
Available at arXiv:1302.2787, 2013 [arXiv]
-
A Note on Subspace Evasive Sets
Avraham Ben-Aroya, Igor Shinkar
Chicago Journal of Theoretical Computer Science, 2014, Article 9, 1-11, 2014
Available at ECCC TR12-095, 2012 [ECCC]
-
Greedy Random Walk
Tal Orenshtein, Igor Shinkar
Combinatorics, Probability and Computing, 23(2), 269-289, 2014
Available at arXiv:1101.5711, 2011 [arXiv]
2012
-
Two-Sided Error Proximity Oblivious Testing
Oded Goldreich, Igor Shinkar
RANDOM 2012
Random Structures & Algorithms, 48(2), 341-383, 2016
Full version is available at ECCC TR12-021, 2012 [ECCC]
2010
-
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors
Irit Dinur, Igor Shinkar
APPROX 2010
Available at ECCC TR13-148, 2013 [ECCC]
PhD thesis: Topics on local-to-global phenomena in large combinatorial objects
Advisor: Prof. Irit Dinur
Weizmann Institute of Science, Rehovot, Israel 2014
[pdf]
Master's thesis: Intersecting Families, Independent Sets and Coloring of Certain Graph Products
Advisor: Prof. Irit Dinur
Weizmann Institute of Science, Rehovot, Israel 2009
[pdf]