Igor Shinkar - RankMe

82 papers A* 8A 8B 1Journal 57Unranked 8

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