Igor Shinkar

Harsimran Singh

Proceedings of the Approximation, 2025

2024

Erratum: Multitasking Capacity: Hardness Results and Improved Constructions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2024

On the Power of Interactive Proofs for Learning.

[BibT_eX]

[DOI]

Mohammad Mahdi Khodabandeh

Mohammad Mahdi Jahanara

Ninad Rajgopal

Bahar Salamatian

Sathyawageeswar Subramanian

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Quantum Worst-Case to Average-Case Reductions for All Linear Problems.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Matrix Multiplication Reductions.

[BibT_eX]

[DOI]

Ashish Gola

Harsimran Singh

Proceedings of the Approximation, 2024

2023

On mappings on the hypercube with small average stretch.

[BibT_eX]

[DOI]

Lucas Boczkowski

Comb. Probab. Comput., March, 2023

Derandomization of Cell Sampling.

[BibT_eX]

[DOI]

Alexander Golovnev

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

2022

Meyniel Extremal Families of Abelian Cayley Graphs.

[BibT_eX]

[DOI]

Fatemeh Hasiri

Graphs Comb., 2022

Worst-case to average-case reductions via additive combinatorics.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Relaxed Locally Correctable Codes with Improved Parameters.

[BibT_eX]

[DOI]

Vahid R. Asadi

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Multitasking Capacity: Hardness Results and Improved Constructions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality.

[BibT_eX]

[DOI]

Mohammad Mahdi Jahanara

Sajin Koroth

Electron. Colloquium Comput. Complex., 2020

Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

On Local Testability in the Non-Signaling Setting.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

On percolation and -hardness.

[BibT_eX]

[DOI]

Huck Bennett

Random Struct. Algorithms, 2019

Sorting Networks on Restricted Topologies.

[BibT_eX]

[DOI]

Indranil Banerjee

Dana Richards

Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019

Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

String Matching: Communication, Circuits, and Learning.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

An Entropy Lower Bound for Non-Malleable Extractors.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

On Lipschitz Bijections Between Boolean Functions.

[BibT_eX]

[DOI]

Shravas Rao

Comb. Probab. Comput., 2018

Testing Linearity against Non-Signaling Strategies.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem.

[BibT_eX]

[DOI]

Alexander Golovnev

CoRR, 2017

A graph-theoretic approach to multitasking.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

On Axis-Parallel Tests for Tensor Product Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Two-sided error proximity oblivious testing.

[BibT_eX]

[DOI]

Oded Goldreich

Random Struct. Algorithms, 2016

A Tight Upper Bound on Acquaintance Time of Graphs.

[BibT_eX]

[DOI]

Omer Angel

Graphs Comb., 2016

On Coloring Random Subgraphs of a Fixed Graph.

[BibT_eX]

[DOI]

CoRR, 2016

An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.

[BibT_eX]

[DOI]

Subhash Khot

CoRR, 2016

A Graph-Theoretic Approach to Multitasking.

[BibT_eX]

[DOI]

CoRR, 2016

On Hardness of Approximating the Parameterized Clique Problem.

[BibT_eX]

[DOI]

Subhash Khot

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

The Complexity of DNF of Parities.

[BibT_eX]

[DOI]

Gil Cohen

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

On Percolation and NP-Hardness.

[BibT_eX]

[DOI]

Huck Bennett

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

An ~O(n) Queries Adaptive Tester for Unateness.

[BibT_eX]

[DOI]

Subhash Khot

Proceedings of the Approximation, 2016

2015

On Percolation and NP-Hardness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Direct Sum Testing.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Zero-Fixing Extractors for Sub-Logarithmic Entropy.

[BibT_eX]

[DOI]

Gil Cohen

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

Acquaintance Time of a Graph.

[BibT_eX]

[DOI]

Itai Benjamini

Gilad Tsur

SIAM J. Discret. Math., 2014

Greedy Random Walk.

[BibT_eX]

[DOI]

Tal Orenshtein

Comb. Probab. Comput., 2014

Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball.

[BibT_eX]

[DOI]

Itai Benjamini

Gil Cohen

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2012

A Note on Subspace Evasive Sets.

[BibT_eX]

[DOI]

Avraham Ben-Aroya

Electron. Colloquium Comput. Complex., 2012

Two-Sided Error Proximity Oblivious Testing - (Extended Abstract).

[BibT_eX]

[DOI]

Oded Goldreich

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2010

On the Conditional Hardness of Coloring a 4-Colorable Graph with Super-Constant Number of Colors.

[BibT_eX]

[DOI]

Irit Dinur