2024
Erratum: Multitasking Capacity: Hardness Results and Improved Constructions.
SIAM J. Discret. Math., 2024
On the Power of Interactive Proofs for Learning.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Matrix Multiplication Reductions.
Proceedings of the Approximation, 2024
2023
On mappings on the hypercube with small average stretch.
Comb. Probab. Comput., March, 2023
Derandomization of Cell Sampling.
Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023
2022
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity.
SIAM J. Comput., 2022
Meyniel Extremal Families of Abelian Cayley Graphs.
Graphs Comb., 2022
Quantum Worst-Case to Average-Case Reductions for All Linear Problems.
Electron. Colloquium Comput. Complex., 2022
Worst-Case to Average-Case Reductions via Additive Combinatorics.
Electron. Colloquium Comput. Complex., 2022
2020
Multitasking Capacity: Hardness Results and Improved Constructions.
SIAM J. Discret. Math., 2020
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality.
Electron. Colloquium Comput. Complex., 2020
Relaxed Locally Correctable Codes with Improved Parameters.
Electron. Colloquium Comput. Complex., 2020
2019
On percolation and -hardness.
Random Struct. Algorithms, 2019
On Local Testability in the Non-Signaling Setting.
Electron. Colloquium Comput. Complex., 2019
Sorting Networks on Restricted Topologies.
Proceedings of the SOFSEM 2019: Theory and Practice of Computer Science, 2019
String Matching: Communication, Circuits, and Learning.
Proceedings of the Approximation, 2019
2018
An Entropy Lower Bound for Non-Malleable Extractors.
Electron. Colloquium Comput. Complex., 2018
Probabilistic Checking against Non-Signaling Strategies from Linearity Testing.
Electron. Colloquium Comput. Complex., 2018
Testing Linearity against Non-Signaling Strategies.
Electron. Colloquium Comput. Complex., 2018
On Lipschitz Bijections Between Boolean Functions.
Comb. Probab. Comput., 2018
2017
On Axis-Parallel Tests for Tensor Product Codes.
Electron. Colloquium Comput. Complex., 2017
Detecting Patterns Can Be Hard: Circuit Lower Bounds for the String Matching Problem.
CoRR, 2017
A graph-theoretic approach to multitasking.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
2016
Two-sided error proximity oblivious testing.
Random Struct. Algorithms, 2016
A Tight Upper Bound on Acquaintance Time of Graphs.
Graphs Comb., 2016
An Õ(n) Queries Adaptive Tester for Unateness.
Electron. Colloquium Comput. Complex., 2016
On Coloring Random Subgraphs of a Fixed Graph.
CoRR, 2016
An $\widetilde{O}(n)$ Queries Adaptive Tester for Unateness.
CoRR, 2016
A Graph-Theoretic Approach to Multitasking.
CoRR, 2016
On Percolation and NP-Hardness.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
2015
On Percolation and NP-Hardness.
Electron. Colloquium Comput. Complex., 2015
On Hardness of Approximating the Parameterized Clique Problem.
Electron. Colloquium Comput. Complex., 2015
2014
Acquaintance Time of a Graph.
SIAM J. Discret. Math., 2014
Zero-Fixing Extractors for Sub-Logarithmic Entropy.
Electron. Colloquium Comput. Complex., 2014
The Complexity of DNF of Parities.
Electron. Colloquium Comput. Complex., 2014
Comb. Probab. Comput., 2014
A Note on Subspace Evasive Sets.
Chic. J. Theor. Comput. Sci., 2014
2013
On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors.
Electron. Colloquium Comput. Complex., 2013
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball.
Electron. Colloquium Comput. Complex., 2013
2012
Two-Sided Error Proximity Oblivious Testing - (Extended Abstract).
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012