User Jason Gaitonde - Theoretical Computer Science Stack Exchange

Jason Gaitonde

Member for 3 years, 9 months
Last seen this week

15 Answers

Score Activity Newest

9 votes

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

answered Jul 8, 2019 at 4:41

9 votes

Accepted

Does two-sided error have more capability than one-sided error?

answered Jan 11, 2020 at 3:38

8 votes

Accepted

On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

answered Oct 15, 2020 at 21:55

5 votes

Accepted

Dual to hypercontractive inequality

answered Oct 14, 2019 at 17:44

5 votes

Accepted

Big-O bounds on the k-th largest element of iid Gaussians

answered Jun 28, 2019 at 1:24

5 votes

Accepted

XOR Resilient Encoding

answered Mar 18, 2021 at 23:35

3 votes

Accepted

Finding the size $k$ subset in a metric space that maximizes the min distance between elements

answered Apr 13, 2020 at 5:43

2 votes

Accepted

How many more colours do you need if you add to $G$ a maximum matching from $G^c$?

answered Nov 16, 2020 at 19:13

2 votes

Chain rule for KL divergence

answered Jun 29, 2019 at 3:16

2 votes

Accepted

Nonconstructive $\log(n)$ seed length PRG for fooling modular tests

answered Jan 21 at 18:03

2 votes

Face-splitting product of two Vandermonde matrices: When is is invertible?

answered Oct 7, 2020 at 14:23

1 vote

Accepted

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

answered Mar 16 at 23:48

1 vote

Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$

answered Nov 26, 2020 at 20:39

1 vote

Accepted

Sum-of-Squares Certificates

answered Sep 29, 2020 at 22:03

0 votes

Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm

answered Mar 23 at 15:46