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]