Hard Theorems

'Cause when the proof gets tough… the tough get provin' (…proof complexity lower bounds!)

Sums-of-squares integer programming relaxation: Lecture 6

Lecture 6: Max-Cut approximation as a Lasserre rounding.

Scribe: Marc Vinyals


We show how to give a good approximation for the max-cut problem using only low levels of the Lasserre hierarchy. This implies a separation between Sherali-Adams and Lasserre hierarchies. Additionally we introduce basic Fourier analysis in the boolean setting.

Link: [Lecture notes 06]

Sums-of-squares integer programming relaxation: Lecture 5

Lecture 5: Properties of the Lasserre Relaxation.

Scribe: Sangxia Huang


In this lecture, we study the properties of the solution vectors of the Lasserre relaxation. We start with some basic properties of the solutions, and then continue to show that the solution vectors give us a family of locally consistent distributions over feasible integral local solutions. At the end of the lecture, we see an example of this property in graph coloring.

Link: [Lecture notes 05]

Sums-of-squares integer programming relaxation: Lecture 4

Lecture 4: Semidefinite program relaxations of integer programs.

Scribe: Mariette Annergren


We continue the discussion on how to improve the initial relaxation made of an integer program. Here, we focus on semidefinite program (SDP) relaxations, and we introduce Lovász-Schrijver relaxation with semidefinite programming, and the Positivstellensatz, Positivstellensatz Calculus and sums-of-squares (SOS) proof systems.

Link: [Lecture notes 04]

The call for paper of MFCS 2015 is out!

The deadline is on April 22, 2015.

From the webpage http://mfcs2015.di.unimi.it/

The series of MFCS symposia, organized since 1972, has a long and well-established tradition. The MFCS symposia encourage high-quality research in all branches of theoretical computer science. Their broad scope provides an opportunity to bring together researchers who do not usually meet at specialized conferences. Quality papers presenting original research on theoretical aspects of computer science are solicited.

CCC 2015 accepted papers.

There will be a great Proof Complexity session at CCC2015.

  • Non-commutative formulas and Frege lower bounds: a new characterization of propositional proofs. Fu Li (Tsinghua University), Iddo Tzameret (Royal Holloway, University of London), Zhengyu Wang (Harvard University)
  • The space complexity of cutting planes refutations. Nicola Galesi (Sapienza University of Rome), Pavel Pudlák (Czech Academy of Sciences), Neil Thapen (Czech Academy of Sciences)
  • The functional pigeonhole principle requires polynomial calculus proofs of exponential size. Mladen Miksa (KTH Royal Institute of Technology), Jakob Nordstrom (KTH Royal Institute of Technology)
  • Tight size-degree lower bounds for sums-of-squares proofs. Massimo Lauria (KTH Royal Institute of Technology) Jakob Nordström (KTH Royal Institute of Technology)

See you all in Portland. If you come for STOC, no reason to miss CCC 2015!

CCC 2015 accepted papers.

Sums-of-squares integer programming relaxation: Lecture 3

Lecture 3: Improving linear relaxations of integer programs.

Scribe: Mariette Annergren


We discuss methods to improve the linear relaxations of integer programs.

They are systematic ways to find tighter and tighter polytopes containing the convex hull of the integer solutions. The main idea is to lift, that is, to augment the linear program to a higher dimensional space and then to project it down to the original space to obtain a polytope that is smaller than the one we started with. We shall see two different ways to do lift and project: namely the Lovász-Schrijver and Sherali-Adams hierarchies.

Link: [Lecture notes 03]

Highlight inverse search in Emacs + AUCTeX

I always lose track of the cursor when I use inverse search on LaTeX documents. This small hack will mitigate the pain.

One cool addition to Emacs, if you write papers using LaTeX1, is the powerful AUCTeX software. Among tons of useful features it gives the possibility to jump from any point in your LaTeX code to the corresponding point in the PDF document (this is called “forward search” in the lingo). If you have a proper PDF viewer (e.g. Evince on Linux or Skim on MacOSX) the target location will be highlighted.


But what about the opposite? If your setup is correct it is possible to click on the preview document, and Emacs will jump to the corresponding point in the appropriate LaTeX file.

If you are like me, you like low contrast themes a big Emacs windows (frames in Emacs parlance), so it is easy to lose track of the cursor, which can end up anywhere. With the following piece of code every time you use inverse search, the target location in the LaTex file will be highlighted as well.

(defadvice TeX-source-correlate-sync-source (after ad-TeX-correlate-center)
    "Center and highlight point after AUCTeX inverse-search."
    (pulse-momentary-highlight-one-line (point)))

Here’s the result.


This is of course useless if you use global-hl-line-mode, but I find quite annoying. The actual highlight style is due to the pulse.el package (included in recents GNU/Emacs versions).



which you should do, whatever some misinformed researchers say. At least if you are in Math, CS or Physics.

Sums-of-squares integer programming relaxation: Lecture 2

Lecture 2: Semidefinite programming and relaxations.

Scribe: Massimo Lauria


Semidefinite programs are a valuable tools in approximation algorithms and in combinatorial optimization, since semidefinite relaxations are usually stronger than linear ones. In this lecture we describe what is a semidefinite program.

Link: [Lecture notes 02]

Sums-of-squares integer programming relaxation: Lecture 1

Lecture 1: Linear relaxations of integer programs.

Scribe: Massimo Lauria


We can express combinatorial problems using integer programs and, since we can’t solve them, we consider relaxed programs in which integer constraints are relaxed to linear ones. Then we round fractional solutions to integer. We consider hierarchies of linear programs and discuss the quality of the corresponding solutions.}

Link: [Lecture notes 01]

Sums-of-squares integer programming relaxation (winter 2014)

In the warm winter of 2014, I gave a course on the Sums-of-squares integer programming relaxations. The course had the usual “teach it to learn it” attitude that students often have to endure, but it was very useful to get up to speed with Sums-of-squares the PhD students of the proof complexity group at KTH. Furthermore I have been blessed by guest lectures from Per Austrin, Johan Håstad and David Steurer.

Course URL: http://www.csc.kth.se/~lauria/sos14/

I will slowly upload the lecture notes here as I review them, but you can find them already in the course webpage.

Description of the course

Most combinatorial optimization problems have a natural formulation as integer linear programs. Unfortunately it is hard to solve such programs, so we settle for less: we look for a fractional solution and then we round it to an integer one. This process usually gives a solution which is far from optimal.

Mathematicians and computer scientists have developed ways to improve the quality of solutions: they introduce new constraints that are valid for all integer solutions, but may exclude some fractional ones.

This process is formalized by the sum of squares inference system, which is a way to deduce such new constraints. This is the strongest system known in current literature and subsumes many successful techniques in approximation.

In the course we will discuss sums-of-squares system, some of its subsystems, and the performance of certain systematic ways to produce the new constraints: for some problems we can get good approximation algorithms, while for others the systematic approach is too expensive. In particular we will focus on rank lower bounds, which give a way to measure how hard a problem is for sums-of-squares.

The course is made of two parts:

I. In the first part we introduce sum of squares and its many subsystems. It is important to spend some time on the subsystems because most lower bounds in literature are for them. We will also briefly introduce semidefinite positive programming and semidefinite positive relaxations.

II. In the second part of the course we will study rank for optimization problems like 3-SAT, 3-XOR, Knapsack, Planted Clique, Densest k-subgraph.


Get every new post delivered to your Inbox.

Join 748 other followers