Papers, presentations, notes, and random musings.


Antares Chen, Jonathan Shi, and Luca Trevisan
arXiv 2008.05648


Eliane S. Wiese, Michael Yen, Antares Chen, Lucas A. Santos, and Armando Fox.
Learning@Scale 2017
Antares Chen, Eliane S. Wiese, HeZheng Yin, Rohan Choudhury, and Armando Fox.
LWMOOCS 2016 [slides]
Antares Chen, David G. Harris, Aravind Srinivasan
SODA 2016 [slides]

Notes from Berkeley's UGTCS

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.

Notes from classes

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.