User Clement C.

7

23

votes

3

answers

2k

views

Generalizing the “median trick” to higher dimensions?

ds.algorithms randomized-algorithms

Sep 19 '15 at 3:40 Vitaly 881

2

23

votes

2

answers

668

views

Question about two matrices: Hadamard v. “the magical one” in the proof of the sensitivity conjecture

boolean-functions matrices boolean-matrix

Jul 9 '19 at 4:23 J.G 655

5

4

votes

0

answers

663

views

Minimizing a monotone submodular function under a cardinality constraint

reference-request submodularity minimization

Jan 31 '16 at 21:52 Yuval Filmus 14.1k

2

4

votes

1

answer

663

views

Autoencoders and information compression

machine-learning it.information-theory

May 23 '18 at 16:23 Anirbit 644

2

6

votes

2

answers

604

views

Applications of Takens' theorem to TCS?

machine-learning lg.learning physics

Aug 24 '19 at 2:08 Kalinda Vathupola 11

3

11

votes

4

answers

586

views

Lower bound for testing closeness in $L_2$ norm?

ds.algorithms lower-bounds st.statistics property-testing

Jul 29 '13 at 21:23 Community♦ 1

2

11

votes

2

answers

561

views

Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

reference-request randomized-algorithms property-testing

Jan 1 '15 at 21:31 Community♦ 1

6

12

votes

1

answer

449

views

Deterministic error reduction, state-of-the-art?

reference-request randomness pseudorandomness expanders

Jun 18 '19 at 3:08 guest 96

5

14

votes

1

answer

426

views

Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

reference-request pr.probability boolean-functions

Mar 25 '16 at 22:18 Neal Young 6,528

8

votes

2

answers

346

views

Analogue of $k$-wise independence for other distributions than uniform

reference-request k-wise-independence

Jan 2 at 12:20 Hhan 131

1

5

votes

1

answer

344

views

Gap-Hamming with different “threshold” (i.e., not $n/2$)

communication-complexity

Jun 3 '17 at 17:36 Clement C. 4,006

3

13

votes

0

answers

316

views

Fourier spectrum of the parity of two monotone Boolean functions

boolean-functions fourier-analysis monotone

Mar 7 '17 at 20:35 Clement C. 4,006

4

5

votes

1

answer

223

views

Minimizing a submodular function given noisy oracle access

reference-request optimization submodularity minimization

Nov 6 '16 at 19:42 Clement C. 4,006

1

4

votes

0

answers

220

views

One-way randomized complexity of (variants of) Gap-Hamming-Distance?

lower-bounds communication-complexity

Oct 17 '15 at 12:28 Clement C. 4,006

1

3

votes

0

answers

219

views

Testing sortedness of a normalized list of $n$ numbers

property-testing

Nov 18 '14 at 16:36 Juho 3,150

5

votes

0

answers

190

views

Generalization of Element Distinctness

reference-request property-testing

Jul 18 '19 at 5:41 Community♦ 1

2

votes

1

answer

181

views

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

reference-request randomness derandomization k-wise-independence

Mar 11 '19 at 21:56 Thomas 2,628

4

votes

1

answer

168

views

Newman's lemma for distributional communication complexity

randomness communication-complexity

Dec 16 '18 at 19:58 domotorp 13.2k

1

3

votes

1

answer

159

views

Separations between testing and tolerant testing for (natural) classes of functions?

reference-request lower-bounds property-testing

May 4 '18 at 18:00 Clement C. 4,006

2

4

votes

1

answer

149

views

Problems still “hard” in the SMP/Referee model with shared randomness?

reference-request communication-complexity

Mar 8 '16 at 15:15 Clement C. 4,006

1

7

votes

0

answers

144

views

Computing the $n$-th bit of the binary representation of $\pi$

time-complexity

Dec 10 at 22:53 Clement C. 4,006

1

3

votes

1

answer

102

views

Converting a Bernoulli to a Gaussian

randomized-algorithms it.information-theory randomness

Dec 16 at 0:47 Clement C. 4,006

2

votes

1

answer

93

views

Robustness to non-uniform randomness vs. one-sidedness

randomized-algorithms randomness property-testing

Apr 4 '19 at 20:15 D.W. 9,518

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

23 Questions

Generalizing the “median trick” to higher dimensions?

Question about two matrices: Hadamard v. “the magical one” in the proof of the sensitivity conjecture

Minimizing a monotone submodular function under a cardinality constraint

Autoencoders and information compression

Applications of Takens' theorem to TCS?

Lower bound for testing closeness in $L_2$ norm?

Lower bound on estimating $\sum_{k=1}^n a_k$ for non-increasing $(a_k)_k$

Deterministic error reduction, state-of-the-art?

Expected minimum influence of a random Boolean function $f\colon\{-1,1\}^n \to \{-1,1\}$

Analogue of $k$-wise independence for other distributions than uniform

Gap-Hamming with different “threshold” (i.e., not $n/2$)

Fourier spectrum of the parity of two monotone Boolean functions

Minimizing a submodular function given noisy oracle access

One-way randomized complexity of (variants of) Gap-Hamming-Distance?

Testing sortedness of a normalized list of $n$ numbers

Generalization of Element Distinctness

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

Newman's lemma for distributional communication complexity

Separations between testing and tolerant testing for (natural) classes of functions?

Problems still “hard” in the SMP/Referee model with shared randomness?

Computing the $n$-th bit of the binary representation of $\pi$

Converting a Bernoulli to a Gaussian

Robustness to non-uniform randomness vs. one-sidedness