default search action
Igor Shinkar
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j16]Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner:
Erratum: Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. 38(2): 2001-2003 (2024) - [c23]Ashish Gola, Igor Shinkar, Harsimran Singh:
Matrix Multiplication Reductions. APPROX/RANDOM 2024: 34:1-34:15 - [c22]Vahid R. Asadi
, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. SODA 2024: 2535-2567 - [c21]Tom Gur
On the Power of Interactive Proofs for Learning. STOC 2024: 1063-1070 - [e1]Bojan Mohar, Igor Shinkar, Ryan O'Donnell:
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024. ACM 2024 [contents] - [i40]Ashish Gola, Igor Shinkar, Harsimran Singh:
Matrix Multiplication Reductions. CoRR abs/2404.08085 (2024) - [i39]Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar:
On the Power of Interactive Proofs for Learning. CoRR abs/2404.08158 (2024) - 2023
- [j15]Lucas Boczkowski, Igor Shinkar:
On mappings on the hypercube with small average stretch. Comb. Probab. Comput. 32(2): 334-348 (2023) - [c20]Alexander Golovnev, Tom Gur
Derandomization of Cell Sampling. SOSA 2023: 278-284 - 2022
- [j14]Fatemeh Hasiri
Meyniel Extremal Families of Abelian Cayley Graphs. Graphs Comb. 38(3): 61 (2022) - [j13]Alessandro Chiesa, Tom Gur
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SIAM J. Comput. 51(6): 1839-1865 (2022) - [c19]Vahid R. Asadi
Worst-case to average-case reductions via additive combinatorics. STOC 2022: 1566-1574 - [i38]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar:
Worst-Case to Average-Case Reductions via Additive Combinatorics. CoRR abs/2202.08996 (2022) - [i37]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. CoRR abs/2212.03348 (2022) - [i36]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar:
Worst-Case to Average-Case Reductions via Additive Combinatorics. Electron. Colloquium Comput. Complex. TR22 (2022) - [i35]Vahid R. Asadi, Alexander Golovnev, Tom Gur, Igor Shinkar, Sathyawageeswar Subramanian:
Quantum Worst-Case to Average-Case Reductions for All Linear Problems. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [c18]Vahid R. Asadi
Relaxed Locally Correctable Codes with Improved Parameters. ICALP 2021: 18:1-18:12 - [i34]Alexander Golovnev, Tom Gur, Igor Shinkar:
Derandomization of Cell Sampling. CoRR abs/2108.05970 (2021) - 2020
- [j12]Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths
Multitasking Capacity: Hardness Results and Improved Constructions. SIAM J. Discret. Math. 34(1): 885-903 (2020) - [j11]Tom Gur
An Entropy Lower Bound for Non-Malleable Extractors. IEEE Trans. Inf. Theory 66(5): 2904-2911 (2020) - [j10]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. Theory Comput. 16: 1-34 (2020) - [j9]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Testing Linearity against Non-signaling Strategies. ACM Trans. Comput. Theory 12(3): 16:1-16:51 (2020) - [c17]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Local Testability in the Non-Signaling Setting. ITCS 2020: 26:1-26:37 - [c16]Alessandro Chiesa, Tom Gur
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. SODA 2020: 1395-1411 - [i33]Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar:
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality. CoRR abs/2009.04892 (2020) - [i32]Vahid R. Asadi, Igor Shinkar:
Relaxed Locally Correctable Codes with Improved Parameters. CoRR abs/2009.07311 (2020) - [i31]Vahid R. Asadi, Igor Shinkar:
Relaxed Locally Correctable Codes with Improved Parameters. Electron. Colloquium Comput. Complex. TR20 (2020) - [i30]Alessandro Chiesa, Tom Gur, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. Electron. Colloquium Comput. Complex. TR20 (2020) - [i29]Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar:
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j8]Huck Bennett, Daniel Reichman, Igor Shinkar:
On percolation and -hardness. Random Struct. Algorithms 54(2): 228-257 (2019) - [c15]Alexander Golovnev, Mika Göös, Daniel Reichman, Igor Shinkar:
String Matching: Communication, Circuits, and Learning. APPROX-RANDOM 2019: 56:1-56:20 - [c14]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. ITCS 2019: 25:1-25:17 - [c13]Indranil Banerjee
Sorting Networks on Restricted Topologies. SOFSEM 2019: 54-66 - [i28]Lucas Boczkowski, Igor Shinkar:
On Mappings on the Hypercube with Small Average Stretch. CoRR abs/1905.11350 (2019) - [i27]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Local Testability in the Non-Signaling Setting. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j7]Shravas Rao, Igor Shinkar:
On Lipschitz Bijections Between Boolean Functions. Comb. Probab. Comput. 27(3): 411-426 (2018) - [c12]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Testing Linearity against Non-Signaling Strategies. CCC 2018: 17:1-17:37 - [i26]Tom Gur, Igor Shinkar:
An Entropy Lower Bound for Non-Malleable Extractors. CoRR abs/1801.03200 (2018) - [i25]Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, Alexander Y. Ku:
Multitasking Capacity: Hardness Results and Improved Constructions. CoRR abs/1809.02835 (2018) - [i24]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Testing Linearity against Non-Signaling Strategies. Electron. Colloquium Comput. Complex. TR18 (2018) - [i23]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
Probabilistic Checking against Non-Signaling Strategies from Linearity Testing. Electron. Colloquium Comput. Complex. TR18 (2018) - [i22]Tom Gur, Igor Shinkar:
An Entropy Lower Bound for Non-Malleable Extractors. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j6]Roee David, Irit Dinur
Direct Sum Testing. SIAM J. Comput. 46(4): 1336-1369 (2017) - [c11]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. APPROX-RANDOM 2017: 39:1-39:22 - [c10]Noga Alon, Daniel Reichman, Igor Shinkar, Tal Wagner, Sebastian Musslick, Jonathan D. Cohen, Tom Griffiths, Biswadip Dey, Kayhan Özcimder:
A graph-theoretic approach to multitasking. NIPS 2017: 2100-2109 - [i21]Alexander Golovnev, Daniel Reichman, Igor Shinkar:
Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem. CoRR abs/1709.02034 (2017) - [i20]Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j5]Omer Angel, Igor Shinkar:
A Tight Upper Bound on Acquaintance Time of Graphs. Graphs Comb. 32(5): 1667-1673 (2016) - [j4]Oded Goldreich
Two-sided error proximity oblivious testing. Random Struct. Algorithms 48(2): 341-383 (2016) - [c9]Subhash Khot, Igor Shinkar:
An ~O(n) Queries Adaptive Tester for Unateness. APPROX-RANDOM 2016: 37:1-37:7 - [c8]Huck Bennett, Daniel Reichman, Igor Shinkar:
On Percolation and NP-Hardness. ICALP 2016: 80:1-80:14 - [c7]Subhash Khot, Igor Shinkar:
On Hardness of Approximating the Parameterized Clique Problem. ITCS 2016: 37-45 - [c6]Gil Cohen, Igor Shinkar:
The Complexity of DNF of Parities. ITCS 2016: 47-58 - [i19]Subhash Khot, Igor Shinkar:
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness. CoRR abs/1608.02451 (2016) - [i18]Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Özcimder, Daniel Reichman, Igor Shinkar, Tal Wagner:
A Graph-Theoretic Approach to Multitasking. CoRR abs/1611.02400 (2016) - [i17]Igor Shinkar:
On Coloring Random Subgraphs of a Fixed Graph. CoRR abs/1612.04319 (2016) - [i16]Indranil Banerjee, Dana Richards, Igor Shinkar:
Sorting Networks On Restricted Topologies. CoRR abs/1612.06473 (2016) - [i15]Subhash Khot, Igor Shinkar:
An Õ(n) Queries Adaptive Tester for Unateness. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [c5]Gil Cohen, Igor Shinkar:
Zero-Fixing Extractors for Sub-Logarithmic Entropy. ICALP (1) 2015: 343-354 - [c4]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. ITCS 2015: 327-336 - [i14]Shravas Rao, Igor Shinkar:
On Lipschitz Bijections between Boolean Functions. CoRR abs/1501.03016 (2015) - [i13]Daniel Reichman, Igor Shinkar:
On Percolation and NP-Hardness. CoRR abs/1508.02071 (2015) - [i12]Subhash Khot, Igor Shinkar:
On Hardness of Approximating the Parameterized Clique Problem. Electron. Colloquium Comput. Complex. TR15 (2015) - [i11]Daniel Reichman, Igor Shinkar:
On Percolation and NP-Hardness. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j3]Avraham Ben-Aroya, Igor Shinkar:
A Note on Subspace Evasive Sets. Chic. J. Theor. Comput. Sci. 2014 (2014) - [j2]Tal Orenshtein
Greedy Random Walk. Comb. Probab. Comput. 23(2): 269-289 (2014) - [j1]Itai Benjamini, Igor Shinkar, Gilad Tsur:
Acquaintance Time of a Graph. SIAM J. Discret. Math. 28(2): 767-785 (2014) - [c3]Itai Benjamini, Gil Cohen, Igor Shinkar:
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. FOCS 2014: 81-89 - [i10]Gil Cohen, Igor Shinkar:
The Complexity of DNF of Parities. Electron. Colloquium Comput. Complex. TR14 (2014) - [i9]Gil Cohen, Igor Shinkar:
Zero-Fixing Extractors for Sub-Logarithmic Entropy. Electron. Colloquium Comput. Complex. TR14 (2014) - [i8]Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i7]Itai Benjamini, Igor Shinkar, Gilad Tsur:
Acquaintance Time of a Graph. CoRR abs/1302.2787 (2013) - [i6]Omer Angel, Igor Shinkar:
A Tight Upper Bound on Acquaintance Time of Graphs. CoRR abs/1307.6029 (2013) - [i5]Itai Benjamini, Gil Cohen, Igor Shinkar:
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. CoRR abs/1310.2017 (2013) - [i4]Itai Benjamini, Gil Cohen, Igor Shinkar:
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. Electron. Colloquium Comput. Complex. TR13 (2013) - [i3]Irit Dinur, Igor Shinkar:
On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c2]Oded Goldreich
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract). APPROX-RANDOM 2012: 565-578 - [i2]Avraham Ben-Aroya, Igor Shinkar:
A Note on Subspace Evasive Sets. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [i1]Tal Orenshtein, Igor Shinkar:
Greedy random walk. CoRR abs/1101.5711 (2011) - 2010
- [c1]Irit Dinur
On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors. APPROX-RANDOM 2010: 138-151
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 21:20 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: