17,878 reputation
568129
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 7 months
seen 5 hours ago

algorithms/complexity extremist


Mar
9
awarded  Nice Answer
Mar
8
answered The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem
Mar
8
comment The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem
I think you mean "unary P not equal to unary NP"
Mar
5
awarded  Nice Answer
Mar
4
answered Scope of natural proofs barrier
Mar
4
comment Is MAX-SAT SETH (like) hard?
Probably he means: for every $\delta > 0$ there is a k such that max k sat $(1-1/2^k + \varepsilon)$-approximation needs at least $(2-\delta)^{2^k \varepsilon m}$ time. (Don't think this is true...)
Feb
28
comment Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
It occurs to me that the above is a pretty good example of what we mean by "Fine-grained complexity" (a Fall 2015 program at the Simons Institute). One of the key ideas is that complexity theory can look quite different when, instead of trying to find for each problem a (potentially bizarre) computational model for which that problem is "complete", one simply focuses on understanding what is the best possible runtime exponent for the problem.
Feb
27
awarded  Nice Answer
Feb
27
comment Is there an oracle such that SAT is not infinitely often in sub-exponential time?
EXP isn't in io SUBEXP, because in EXP we can diagonalize against (for example) the first n subexp time TMs, on the inputs of length n. Eventually, any particular subexp TM will appear among the first n, and on almost every input length our EXP machine can output the opposite value on at least one input of that length. I don't know of a reference that studies io things in detail but they appear in many papers.
Feb
27
answered Problems with big open complexity gaps
Feb
25
awarded  Good Question
Feb
25
comment Is there an oracle such that SAT is not infinitely often in sub-exponential time?
Thanks Lance. I missed the obvious!
Feb
24
accepted Is there an oracle such that SAT is not infinitely often in sub-exponential time?
Feb
24
awarded  Nice Question
Feb
24
awarded  Curious
Feb
23
asked Is there an oracle such that SAT is not infinitely often in sub-exponential time?
Feb
22
comment Computational Model in SETH
Regarding quantum algorithms, Grover gives about $$2^{n/2} $$ time for CNF SAT. But one could pose a "quantum SETH" which asserts that this square-root speedup is best possible.
Feb
9
comment An oracle relative to which EXP(NP) = BPP
Yes, there are oracles making them equal and oracles making them different, if I recall. Lance Fortnow knows the reference... I can try to look it up myself, but if you do a search on sciencedirect for it, you're likely to see it.
Jan
17
comment Graph with minimum number of edges having given sets of nodes as its paths
Why not just make a clique over all the nodes? That will support any set of paths you want
Jan
15
comment Deciding emptiness of intersection of regular languages in subquadratic time
So for example (based on Michael's comment), the strong exponential time hypothesis implies that the exponent should be 2. I think this could also proved to follow from the exponential time hypothesis...