Previous Conferences & Workshops

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed...

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a graph G=(V,E) and a set of pairs of vertices (s_1,t_1), (s_2,t_2), ..., (s_k,t_k). The objective is to decide if all the pairs can be...

We have proposed that the glass transition is one example of a broader class of jamming transitions, where systems can develop extremely long stress relaxation times in disordered states as temperature is lowered, an applied shear stress is lowered...

The Glauber dynamics is a simple Markov chain algorithm for sampling from distributions that arise in models from statistical physics. In each step of this dynamics the value (or spin) of a random site is updated according to some rule which is...

The problem of average-case learning for decision trees is as follows: a decision tree T (over Boolean features x1,...,xn) is chosen at random from some natural distribution over decision trees. The learner is given access to uniform random examples...

In joint work with J. Viaclovsky, we studied the problem of prescribing symmetric functions of the eigenvalues of the Schouten tensor for a conformal metric on a compact manifold (often referred to as the "Sigma-k Yamabe problem"). This is...