User Ryan Williams - Theoretical Computer Science Stack Exchange

Ryan Williams

Member for 13 years, 3 months
Last seen this week

Twitter
people.csail.mit.edu/rrw
Cambridge, MA, United States

159 Answers

Score Activity Newest

13 votes

Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results

answered Sep 16, 2010 at 15:17

13 votes

DFA intersection in subquadratic space?

answered Aug 19, 2010 at 3:21

13 votes

Generalized Ladner's Theorem

answered Aug 31, 2010 at 23:26

13 votes

What is the general consensus on the NL vs P question?

answered Jun 9 at 17:00

12 votes

Accepted

Space-time tradeoff lower bounds

answered Sep 2, 2010 at 0:42

12 votes

Accepted

Alternate notion of complexity based on gap between brute-force and the best algorithm?

answered Aug 22, 2010 at 19:55

12 votes

SC^2 algorithms for st-connectivity

answered Sep 25, 2010 at 20:05

12 votes

Introduction to spectral graph theory

answered Sep 10, 2010 at 21:04

12 votes

Fast sparse boolean matrix product with possible preprocessing

answered Oct 7, 2010 at 6:35

12 votes

Rigour leading to insight

answered Oct 13, 2010 at 16:34

12 votes

Accepted

Highest lower bound on NP problems (TSP)

answered Jan 17, 2011 at 23:12

12 votes

Accepted

Solving $n$-SAT and #$n$-SAT

answered Aug 27, 2011 at 8:29

12 votes

How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes

answered Aug 19, 2011 at 10:51

12 votes

Advanced techniques for determining complexity lower bounds

answered Aug 22, 2013 at 11:53

12 votes

Hardness of a subcase of Set Cover

answered Aug 31, 2013 at 13:19

12 votes

Accepted

Barriers to separating other complexity classes

answered Oct 8, 2013 at 21:02

11 votes

Problems not known to be PSPACE-complete

answered Mar 10, 2015 at 2:21

11 votes

On reducing the hardness of CNF-SAT to k-Clique

answered Mar 20, 2016 at 16:31

11 votes

Accepted

$NP$-complete problem with quasi-polynomial bound on the number of solutions

answered Nov 15, 2014 at 3:00

11 votes

Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

answered Nov 9, 2020 at 1:48

11 votes

Accepted

If NP in BPP then NP equals RP

answered Dec 22, 2019 at 20:40

11 votes

Accepted

Complexity class of efficient streaming algorithms

answered Apr 24, 2020 at 22:38

11 votes

Accepted

Law of the Excluded Middle in complexity theory

answered Sep 12 at 2:18

11 votes

Lower-bounds under SETH

answered Jun 7, 2022 at 0:38

10 votes

Bootstrapping results that really bootstrap

answered Jul 9, 2019 at 6:01

10 votes

Testing boolean vectors orthogonality with fast query-time

answered Dec 23, 2013 at 1:50

10 votes

Beigel-Tarui transformation of ACC cricuits

answered Aug 22, 2013 at 11:08

9 votes

Accepted

Non-uniform hierarchy theorem for approximating functions

answered May 8, 2012 at 0:38

9 votes

Accepted

Is there a relation between BBH (black box hypothesis) and SETH (strong exponential time hypothesis)?

answered Apr 20, 2019 at 20:35

9 votes

Accepted

Approximating Random MAX-k-SAT

answered Aug 19, 2011 at 19:16

4