Using Martingales to Derive Robust Concentration Inequalities in Probability Theory
Examining popular concentration inequalities and deriving strengthenings for Martingales.
Blog
Examining popular concentration inequalities and deriving strengthenings for Martingales.
A pretty interesting implication involving \(\mathrm{P}\), \(\mathrm{NP}\), unary, and sparse languages.
Showing that non-uniform \(\mathrm{NC}_1\) language has a polynomial-size width-5 branching program.
Low-dimension embeddings, Bourgain's distortion proofs, and extensions to \(\ell_p\)-spaces.
List Decoding is really cool, but it also reveals some spectacular results in complexity theory.
The saga of how Andrew and I pranked Bill through cyclic shifts during thanksgiving break.
All problems in \(\mathrm{NL}_i\) have \(O(\log^{2i} n)\) depth, fan-in 2, Boolean circuits through \(\mathrm{USTCON}\).
A beautiful probabilistic argument for why most chords sound unpleasant to the human ear.
Showing that Lipschitz functions can be approximated by Bernstein polynomials.
Proving that \(\mathrm{BPP}\) is contained somewhere in the intersections of the polynomial hierarchy.
Hiring the best secretary in an online setting with a \(3.6\) röntgen (not great, not terrible) probability.
A proof of Toda's theorem, which is that the polynomial hierarchy can be captured by the ability to count.
A proof of Karp-Lipton's theorem, which is a surprising statement about the polynomial hierarchy and symmetric quantifiers.
Proving that the \(\mathrm{VC}\)-dimension, the measure of a finite dataset's complexity, is \(\Sigma_3^\mathrm P\)-complete, and can therefore be computed by counting.
Showing that the space complexity of the parity function, \(\mathrm L_n(\bigoplus_n)\), is quadratic in the number of its leaves, \(n\).
Exploiting buffer overflows to execute code on remote machines and accessing the root kernel of an actual Intel processor.
The role of cyclic and symmetric groups in making choices during extreme (hypothetical) life or death situations.
To the top
