MSR/MIT Theory Reading Group

Locally-correctable codes (LCCs) and locally-testable codes (LTCs) are special families of error-correcting codes that admit extremely efficient, i.e., sub-linear time, algorithms for error correction and detection, respectively, while making a few queries to the received word.

Abstract: 

We establish the random k-SAT threshold conjecture for all k exceeding an absolute constant k(0).

Over the past three decades, communication complexity had a profound impact on nearly every field of theoretical computer science, and constitutes one of the few known methods for proving unconditional lower bounds.

The Unique Games Conjecture of Khot is the basis of remarkable inapproximability results.  In recent years, researchers have explored possible algorithms for refuting it based on the Lasserre (aka Sum of Squares) hierarchy of semidefinite programs.

Matching problems in Economics, frequently differ from traditional matching problems in that the matching with desired properties one seeks is not the solution to linear optimization problem defined over the set of feasible matchings. The difference arises from the role of preferences.

Error correcting codes have transformed the way we transfer information. In particular, they give computationally efficient ways to protect one-way communications against noise by adding minimal amounts of redundancy.

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,{P} otsubseteq mathbb{NC_1}$ ).

The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps.

I will start with an overview of the basic phase transition and concentration results for random k-SAT, and discuss more recent results for planted k-SAT.

Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace's equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics.

We give two new characterizations of (F_2-linear, smooth) locally testable error-correcting codes in terms of Cayley graphs over (F_2)^h

It is an elementary fact that every (unbounded fan-in) depth-d circuit of size S is equivalent to a depth-d formula of size at most S^d.

This talk will discuss sparse Johnson-Lindenstrauss transforms, i.e. sparse linear maps into much lower dimension which preserve the Euclidean geometry of a set of vectors. Applications to certain domains will also be presented, such as to numerical linear algebra.