Johan Håstad

Electron. Colloquium Comput. Complex., 2023

The EATCS Award 2023 - Laudatio for Amos Fiat.

[BibT_eX]

[DOI]

Bull. EATCS, 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]

IEEE Trans. Inf. Theory, 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

Optimal Inapproximability with Universal Factor Graphs.

[BibT_eX]

[DOI]

Jonah Brown-Cohen

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

Improved NP-Inapproximability for 2-Variable Linear Equations.

[BibT_eX]

[DOI]

Theory Comput., 2017

An Improved Bound on the Fraction of Correctable Deletions.

[BibT_eX]

[DOI]

Boris Bukh

IEEE Trans. Inf. Theory, 2017

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

(2+ε)-Sat Is NP-hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 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å

IACR Cryptol. ePrint Arch., 2017

On small-depth Frege proofs for Tseitin for grids.

[BibT_eX]

[DOI]

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

Electron. Colloquium Comput. Complex., 2016

Bounded independence vs. moduli.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

Making the Long Code Shorter.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

2014

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

On the Correlation of Parity and Small-Depth Circuits.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

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

[BibT_eX]

[DOI]

SIAM J. Comput., 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

On the usefulness of predicates.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2013

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

[BibT_eX]

[DOI]

Theory Comput., 2013

On the power of many one-bit provers.

[BibT_eX]

[DOI]

Rafael Pass

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

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

[BibT_eX]

[DOI]

Andrei A. Krokhin

Dániel Marx

Dagstuhl Reports, 2012

2011

Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Randomly Supported Independence and Resistance.

[BibT_eX]

[DOI]

SIAM J. Comput., 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

On the List-Decodability of Random Linear Codes.

[BibT_eX]

[DOI]

Swastik Kopparty

Electron. Colloquium Comput. Complex., 2010

Approximating Linear Threshold Predicates.

[BibT_eX]

[DOI]

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

2009

On the Approximation Resistance of a Random Predicate.

[BibT_eX]

[DOI]

Comput. Complex., 2009

2008

Practical Construction and Analysis of Pseudo-Randomness Primitives.

[BibT_eX]

[DOI]

Mats Näslund

J. Cryptol., 2008

Towards an Optimal Separation of Space and Length in Resolution.

[BibT_eX]

[DOI]

Jakob Nordström

Electron. Colloquium Comput. Complex., 2008

Every 2-csp Allows Nontrivial Approximation.

[BibT_eX]

[DOI]

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

A Smaller Sleeping Bag for a Baby Snake.

[BibT_eX]

[DOI]

Svante Linusson

Johan Wästlund

Discret. Comput. Geom., 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

Query Efficient PCPs with Perfect Completeness.

[BibT_eX]

[DOI]

Subhash Khot

Theory Comput., 2005

2004

On the advantage over a random assignment.

[BibT_eX]

[DOI]

Srinivasan Venkatesh

Random Struct. Algorithms, 2004

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

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2004

2003

Simple analysis of graph tests for linearity and PCP.

[BibT_eX]

[DOI]

Avi Wigderson

Random Struct. Algorithms, 2003

Fitting points on the real line and its application to RH mapping.

[BibT_eX]

[DOI]

Lars Ivansson

Jens Lagergren

J. Algorithms, 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

Hardness of Approximate Hypergraph Coloring.

[BibT_eX]

[DOI]

Madhu Sudan

SIAM J. Comput., 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

Linear-Consistency Testing.

[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

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

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

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

Circuit Bottom Fan-In and Computational Power.

[BibT_eX]

[DOI]

Liming Cai

Jianer Chen

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

1997

Clique is hard to approximate within n1-epsilon

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Some optimal inapproximability results

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

1996

Linearity testing in characteristic two.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 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

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

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

Inf. Process. Lett., 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

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

On the Power of Small-Depth Threshold Circuits.

[BibT_eX]

[DOI]

Comput. Complex., 1991

1990

Tensor Rank is NP-Complete.

[BibT_eX]

[DOI]

J. Algorithms, 1990

On the power of interaction.

[BibT_eX]

[DOI]

Shafi Goldwasser

Comb., 1990

Pseudo-Random Generators under Uniform Assumptions

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 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

Polynomial Time Algorithms for Finding Integer Relations among Real Numbers.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

Optimal bounds for decision problems on the CRCW PRAM.

[BibT_eX]

[DOI]

Paul Beame

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

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

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

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]