Mika Göös

Nathaniel Harms

Artur Riazanov

Proceedings of the Approximation, 2025

2024

Further Collapses in $\boldsymbol{\mathsf{TFNP}}$.

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Hardness Condensation by Restriction.

[BibT_eX]

[DOI]

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

One-Way Functions vs. TFNP: Simpler and Improved.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Depth-3 Circuits for Inner Product.

[BibT_eX]

[DOI]

Ziyi Guan

Tiberiu Mosnoi

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Top-Down Lower Bounds for Depth-Four Circuits.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Guest Column: Proofs, Circuits, and Communication.

[BibT_eX]

[DOI]

Susanna F. de Rezende

Robert Robere

SIGACT News, 2022

Proofs, Circuits, and Communication.

[BibT_eX]

[DOI]

Susanna F. de Rezende

Robert Robere

CoRR, 2022

On Semi-Algebraic Proofs and Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Lower Bounds for Unambiguous Automata via Communication Complexity.

[BibT_eX]

[DOI]

Stefan Kiefer

Weiqiang Yuan

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Separations in Proof Complexity and TFNP.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Randomised Composition and Small-Bias Minimax.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Further Collapses in TFNP.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

Communication Complexity of Collision.

[BibT_eX]

[DOI]

Siddhartha Jain

Proceedings of the Approximation, 2022

2021

Unambiguous DNFs from Hex.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Lower Bounds on Unambiguous Automata Complementation and Separation via Communication Complexity.

[BibT_eX]

[DOI]

Stefan Kiefer

CoRR, 2021

Automating algebraic proof systems is NP-hard.

[BibT_eX]

[DOI]

Susanna F. de Rezende

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Unambiguous DNFs and Alon-Saks-Seymour.

[BibT_eX]

[DOI]

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

A Majority Lemma for Randomised Query Complexity.

[BibT_eX]

[DOI]

Gilbert Maystre

Proceedings of the 36th Computational Complexity Conference, 2021

On the Power and Limitations of Branch and Cut.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Automating cutting planes is NP-hard.

[BibT_eX]

[DOI]

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

The Power of Many Samples in Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

When Is Amplification Necessary for Composition in Randomized Query Complexity?

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

Correction to: Query-to-Communication Lifting for P NP.

[BibT_eX]

[DOI]

Comput. Complex., 2019

Adventures in Monotone Complexity and TFNP.

[BibT_eX]

[DOI]

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

A Lower Bound for Sampling Disjoint Sets.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

String Matching: Communication, Circuits, and Learning.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Randomized Communication versus Partition Number.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Monotone circuit lower bounds from resolution.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria.

[BibT_eX]

[DOI]

Aviad Rubinstein

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

A Tight Lower Bound for Entropy Flattening.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Communication Lower Bounds via Query Complexity.

[BibT_eX]

[DOI]

PhD thesis, 2017

Linear-in-Δ lower bounds in the LOCAL model.

[BibT_eX]

[DOI]

Juho Hirvonen

Distributed Comput., 2017

Randomized Communication vs. Partition Number.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Query-to-Communication Lifting for BPP.

[BibT_eX]

[DOI]

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

Query-to-Communication Lifting for P^NP.

[BibT_eX]

[DOI]

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Locally Checkable Proofs in Distributed Computing.

[BibT_eX]

[DOI]

Theory Comput., 2016

Separating OR, SUM, and XOR circuits.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Non-local Probes Do Not Help with Many Graph Problems.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 30th International Symposium, 2016

The Landscape of Communication Complexity Classes.

[BibT_eX]

[DOI]

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

Extension Complexity of Independent Set Polytopes.

[BibT_eX]

[DOI]

Rahul Jain

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

Separations in Communication Complexity Using Cheat Sheets and Information Complexity.

[BibT_eX]

[DOI]

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

A Composition Theorem for Conical Juntas.

[BibT_eX]

[DOI]

T. S. Jayram

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Non-Local Probes Do Not Help with Graph Problems.

[BibT_eX]

[DOI]

CoRR, 2015

Rectangles Are Nonnegative Juntas.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.

[BibT_eX]

[DOI]

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

Deterministic Communication vs. Partition Number.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Lower Bounds for Clique vs. Independent Set.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Search methods for tile sets in patterned DNA self-assembly.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

Randomized distributed decision.

[BibT_eX]

[DOI]

Distributed Comput., 2014

Communication lower bounds via critical block sensitivity.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Linear-in-delta lower bounds in the LOCAL model.

[BibT_eX]

[DOI]

Juho Hirvonen

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

Communication Complexity of Set-Disjointness for All Probabilities.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

What can be decided locally without identifiers?

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

2012

Review of DISC 2012.

[BibT_eX]

[DOI]

SIGACT News, 2012

No Sublogarithmic-Time Approximation Scheme for Bipartite Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

Lower bounds for local approximation.

[BibT_eX]

[DOI]

Juho Hirvonen

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2012

2011

Locally checkable proofs.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

2010

Synthesizing Minimal Tile Sets for Patterned DNA Self-assembly.

[BibT_eX]

[DOI]