Skip to main content
Thomas's user avatar
Thomas's user avatar
Thomas's user avatar
Thomas
  • Member for 13 years, 7 months
  • Last seen more than a week ago
  • California, USA
4 votes

Is uniform convergence faster for low-entropy distributions?

2 votes
Accepted

Biased binary search?

2 votes
Accepted

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

8 votes

Average-case analogue of Small-bias Spaces

15 votes
Accepted

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

20 votes

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

4 votes
Accepted

Differential Privacy and Randomized Responses for Counting Queries

1 vote

Random grid point in a d-dimensional ball

3 votes
Accepted

Choosing 2*n values while evaluating Fast Fourier Transform

6 votes
Accepted

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

17 votes
Accepted

Matrix permanent is 0

2 votes

Algorithm for finding heavy hitters in a weighted stream

14 votes

Generalizing the "median trick" to higher dimensions?

2 votes

Upper bound on the pseudoentropy of any distribution

2 votes

Which randomized algorithms have exponentially small error probability?

6 votes

Does approximation degree of AND depend on error?

2 votes

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

8 votes

Do we have any nontrivial uniform circuits?

6 votes

Sampling from the binomial distribution with limited randomness and time

12 votes
Accepted

Approximating #P-hard problems

7 votes

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

3 votes

Is being fooled by limited independence preserved by products?

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

16 votes

Complexity of Finding the Eigendecomposition of a Matrix