Enlightened - Badge - Theoretical Computer Science Stack Exchange

Enlightened

First to answer and accepted with score of 10 or more. This badge can be awarded multiple times.

Ryan Williams

27.3k7 gold badges114 silver badges163 bronze badges

earned this badge 44 times.

Law of the Excluded Middle in complexity theory

Awarded Sep 21 at 22:57

Complexity class of efficient streaming algorithms

Awarded May 4, 2020 at 0:50

If NP in BPP then NP equals RP

Awarded Dec 26, 2019 at 1:10

Complexity of k-clique for hypergraphs

Awarded Aug 26, 2019 at 20:00

An obstruction like ETH

Awarded Apr 30, 2019 at 19:40

Smallest vertex cover which is also an independent set

Awarded Oct 6, 2016 at 16:02

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

Awarded Aug 24, 2016 at 21:36

Memory requirement for fast matrix multiplication

Awarded Aug 15, 2016 at 13:24

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

Awarded May 10, 2016 at 19:32

How is the MA version of SETH proven to be false?

Awarded Jan 20, 2016 at 14:32

Potentially equal complexity classes without known contradictory relativizations

Awarded Nov 12, 2015 at 20:11

Space-time tradeoff lower bounds

Awarded Nov 12, 2015 at 15:32

NTIME(n^k) ≠ DTIME(n^k) ?

Awarded Nov 6, 2015 at 22:48

smallest circuit size using XOR gates

Awarded Aug 15, 2015 at 13:08

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

Awarded Jan 7, 2015 at 19:29

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

Awarded Feb 19, 2014 at 19:57

Computational Model in SETH

Awarded Dec 2, 2013 at 13:35

How many tautologies are there?

Awarded Oct 22, 2013 at 23:27

Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?

Awarded Jan 11, 2013 at 5:57

Are there natural separations in the nondeterministic time hierarchy?

Awarded Jan 9, 2013 at 5:19

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

Awarded Jan 8, 2013 at 4:12

Consequences of a $O^*(2^{n / \log(n \log n)} )$ algorithm for a #P-complete problem

Awarded Sep 12, 2012 at 10:57

Is "Experimental Complexity Theory" being used to solve open problems?

Awarded Jul 26, 2012 at 6:10

What is $\mathsf{NP}$ restricted to linear size witnesses?

Awarded May 10, 2012 at 17:25

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

Awarded Mar 26, 2012 at 5:24

Characterization of problems for which sublinear time algorithms exist

Awarded Mar 8, 2012 at 5:53

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

Awarded Feb 25, 2012 at 3:12

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

Awarded Jan 10, 2012 at 9:18

Super-polynomial time approximation algorithms for MAX 3SAT

Awarded Dec 15, 2011 at 10:17

Complexity of Unique s-t-Connectivity

Awarded Aug 12, 2011 at 8:12

Do all complexity classes have a leaf language characterization?

Awarded Jul 7, 2011 at 4:42

Paradigms for complexity analysis of algorithms

Awarded Jul 3, 2011 at 8:00

What is the big version of NC?

Awarded May 31, 2011 at 20:08

Permanents - Approximation and connection to integer factorization

Awarded Mar 29, 2011 at 17:02

Is there any justification to believe that $NL\neq L$?

Awarded Mar 13, 2011 at 7:34

Is there a Time Hierarchy theorem for PH?

Awarded Feb 16, 2011 at 7:47

Highest lower bound on NP problems (TSP)

Awarded Feb 6, 2011 at 18:08

Matrix multiplication in $O(n^2 \log n)$

Awarded Nov 28, 2010 at 16:15

True Bit Complexity of matrix multiplication is $O(n^{4})$

Awarded Oct 21, 2010 at 9:46

NC = P consequences?

Awarded Oct 8, 2010 at 3:10

Lower bounds on #SAT?

Awarded Oct 1, 2010 at 7:40

Space complexity of Coppersmith–Winograd algorithm

Awarded Sep 17, 2010 at 0:50

Is there a complexity theory analogue of Rice's theorem in computability theory?

Awarded Aug 30, 2010 at 3:24

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

Awarded Aug 29, 2010 at 18:53

Others with this badge