Alexander Golovnev

IEEE Trans. Inf. Theory, 2025

Special Section on The Sixty-Third Annual IEEE Symposium on Foundations of Computer Science (2022).

[BibT_eX]

[DOI]

Lijie Chen

Sathyawageeswar Subramanian

Huy Le Nguyen

SIAM J. Comput., 2025

2024

Sketching Approximability of All Finite CSPs.

[BibT_eX]

[DOI]

J. ACM, April, 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

On the Power of Adaptivity for Function Inversion.

[BibT_eX]

[DOI]

Karthik Gajulapalli

Samuel King

Proceedings of the 5th Conference on Information-Theoretic Cryptography, 2024

Hilbert Functions and Low-Degree Randomness Extractors.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

Matrix Multiplication Verification Using Coding Theory.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Improving 3N Circuit Complexity Lower Bounds.

[BibT_eX]

[DOI]

Comput. Complex., December, 2023

On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Lattice Problems beyond Polynomial Time.

[BibT_eX]

[DOI]

Vinod Vaikuntanathan

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Derandomization of Cell Sampling.

[BibT_eX]

[DOI]

Tom Gur

Igor Shinkar

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Polynomial formulations as a barrier for reduction-based hardness proofs.

[BibT_eX]

[DOI]

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

Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

Revisiting Time-Space Tradeoffs for Function Inversion.

[BibT_eX]

[DOI]

Siyao Guo

Spencer Peters

Proceedings of the Advances in Cryptology - CRYPTO 2023, 2023

The (Im)possibility of Simple Search-To-Decision Reductions for Approximation Problems.

[BibT_eX]

[DOI]

Siyao Guo

Spencer Peters

Proceedings of the Approximation, 2023

Range Avoidance for Constant Depth Circuits: Hardness and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

Linear space streaming lower bounds for approximating CSPs.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 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

Sketching Approximability of (Weak) Monarchy Predicates.

[BibT_eX]

[DOI]

Chi-Ning Chou

Amirbehshad Shahrasbi

Madhu Sudan

Santhoshini Velusamy

Proceedings of the Approximation, 2022

2021

Brakedown: Linear-time and post-quantum SNARKs for R1CS.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2021

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization.

[BibT_eX]

[DOI]

Siyao Guo

Spencer Peters

Electron. Colloquium Comput. Complex., 2021

Approximability of all finite CSPs in the dynamic streaming setting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Classification of the streaming approximability of Boolean CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Fine-grained hardness of CVP(P) - Everything that we can prove (and nothing else).

[BibT_eX]

[DOI]

Divesh Aggarwal

Huck Bennett

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

Circuit Depth Reductions.

[BibT_eX]

[DOI]

R. Ryan Williams

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Approximability of all finite CSPs with linear sketches.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications.

[BibT_eX]

[DOI]

Ishay Haviv

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Optimal Streaming Approximations for all Boolean Max-2CSPs.

[BibT_eX]

[DOI]

Chi-Ning Chou

Santhoshini Velusamy

CoRR, 2020

Data structures meet cryptography: 3SUM with preprocessing.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Polynomial Data Structure Lower Bounds in the Group Model.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat.

[BibT_eX]

[DOI]

Chi-Ning Chou

Santhoshini Velusamy

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Breaking the Encryption Scheme of the Moscow Internet Voting System.

[BibT_eX]

[DOI]

Pierrick Gaudry

Proceedings of the Financial Cryptography and Data Security, 2020

2019

AC0[p] Lower Bounds against MCSP via the Coin Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications.

[BibT_eX]

[DOI]

CoRR, 2019

On the computational complexity of the probabilistic label tree algorithms.

[BibT_eX]

[DOI]

Róbert Busa-Fekete

Krzysztof Dembczynski

CoRR, 2019

Static data structure lower bounds imply rigidity.

[BibT_eX]

[DOI]

Zeev Dvir

Omri Weinstein

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The information-theoretic value of unlabeled data in semi-supervised learning.

[BibT_eX]

[DOI]

Dávid Pál

Balázs Szörényi

Proceedings of the 36th International Conference on Machine Learning, 2019

AC<sup>0</sup>[p] Lower Bounds Against MCSP via the Coin Problem.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Collapsing Superstring Conjecture.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

String Matching: Communication, Circuits, and Learning.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Gate elimination: Circuit size lower bounds and #SAT upper bounds.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Circuit Depth Reductions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Collapsing Superstring Conjecture.

[BibT_eX]

[DOI]

CoRR, 2018

2017

Circuit Complexity: New Techniques and Their Limitations.

[BibT_eX]

[DOI]

PhD thesis, 2017

Tight Lower Bounds on Graph Embedding Problems.

[BibT_eX]

[DOI]

J. ACM, 2017

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

[BibT_eX]

[DOI]

Daniel Reichman

Igor Shinkar

CoRR, 2017

On the Quantitative Hardness of CVP.

[BibT_eX]

[DOI]

Huck Bennett

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

The Minrank of Random Graphs.

[BibT_eX]

[DOI]

Oded Regev

Omri Weinstein

Proceedings of the Approximation, 2017

2016

Families with Infants: Speeding Up Algorithms for NP-Hard Problems Using FFT.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Tight Bounds for Graph Homomorphism and Subgraph Isomorphism.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

On the Limits of Gate Elimination.

[BibT_eX]

[DOI]

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

Weighted Gate Elimination: Boolean Dispersers for Quadratic Varieties Imply Improved Circuit Lower Bounds.

[BibT_eX]

[DOI]

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

A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism.

[BibT_eX]

[DOI]

CoRR, 2015

A note on lower bounds for non-interactive message authentication using weak keys.

[BibT_eX]

[DOI]

Divesh Aggarwal

Proceedings of the 2015 IEEE Information Theory Workshop, 2015

Condensed Unpredictability.

[BibT_eX]

[DOI]

Maciej Skorski

Krzysztof Pietrzak

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

Lower Bounds for the Graph Homomorphism Problem.

[BibT_eX]

[DOI]

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

A Formal Treatment of Backdoored Pseudorandom Generators.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - EUROCRYPT 2015, 2015

2014

New exact algorithms for the 2-constraint satisfaction problem.

[BibT_eX]

[DOI]

Konstantin Kutzkov

Theor. Comput. Sci., 2014

Solving SCS for bounded length strings in fewer than 2<sup>n</sup> steps.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Approximating Asymmetric TSP in exponential Time.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2014

Families with Infants: A General Approach to Solve Hard Partition Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013

Solving 3-Superstring in 3 n/3 Time.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2013, 2013

Approximating Shortest Superstring Problem Using de Bruijn Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012

A New Algorithm for Parameterized MAX-SAT.

[BibT_eX]

[DOI]

Ivan Bliznets

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

2011

New Upper Bounds for MAX-2-SAT and MAX-2-CSP w.r.t. the Average Variable Degree.

[BibT_eX]

[DOI]