Lorenzo Orecchia
Contact Info
617
Soda Hall
Berkeley,
CA 94720
USA
orecchia
at eecs.berkeley.edu
I am a Ph.D. student in
theoretical computer science. My
advisor is Satish Rao.
I am interested in
algorithms for graph partitioning.
For details, please see my
Curriculum Vitae (pdf).
Publications and Preprints
Fast Approximation Algorithms for Graph Partitioning Using Spectral and
Semidenite-Programming Techniques(pdf)
UC Berkeley Dissertation, May 2011.
A Note on Graph Sparsification by Sampling
In preparation.
A Spectral Algorithm
with Applications to Exploring Data Graphs Locally (pdf)
With Michael W. Mahoney and Nisheeth K. Vishnoi.
In preparation.
Towards an SDP-Based
Approach to Spectral Methods: A
Nearly-Linear Time Algorithm for Graph Partitioning and Decomposition (pdf)
With
Nisheeth K. Vishnoi.
SODA
2011.
Implementing
Regularization Implicitly Via Approximate Eigenvector Computation (pdf)
With
Michael W. Mahoney.
arXiv:1010.0703v1
[cs.DS], 2010. Accepted at ICML 2011.
Optimal design of
oligomer libraries using pseudo-de-Bruijn sets
With Samantha J. Riesenfeld and Katherine S.
Pollard.
Submitted.
Empirical Evaluation of
Graph Partitioning Using Spectral Embeddings and Flow (pdf)
With
Kevin J. Lang and Michael W. Mahoney.
SEA
2009.
A Spectral Algorithm
for Improving Graph Partitions (pdf)
With
Michael W. Mahoney and Nisheeth K. Visnoi.
arXiv:0912.0681v1
[cs.DS], 2009.
On Partitioning Graphs
via Single Commodity Flows (pdf)
With
Leonard Schulman, Umesh V. Vazirani, and Nisheeth K. Vishnoi.
STOC
2008.
On a Cut-Matching Game
for the Sparsest Cut Problem (pdf)
With
Rohit Khandekar, Subhash A. Khot, and Nisheeth K. Vishnoi.
EECS
Dept., UC Berkeley, Tech. Rep. UCB/EECS-2007-177, Dec. 2007.
Localized Techniques
for Broadcasting in Wireless Sensor Networks (pdf)
With
Devidatt Dubhashi, Olle HŠggstršm, Alessandro Panconesi, Chiara Petrioli, and Andrea
Vitaletti.
Algorithmica,
49-4, Dec. 2007.
Localized Techniques
for Broadcasting in Wireless Sensor Networks (pdf)
With
Alessandro Panconesi, Chiari Petrioli, and Andrea Vitaletti.
DIALM-POMC
Workshop on the Foundations of Mobile Computing, Philadelphia, Oct. 2004.
Selected Talks
Implementing Regularization Implicitly By Approximate Eigenvector Computation
(pdf)
ICML 2011.
Matrix Multiplicative Weight Updates and Fast Graph Algorithms
(pdf)
A general talk about my current research.
Towards an SDP-based Approach to Spectral Methods:
A Nearly-linear-time Algorithm for Graph Partitioning and Decomposition (pdf)
SODA 2011.
How to Use SDPs in the
Design of Fast Spectral Algorithms:
Finding Balanced Cuts and Larged Induced Expanders (pdf)
Theory
Seminar, EECS Dept., UC Berkeley, Apr. 2010.
On Partitioning Graphs
via Single Commodity Flows (pdf)
STOC
2008.
Personal