User Ryan Williams

17 votes

Accepted

Are quasi-polynomial sized circuits for 3-SAT trivial?

answered Jan 7, 2012 at 18:54

17 votes

Constructivity in Natural Proof and Geometric Complexity

answered Jan 4, 2013 at 18:44

17 votes

Can one return to a TCS research job after an excursion to a non-research industry job?

answered Mar 6, 2013 at 18:56

17 votes

Books/Lecture Notes on Parametrized Complexity

answered May 22, 2013 at 21:27

17 votes

Accepted

What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

answered Apr 7, 2011 at 21:47

17 votes

Techniques for Reversing the Order of Quantiﬁers

answered Jan 22, 2011 at 19:18

17 votes

Accepted

Is there a Time Hierarchy theorem for PH?

answered Feb 13, 2011 at 16:28

17 votes

Proofs, Barriers and P vs NP

answered Sep 17, 2010 at 0:10

16 votes

Accepted

Permanents - Approximation and connection to integer factorization

answered Oct 18, 2010 at 6:53

16 votes

Accepted

Complexity of Unique s-t-Connectivity

answered Aug 11, 2011 at 10:55

16 votes

A data structure for minimum dot product queries

answered Aug 14, 2011 at 8:16

16 votes

Scope of natural proofs barrier

answered Mar 4, 2015 at 6:38

16 votes

Accepted

An obstruction like ETH

answered Apr 29, 2019 at 20:37

16 votes

Accepted

Is ALogTime != PH hard to prove (and unknown)?

answered May 9, 2016 at 7:07

16 votes

Accepted

Memory requirement for fast matrix multiplication

answered Aug 13, 2016 at 6:09

15 votes

Accepted

Smallest vertex cover which is also an independent set

answered Oct 3, 2016 at 4:50

15 votes

Accepted

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

answered Mar 8, 2015 at 6:31

15 votes

Accepted

Uses of XORification

answered Nov 16, 2011 at 23:53

15 votes

Accepted

Complexity Classes for Cases Other Than "Worst Case"

answered Sep 20, 2010 at 17:08

15 votes

Open problems on the frontiers of TCS

answered Sep 6, 2010 at 7:30

15 votes

Accepted

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

answered Aug 26, 2010 at 6:02

15 votes

Accepted

Are there natural separations in the nondeterministic time hierarchy?

answered Sep 1, 2010 at 16:36

14 votes

Generalized Ladner's Theorem

answered Aug 31, 2010 at 23:26

14 votes

Accepted

Are there alternatives to using polynomials in defining the different notions of efficient computation?

answered Aug 24, 2010 at 23:28

14 votes

Accepted

NP-complete variants of undecidable problems?

answered Sep 13, 2010 at 3:21

14 votes

MAX 1 in 2 SAT Algorithm

answered Aug 22, 2014 at 22:13

14 votes

Accepted

Complexity of k-clique for hypergraphs

answered Aug 12, 2015 at 7:12

13 votes

Does the isomorphism conjecture imply exponential lower bounds on witnesses density?

answered Nov 7, 2015 at 23:32

13 votes

Accepted

Collapses under the assumption that $NEXP\subseteq P/Poly$

answered Jul 20, 2016 at 14:16

13 votes

What is the fastest known simulation of BPP using Las Vegas algorithms?

answered Apr 1, 2013 at 1:40

Stack Exchange Network

160 Answers

Are quasi-polynomial sized circuits for 3-SAT trivial?

Constructivity in Natural Proof and Geometric Complexity

Can one return to a TCS research job after an excursion to a non-research industry job?

Books/Lecture Notes on Parametrized Complexity

What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

Techniques for Reversing the Order of Quantiﬁers

Is there a Time Hierarchy theorem for PH?

Proofs, Barriers and P vs NP

Permanents - Approximation and connection to integer factorization

Complexity of Unique s-t-Connectivity

A data structure for minimum dot product queries

Scope of natural proofs barrier

An obstruction like ETH

Is ALogTime != PH hard to prove (and unknown)?

Memory requirement for fast matrix multiplication

Smallest vertex cover which is also an independent set

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

Uses of XORification

Complexity Classes for Cases Other Than "Worst Case"

Open problems on the frontiers of TCS

What are the best known upper bounds and lower bounds for computing O(log n)-Clique?

Are there natural separations in the nondeterministic time hierarchy?

Generalized Ladner's Theorem

Are there alternatives to using polynomials in defining the different notions of efficient computation?

NP-complete variants of undecidable problems?

MAX 1 in 2 SAT Algorithm

Complexity of k-clique for hypergraphs

Does the isomorphism conjecture imply exponential lower bounds on witnesses density?

Collapses under the assumption that $NEXP\subseteq P/Poly$

What is the fastest known simulation of BPP using Las Vegas algorithms?