Johan Håstad

Björn Martinsson

Electron. Colloquium Comput. Complex., 2025

2024

A Logarithmic Approximation of Linearly-Ordered Colourings.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

The EATCS Award 2023 - Laudatio for Amos Fiat.

[BibT_eX]

[DOI]

Bull. EATCS, 2023

On small-depth Frege proofs for PHP.

[BibT_eX]

[DOI]

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

2022

The EATCS Award 2023 - Call for Nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2022

On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited.

[BibT_eX]

[DOI]

Kilian Risse

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

2021

Explicit two-deletion codes with redundancy matching the existential bound.

[BibT_eX]

[DOI]

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

Optimal Inapproximability with Universal Factor Graphs.

[BibT_eX]

[DOI]

Jonah Brown-Cohen

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

2020

The EATCS Award 2021 - Call for Nominations.

[BibT_eX]

[DOI]

Marta Kwiatkowska

Éva Tardos

Bull. EATCS, 2020

d-Galvin Families.

[BibT_eX]

[DOI]

Guillaume Lagarde

Joseph Swernofsky

Electron. J. Comb., 2020

2019

Bounded Independence versus Symmetric Tests.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

Following a tangent of proofs.

[BibT_eX]

[DOI]

Proceedings of the Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali, 2019

2018

Knuth Prize Lecture: On the Difficulty of Approximating Boolean Max-CSPs.

[BibT_eX]

[DOI]

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

2017

On the Hardness of Approximating Balanced Homogenous 3-Lin.

[BibT_eX]

[DOI]

Rajsekar Manokaran

Theory Comput., 2017

An Improved Bound on the Fraction of Correctable Deletions.

[BibT_eX]

[DOI]

Boris Bukh

IEEE Trans. Inf. Theory, 2017

An Average-Case Depth Hierarchy Theorem for Boolean Circuits.

[BibT_eX]

[DOI]

J. ACM, 2017

Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers.

[BibT_eX]

[DOI]

Martin Ekerå

Proceedings of the Post-Quantum Cryptography - 8th International Workshop, 2017

On Small-Depth Frege Proofs for Tseitin for Grids.

[BibT_eX]

[DOI]

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

2016

The square lattice shuffle, correction.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2016

An Average-Case Depth Hierarchy Theorem for Higher Depth.

[BibT_eX]

[DOI]

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

Bounded Independence vs. Moduli.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Improved NP-Inapproximability for 2-Variable Linear Equations.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

On DNF Approximators for Monotone Boolean Functions.

[BibT_eX]

[DOI]

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

(2 + epsilon)-Sat Is NP-Hard.

[BibT_eX]

[DOI]

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

2013

Satisfying Degree-d Equations over GF[2]n.

[BibT_eX]

[DOI]

Theory Comput., 2013

(2+ε)-SAT is NP-hard.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On the power of many one-bit provers.

[BibT_eX]

[DOI]

Rafael Pass

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

On the correlation of parity and small-depth circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451).

[BibT_eX]

[DOI]

Andrei A. Krokhin

Dániel Marx

Dagstuhl Reports, 2012

Making the Long Code Shorter.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

On the Usefulness of Predicates.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

On the NP-Hardness of Max-Not-2.

[BibT_eX]

[DOI]

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

2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Making the long code shorter, with applications to the Unique Games Conjecture.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Satisfying Degree-d Equations over GF[2] n.

[BibT_eX]

[DOI]

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

2010

Special Issue "Conference on Computational Complexity 2009" Guest Editor's Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2010

An Efficient Parallel Repetition Theorem.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography, 7th Theory of Cryptography Conference, 2010

On the list-decodability of random linear codes.

[BibT_eX]

[DOI]

Swastik Kopparty

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Approximating Linear Threshold Predicates.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

Randomly supported independence and resistance.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Towards an optimal separation of space and length in resolution.

[BibT_eX]

[DOI]

Jakob Nordström

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

The Randomized Communication Complexity of Set Disjointness.

[BibT_eX]

[DOI]

Avi Wigderson

Theory Comput., 2007

The Security of the IAPM and IACBC Modes.

[BibT_eX]

[DOI]

J. Cryptol., 2007

On the Approximation Resistance of a Random Predicate.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

The square lattice shuffle.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2006

On Nontrivial Approximation of CSPs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

Every 2-CSP allows nontrivial approximation.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Randomness Extraction and Key Derivation Using the CBC, Cascade and HMAC Modes.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2004

2003

Inapproximability Some history and some open problems.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Combinatorial bounds for list decoding.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2002

On the advantage over a random assignment.

[BibT_eX]

[DOI]

Srinivasan Venkatesh

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

On Lower Bounds for Selecting the Median.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2001

A Slight Sharpening of LMN.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p.

[BibT_eX]

[DOI]

Gunnar Andersson

Lars Engebretsen

J. Algorithms, 2001

A Smaller Sleeping Bag for a Baby Snake.

[BibT_eX]

[DOI]

Svante Linusson

Johan Wästlund

Discret. Comput. Geom., 2001

Query Efficient PCPs with Perfect Completeness.

[BibT_eX]

[DOI]

Subhash Khot

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Simple Analysis of Graph Tests for Linearity and PCP.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

Practical Construction and Analysis of Pseudo-Randomness Primitives.

[BibT_eX]

[DOI]

Mats Näslund

Proceedings of the Advances in Cryptology, 2001

2000

Tight Bounds for Searching a Sorted Array of Strings.

[BibT_eX]

[DOI]

SIAM J. Comput., 2000

On bounded occurrence constraint satisfaction.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Hardness of Approximate Hypergraph Coloring.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

Funkspiel schemes: an alternative to conventional tamper resistance.

[BibT_eX]

[DOI]

Proceedings of the CCS 2000, 2000

1999

A Pseudorandom Generator from any One-way Function.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

On approximating CSP-B

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

The Security of all RSA and Discrete Log Bits

[BibT_eX]

[DOI]

Mats Näslund

Electron. Colloquium Comput. Complex., 1999

A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p.

[BibT_eX]

[DOI]

Gunnar Andersson

Lars Engebretsen

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Linear Consistency Testing.

[BibT_eX]

[DOI]

Proceedings of the Randomization, 1999

1998

The Shrinkage Exponent of de Morgan Formulas is 2.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Monotone Circuits for Connectivity Have Depth (log n)2-o(1).

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

On the Complexity of Interactive Proofs with Bounded Communication.

[BibT_eX]

[DOI]

Oded Goldreich

Inf. Process. Lett., 1998

Some Recent Strong Inapproximability Results.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1998

The Security of Individual RSA Bits.

[BibT_eX]

[DOI]

Mats Näslund

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Fitting Points on the Real Line and Its Application to RH Mapping.

[BibT_eX]

[DOI]

Lars Ivansson

Jens Lagergren

Proceedings of the Algorithms, 1998

1997

Some Optimal Inapproximability Results.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Circuit Bottom Fan-in and Computational Power.

[BibT_eX]

[DOI]

Liming Cai

Jianer Chen

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Analysis of Backoff Protocols for Multiple Access Channels.

[BibT_eX]

[DOI]

Brian Rogoff

SIAM J. Comput., 1996

On the Message Complexity of Interactive Proof Systems

[BibT_eX]

[DOI]

Oded Goldreich

Electron. Colloquium Comput. Complex., 1996

Testing of the Long Code and Hardness for Clique.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Clique is Hard to Approximate Within n1-epsilon.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

On the Shrinkage Exponent for Read-Once Formulae.

[BibT_eX]

[DOI]

Alexander A. Razborov

Andrew Chi-Chih Yao

Theor. Comput. Sci., 1995

Top-Down Lower Bounds for Depth-Three Circuits.

[BibT_eX]

[DOI]

Stasys Jukna

Pavel Pudlák

Comput. Complex., 1995

Monotone circuits for connectivity have depth (log n)2-o(1) (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

A tight lower bound for searching a sorted array.

[BibT_eX]

[DOI]

Arne Andersson

Ola Petersson

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Linearity Testing in Characteristic Two.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Optimal Depth, Very Small Size Circuits for Symmetric Functions in AC0.

[BibT_eX]

[DOI]

Inf. Comput., February, 1994

On the Size of Weights for Threshold Gates.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 1994

The Random Oracle Hypothesis Is False.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

On Average Time Hierarchies.

[BibT_eX]

[DOI]

Per Grape

Inf. Process. Lett., 1994

Recent Results in Hardness of Approximation.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1994

The complexity of searching a sorted array of strings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

Addendum to "Simple Construction of Almost k-wise Independent Random Variables".

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1993

The Discrete Logarithm Modulo a Composite Hides O(n) Bits.

[BibT_eX]

[DOI]

A. W. Schrift

Adi Shamir

J. Comput. Syst. Sci., 1993

A Well-Characterized Approximation Problem.

[BibT_eX]

[DOI]

Steven J. Phillips

Shmuel Safra

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

Top-Down Lower Bounds for Depth 3 Circuits

[BibT_eX]

[DOI]

Stasys Jukna

Pavel Pudlák

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

The shrinkage exponent is 2

[BibT_eX]

[DOI]

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Simple Construction of Almost k-wise Independent Random Variables.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1992

A Simple Lower Bound for Monotone Clique Using a Communication Game.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

Majority Gates vs. General Weighted Threshold Gates.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Relativized Perfect Zero Knowledge Is Not BPP

[BibT_eX]

[DOI]

Inf. Comput., August, 1991

Statistical Zero-Knowledge Languages can be Recognized in Two Rounds.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1991

1990

Pseudo-Random Generators under Uniform Assumptions

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

On the Power of Small-Depth Threshold Circuits

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Simple Constructions of Almost k-Wise Independent Random Variables

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Composition of the Universal Relation.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the Advances In Computational Complexity Theory, 1990

1989

Fast Computation Using Faulty Hypercubes (Extended Abstract)

[BibT_eX]

[DOI]

Mark Newman

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Tensor Rank is NP-Complete.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988

Solving Simultaneous Modular Equations of Low Degree.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

Reconstructing Truncated Integer Variables Satisfying Linear Congruences.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

Dual vectors and lower bounds for the nearest lattice point problem.

[BibT_eX]

[DOI]

Comb., 1988

Everything Provable is Provable in Zero-Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1988

1987

One-Way Permutations in NC0.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1987

Does co-NP Have Short Interactive Proofs?

[BibT_eX]

[DOI]

Ravi B. Boppana

Stathis Zachos

Inf. Process. Lett., 1987

Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract)

[BibT_eX]

[DOI]

Brian Rogoff

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract)

[BibT_eX]

[DOI]

Mark Newman

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Optimal Bounds for Decision Problems on the CRCW PRAM

[BibT_eX]

[DOI]

Paul Beame

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1986

Almost Optimal Lower Bounds for Small Depth Circuits

[BibT_eX]

[DOI]

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers.

[BibT_eX]

[DOI]

Proceedings of the STACS 86, 1986

On the Power of Interaction

[BibT_eX]

[DOI]

Shafi Goldwasser

Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985

The Cryptographic Security of Truncated Linearly Related Variables

[BibT_eX]

[DOI]

Adi Shamir

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

[BibT_eX]

[DOI]

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

On Using RSA with Low Exponent in a Public Key Network.

[BibT_eX]

[DOI]