Badge
| Nice Answer | Answer score of 10 or more. This badge can be awarded multiple times. |
Ryan Williams earned this badge 72 times |
mar 7 at 6:31
Can one return to a TCS research job after an excursion to a non-research industry job?
jan 7 at 12:19
Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$
dec 16 at 21:53
Succint Problems in $\mathsf{P}$
nov 22 at 4:14
Complexity class associated with exhaustive search
sep 27 at 9:07
Implications of proof of abc conjecture for cs theory
may 10 '12 at 4:35
What is $\mathsf{NP}$ restricted to linear size witnesses?
apr 13 '12 at 19:53
How to compute powers of square matrices?
mar 25 '12 at 17:44
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
mar 12 '12 at 18:26
Oblivious Turing Machine emulation lowerbound
mar 6 '12 at 18:09
When are two algorithms said to be “similar”?
feb 25 '12 at 0:31
Solving $n$-SAT and #$n$-SAT
jan 10 '12 at 8:38
Are quasi-polynomial sized circuits for 3-SAT trivial?
dec 9 '11 at 0:09
Super-polynomial time approximation algorithms for MAX 3SAT
nov 21 '11 at 16:25
How many tautologies are there?
nov 17 '11 at 12:33
Uses of XORification
nov 17 '11 at 1:22
What are the consequences of $L = \oplus L$?
nov 10 '11 at 12:57
Toy examples for barriers to $P \ne NP$
oct 30 '11 at 17:43
(false?) proof for computability of a function
oct 12 '11 at 16:31
Results showing existence/non-existence of finite graphs with specific computable properties imply certain complexity results
sep 16 '11 at 19:34
NP-complete variants of undecidable problems?
sep 1 '11 at 14:30
Problems outside of P that are not P-hard
aug 30 '11 at 14:57
Fast sparse boolean matrix product with possible preprocessing
aug 25 '11 at 7:32
How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes
aug 16 '11 at 14:05
A data structure for minimum dot product queries
aug 12 '11 at 2:27
Complexity of Unique s-t-Connectivity
jul 25 '11 at 18:27
What hierarchies and/or hierarchy theorems do you know?
jul 13 '11 at 3:03
NTIME(n^k) ≠ DTIME(n^k) ?
jul 3 '11 at 7:05
Paradigms for complexity analysis of algorithms
may 27 '11 at 21:24
What is the big version of NC?
may 27 '11 at 20:19
Hierarchy for BPP vs derandomization
mar 12 '11 at 4:51
Is there any justification to believe that $NL\neq L$?
mar 8 '11 at 3:38
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
feb 14 '11 at 19:49
Is there a Time Hierarchy theorem for PH?
feb 9 '11 at 2:58
How do you get a “Physical Intuition” for results in TCS?
jan 23 '11 at 19:18
Techniques for Reversing the Order of Quantifiers
jan 18 '11 at 15:57
Highest lower bound on NP problems (TSP)
dec 17 '10 at 1:48
Finding a 5-cycle in a sparse graph efficiently.
nov 28 '10 at 0:50
Matrix multiplication in $O(n^2 \log n)$
nov 15 '10 at 14:53
Open problems on the frontiers of TCS
nov 11 '10 at 1:49
Open problems on the frontiers of TCS
nov 5 '10 at 0:33
Rigour leading to insight
nov 4 '10 at 14:28
Examples of the price of abstraction?
oct 26 '10 at 9:41
Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS?
oct 23 '10 at 18:17
Inspirational talk for final year high school pupils
oct 22 '10 at 0:57
Hardness of approximation assuming NP != coNP
oct 21 '10 at 8:51
Optimal greedy algorithms for NP-hard problems
oct 21 '10 at 7:31
True Bit Complexity of matrix multiplication is $O(n^{4})$
oct 21 '10 at 5:41
Permanents - Approximation and connection to integer factorization
oct 8 '10 at 2:40
NC = P consequences?
oct 7 '10 at 0:05
Is $AC^0/poly \cap NP$ contained in $P$?
oct 6 '10 at 17:45
Chernoff-type Inequality for pair-wise independent random variables
oct 2 '10 at 9:34
DFA intersection in subquadratic space?
