17,898 reputation
568129
bio website stanford.edu/~rrwill
location California
age
visits member for 4 years, 8 months
seen yesterday

algorithms/complexity extremist


Nov
17
revised $NP$-complete problem with quasi-polynomial bound on the number of solutions
added 140 characters in body
Nov
15
comment Practically Good Algorithms of a Very Low Computational Complexity Class
Here's an optimization example... maybe. MAX-LIN: given a large (inconsistent) system of linear equations over GF(2), find a solution that maximizes the number of equations satisfied. This problem cannot be approximated with a factor larger than 1/2 unless P=NP, hence even approximately solving is very difficult. Nevertheless, it seems a 1/2-approximation (which is apparently the best possible) can be computed in TC0: a random assignment works, so we can choose poly(n) assignments (hard-coded) and evaluate the linear system on each one, outputting the best. Maybe I'm missing your point.
Nov
15
answered $NP$-complete problem with quasi-polynomial bound on the number of solutions
Nov
1
awarded  Good Answer
Oct
30
answered Pseudorandom generators indistinguishable by uniform deterministic adversaries
Oct
27
awarded  Nice Answer
Oct
26
comment Natural NP-complete problems with “large” witnesses
Actually, the witness size for Graph Isomorphism and Hamiltonian Path could be seen as sublinear in the input (given that the input is the $n \times n$ adjacency matrix of the graph).
Sep
30
awarded  Explainer
Sep
24
awarded  Autobiographer
Aug
30
comment Finding similar vectors in subquadratic time
Do you work for twitter?blog.twitter.com/2014/all-pairs-similarity-via-dimsum Seriously, even detecting if there is an edge in this graph (I.e. that it's not an independent set of vertices) is going to be very hard to do faster than $O(n^2)$ for an arbitrary similarity function.
Aug
29
comment Large classes which contain LOGSPACE for which strict inclusions are unknown
Yeah, I know about that one too, and other references as well. But I kept to a summary answer that wouldn't take more than 10 minutes to write.
Aug
28
answered Large classes which contain LOGSPACE for which strict inclusions are unknown
Aug
23
awarded  Nice Answer
Aug
22
answered MAX 1 in 2 SAT Algorithm
Aug
17
awarded  Yearling
Aug
3
reviewed Close What can we say about all cycles in graphs (connected undirected graph)
Jul
7
awarded  Custodian
May
21
awarded  Custodian
May
12
comment Arguments for/against Kolmogorov's conjecture about the circuit complexity of P
Roadblocks? I don't think anyone has found the road :) Since most people believe that $P$ doesn't have $O(n^k)$ size circuits, for every fixed $k$, probably few people have even looked for the road.
May
12
awarded  Nice Answer