Publications

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 Yu
  SIAM Journal on Discrete Mathematics, accepted, 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.
  


2019


• An Entropy Lower Bound for Non-Malleable Extractors
  Tom Gur, Igor Shinkar
  Accepted to IEEE Transactions on Information Theory, 2019.
  Available at ECCC TR18-008, 2018. [ECCC]


• Meyniel Extremal Families of Abelian Cayley Graphs
  Fatemeh Hasiri, Igor Shinkar
  Available at arXiv:1909.03027, 2019. [arXiv]


• On Mappings on the Hypercube with Small Average Stretch
  Lucas Boczkowski, Igor Shinkar
  Available at arXiv:1905.11350, 2019. [arXiv]


• Non-Uniform and Learning Algorithms for String Matching Problems
  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, Tom 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]