Papers, presentations, notes, and random musings.
|
Antares Chen, Jonathan Shi, and Luca Trevisan
arXiv 2008.05648
|
|
Approximation Algorithms. Ball-growing with its application to Garg, Vazirani, and Yannakakis's \( 4 \ln (k+1) \)-approximation for multicut.
|
|
Approximation Algorithms. Buchbinder, Feldman, Naor, and Schwartz's double greedy algorithm for maximizing non-monotone submodular functions.
|
|
Approximation Algorithms. Cornuejols, Fisher, and Nemhauser's \( (1 - \frac{1}{e}) \)-approximation for maximizing monotone submodular functions.
|
|
Beyond Worst Case Analysis. Exactly recovering the planted bipartition in a stochastic block model using Abbe, Bandeira, and Hall's SDP-based algorithm.
|
|
Beyond Worst Case Analysis. McSherry's matrix perturbative analysis of a spectral algorithm for finding planted bipartitions in a stochastic block model.
|
|
Beyond Worst Case Analysis. Feige and Killian's SDP-based algorithm for finding planted cliques in \( \mathcal{G}_{n,p} \) and semi-random graphs.
|
|
Beyond Worst Case Analysis. The second-moment calculation demonstrating the largest clique in a \( \mathcal{G}_{n,1/2} \) graph has close to \( 2 \log n \) w.h.p. and a greedy algorithm for finding such a clique.
|
|
Beyond Worst Case Analysis. A review of discrete probability and linear algebra results useful for studying spectral and SDP-based algorithms.
|
|
Berkeley's CS294-154. SDP duality and the relationship between Sum of Squares and Sherali-Adams relaxation hierarchies.
|
|
Berkeley's CS294-154. Semi-definite programming and the degree-2 SoS relaxation for maxcut.
|
|
Berkeley's CS169. Derivations for the average wait times of M/M/1 and M/G/1 queues.
|
|
Berkeley's CS169. Derivation of Little's Law.
|
|
Berkeley's CS270. Final report on Buchbinder and Naor's online cover-pack framework with applications to competitive algorithms for online set cover and routing.
|
|
Berkeley CS294-128. Follow the Regularized Leader, Bregman divergence, and Online Mirror Descent.
|
|
Berkeley CS294-128. The \( \Omega(\log k) \)-competitive lower bound for randomized online paging and an introduction to the online cover-pack framework.
|