## Sum of squares lower bounds for refuting any CSP

Pravesh Kothari

Member, School of Mathematics

December 13, 2016

Yve-Alain Bois

Pablo Picasso did not speak often about abstraction, but when he did, it was either to dismiss it as complacent decoration or to declare its very notion an oxymoron. The root of this hostility is to be found in the impasse that the artist reached in the summer 1910, when abstraction suddenly appeared as the logical development of his previous work, a possibility at which he recoiled in horror. But though he swore to never go again near abstraction, he could not prevent himself from testing his... Read more

Pravesh Kothari

Member, School of Mathematics

December 13, 2016

Nathaniel Bottman

Member, School of Mathematics

December 12, 2016

The Fukaya category of a symplectic manifold is a robust intersection theory of its Lagrangian submanifolds. Over the past decade, ideas emerging from Wehrheim--Woodward's theory of quilts have suggested a method for producing maps between the Fukaya categories of different symplectic manifolds. I have proposed that one should consider maps controlled by compactified moduli spaces of marked parallel lines in the plane, called "2-associahedra".

Ronen Eldan

Weizmann Institute of Science

December 12, 2016

The motivating question for this talk is: What does a sparse Erdős–Rényi random graph, conditioned to have twice the number of triangles than the expected number, typically look like? Motivated by this question, In 2014, Chatterjee and Dembo introduced a framework for obtaining Large Deviation Principles (LDP) for nonlinear functions of Bernoulli random variables (this followed an earlier work of Chatterjee-Varadhan which used limit graph theory to answer this question in the dense regime).

Dinakar Ramakrishnan

California Institute of Technology; Visitor, School of Mathematics

December 8, 2016

Of interest are (i) the conjecture of Bombieri (and Lang) that for any smooth projective surface $X$ of general type over a number field $k$, the set $X(k)$, of $k$-rational points is not Zariski dense, and (ii) the conjecture of Lang that $X(k)$, is even finite if in addition $X$ is hyperbolic, i.e., there is no non-constant holomorphic map from the complex line $C$ into $X(C)$. We can verify them for the Picard modular surfaces $X$ which are smooth toroidal compactifications of congruence quotients $Y$ of the unit ball in $\mathbb C^2$.

David Huse

Princeton University; Member, School of Natural Sciences

December 7, 2016

Eve C. Ostriker

Princeton University

December 6, 2016

Pravesh Kothari

Member, School of Mathematics

December 6, 2016

We show that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, we obtain sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT.

Bill Browder

Founder and Chief Executive Officer of Hermitage Capital Management

December 2, 2016

Bill Browder

World Disorder Lecture Series: Lawless Economy?

In this public lecture, Bill Browder, Founder and Chief Executive Officer of Hermitage Capital Management, will give a firsthand critical analysis of the Russian economy–—particularly the absence of the rule of law–—laden with insights derived from his personal experience.

World Disorder Lecture Series: Lawless Economy?

In this public lecture, Bill Browder, Founder and Chief Executive Officer of Hermitage Capital Management, will give a firsthand critical analysis of the Russian economy–—particularly the absence of the rule of law–—laden with insights derived from his personal experience.

Shubhangi Saraf

Rutgers University

December 5, 2016

Consider a set of $n$ points in $\mathbb R^d$. The classical theorem of Sylvester-Gallai says that, if the points are not all collinear then there must be a line through exactly two of the points. Let us call such a line an "ordinary line". In a recent result, Green and Tao were able to give optimal linear lower bounds (roughly $n/2$) on the number of ordinary lines determined $n$ non-collinear points in $\mathbb R^d$. In this talk we will consider the analog over the complex numbers.

Sheel Ganatra

Member, School of Mathematics

December 2, 2016

Noncommutative geometry, as advocated by Konstevich, proposes to replace the study of (commutative) varieties by the study of their (noncommutative) dg/A-infinity categories of perfect complexes. Conveniently, these techniques can then also be applied to Fukaya categories. In this mini-course, we will review some basic properties and structures in noncommutative geometry, with an emphasis on the notion of "smoothness" of a category and its appearance in topology and both sides of homological mirror symmetry.