Alexander Golovnev

Samuel King

Electron. Colloquium Comput. Complex., 2024

2023

Improving 3N Circuit Complexity Lower Bounds.

[BibT_eX]

[DOI]

Comput. Complex., December, 2023

Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Matrix Multiplication Verification Using Coding Theory.

[BibT_eX]

[DOI]

CoRR, 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

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

[BibT_eX]

[DOI]

Siyao Guo

Spencer Peters

Proceedings of the Approximation, 2023

2022

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

[BibT_eX]

[DOI]

Ishay Haviv

Theory Comput., 2022

Revisiting Time-Space Tradeoffs for Function Inversion.

[BibT_eX]

[DOI]

Siyao Guo

Spencer Peters

Electron. Colloquium Comput. Complex., 2022

Sketching Approximability of (Weak) Monarchy Predicates.

[BibT_eX]

[DOI]

Chi-Ning Chou

Sathyawageeswar Subramanian

Amirbehshad Shahrasbi

Madhu Sudan

Santhoshini Velusamy

Electron. Colloquium Comput. Complex., 2022

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Worst-Case to Average-Case Reductions via Additive Combinatorics.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Linear Space Streaming Lower Bounds for Approximating CSPs.

[BibT_eX]

[DOI]

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

2020

Polynomial Data Structure Lower Bounds in the Group Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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

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

On the limits of gate elimination.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2018

Circuit Depth Reductions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Static Data Structure Lower Bounds Imply Rigidity.

[BibT_eX]

[DOI]

Zeev Dvir

Omri Weinstein

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

2016

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

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

A Formal Treatment of Backdoored Pseudorandom Generators.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

The Minrank of Random Graphs.

[BibT_eX]

[DOI]

Oded Regev

Omri Weinstein

Electron. Colloquium Comput. Complex., 2016

Circuit size lower bounds and #SAT upper bounds through a general framework.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2015

Condensed Unpredictability.

[BibT_eX]

[DOI]

Maciej Skorski

Krzysztof Pietrzak

IACR Cryptol. ePrint Arch., 2015

A Note on Lower Bounds for Non-interactive Message Authentication Using Weak Keys.

[BibT_eX]

[DOI]

Divesh Aggarwal

IACR Cryptol. ePrint Arch., 2015

Weighted gate elimination: Boolean dispersers for quadratic varieties imply improved circuit lower bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

A better-than-3n lower bound for the circuit complexity of an explicit function.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Tight Bounds for Subgraph Isomorphism and Graph Homomorphism.

[BibT_eX]

[DOI]

CoRR, 2015

Lower Bounds for the Graph Homomorphism Problem.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 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]