Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Thomas's user avatar
Thomas's user avatar
Thomas's user avatar
Thomas
  • Member for 13 years, 6 months
  • Last seen more than a month ago
  • California, USA
20 votes

Is parameterized complexity going to be the future of complexity theory?

17 votes
Accepted

Matrix permanent is 0

16 votes

Complexity of Finding the Eigendecomposition of a Matrix

15 votes
Accepted

What is the proof of this nonstandard version of Azuma's inequality?

14 votes

Generalizing the "median trick" to higher dimensions?

12 votes
Accepted

Approximating #P-hard problems

11 votes
Accepted

Are there any distributions with only polynomially many non-zero Fourier coefficients and a small support?

9 votes

Chernoff Bounds for settings with limited dependence

8 votes

Do we have any nontrivial uniform circuits?

8 votes

Average-case analogue of Small-bias Spaces

7 votes

Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

6 votes

Sampling from the binomial distribution with limited randomness and time

6 votes

Does approximation degree of AND depend on error?

6 votes
Accepted

Min Hamming distance of a given string from substrings of another string

4 votes
Accepted

Differential Privacy and Randomized Responses for Counting Queries

4 votes

Is uniform convergence faster for low-entropy distributions?

3 votes
Accepted

Choosing 2*n values while evaluating Fast Fourier Transform

3 votes

Is being fooled by limited independence preserved by products?

2 votes

Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large?

2 votes

Which randomized algorithms have exponentially small error probability?

2 votes

Upper bound on the pseudoentropy of any distribution

2 votes

Algorithm for finding heavy hitters in a weighted stream

2 votes
Accepted

Optimal bounds for $k$-wise non-uniform random bits

2 votes
Accepted

Biased binary search?

1 vote

Random grid point in a d-dimensional ball