Moritz Hardt

I'm a 3^rd year Ph.D. student in Computer Science at Princeton University. My advisor is Boaz Barak. I spent a year as a research scholar at Carnegie Mellon University hosted by Steven Rudich and three years at Saarland University from where I obtained a B.S. and an M.S. in Computer Science. My research interests include algorithms and optimization, complexity theory, as well as foundations of cryptography and privacy. I am particularly interested in problems of high-dimensional geometric and probabilistic nature.

Publications

An Algorithmic Proof of Forster's Lower Bound

Manuscript.

Versions: Video lecture at IAS

Forster's lower bound (2001) on the sign rank of a matrix is a fundamental theorem in communication complexity with applications to learning theory. We give a short, arguably simpler and algorithmic proof of Forster's theorem. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists. We believe that this may be of independent interest. Our algorithm builds on tools due to Barthe (1998) that are related to the equality cases of the generalized Brascamp-Lieb inequalities.
On the Geometry of Differential Privacy

with Kunal Talwar. In STOC 2010

Versions: Technical Report (arXiv)

We give the first differentially private mechanisms with optimal error complexity in the non-adaptive linear query model. Our approach is based on a connection to high-dimensional convex geometry.
Subsampling Semidefinite Programs and Max-Cut on the Sphere

with Boaz Barak, Thomas Holenstein and David Steurer. Manuscript.

Versions: Technical Report (ECCC)

We prove property testing like bounds for semidefinite programming hierarchies and show some applications including a certifying algorithm for Max-Cut on random geometric graphs (aka Feige-Schechtman graphs).
The Uniform Hard-Core Lemma Via Approximate Bregman Projections

with Boaz Barak and Satyen Kale. In SODA 2009

Versions: Preprint (pdf), Proceedings (DOI)

We give a simple and more efficient proof of the uniform hardcore lemma.
Rounding Parallel Repetitions of Unique Games

with Boaz Barak, Ishay Haviv, Anup Rao, Oded Regev and David Steurer. In FOCS 2008

Versions: Preprint (pdf), Proceedings (DOI)

We show an essentially tight connection between the semidefinite programming relaxation of Unique Games and their behavior under parallel repetition. Our results generalize and help to explain Raz's refutation of the Strong Parallel Repetition Conjecture. Indeed, we show that a Unique Game is a counterexample to strong parallel repetition whenever its SDP value is significantly larger than its integral value.
Asymptotically Optimal Hitting Sets Against Polynomials

with Markus Bläser and David Steurer. In ICALP 2008

Versions: Preprint (pdf), Proceedings (DOI)

We construct asymptotically optimal hitting sets (also called blackbox polynomial identity tests) for certain classes of polynomials.
Deterministically Testing Sparse Polynomial Identities of Unbounded Degree

with Markus Bläser, Richard Lipton and Nisheeth Vishnoi. In Inf. Proc. Lett.

Versions: Preprint (pdf), Journal (DOI)

We present two deterministic polynomial identity tests (one blackbox, one non-blackbox) for arithmetic circuits that represent sparse polynomials.

Some Links

I've been organizing Theory Lunch at Princeton.
The schedule is part of our Theory Calendar.
There is a Theory students reading group.
Subscribe for announcements (or see calendar above)
Some pictures

Moritz Hardt

Publications

Some Links

Coordinates:

Office:

Email:

Picture: