D.W.'s user avatar
D.W.'s user avatar
D.W.'s user avatar
D.W.
  • Member for 12 years, 10 months
  • Last seen this week
19 votes
0 answers
1k views

Lower bounds on single-source shortest paths in directed graphs

14 votes
3 answers
2k views

Checking formulas with two quantifiers ($\forall \exists$) - 2QBF

11 votes
1 answer
174 views

Detecting circuit that's similar in functionality and implementation

11 votes
1 answer
377 views

Evaluate boolean circuit on batch of similar inputs

11 votes
1 answer
400 views

Evaluating symmetric polynomials

10 votes
0 answers
299 views

Approximating a convex polyhedron, with fewer inequalities

8 votes
2 answers
512 views

Streaming algorithms suitable for undergrad course

7 votes
0 answers
122 views

Learning function with a few low-order Fourier coefficients, from uniformly random samples

7 votes
0 answers
209 views

Generalization of SAT, where we replace OR with another symmetric function

7 votes
1 answer
1k views

Discrete log in GL(2,p)

5 votes
1 answer
2k views

Implementation that solves minimum set cover

5 votes
0 answers
202 views

Exploring a DFA, with no feedback

5 votes
1 answer
130 views

Commitment schemes with verification in NC0

4 votes
1 answer
423 views

Approximate-#SAT solver

4 votes
0 answers
160 views

Find index set partition that has large projections

3 votes
3 answers
490 views

Pairwise comparison of bit vectors

3 votes
0 answers
103 views

Estimate smooth vector, from dot-product queries

3 votes
1 answer
201 views

Binary search on coin heads probability

2 votes
0 answers
203 views

Oracle for Hamming distance to a secret bitvector

2 votes
2 answers
319 views

Sketches, using ideal hash functions

2 votes
0 answers
99 views

Optimal additive basis for decomposing/partitioning an integer as a sum of two integers