Teaching

Reading Group Algorithms (WS 2011/12)

Kurt Mehlhorn and Carola Winzen

Time:

Thursdays, 16:15 - 17:45

First meeting:

First week of WS 2011/12, i.e., Thursday, October 20.

Room:

024 on the ground floor in the MPI building (E1.4).

Prerequisites:

Knowledge of algorithms and data structures. The target audience of this reading group are master students, PhD students as weel as postdocs.

Content:

We will read (more or less) recent papers in theoretical computer science. The paper may be less recent only if there is interesting follow-up work. In the first 45 minutes, we will have short presentations of one or two different papers. In the second 45 minutes, we have a regular presentation (40 minutes + 5 minutes discussion) of one paper. The reading group is open for all interested students and postdocs. Students aiming to get credits give a regular talk and write a short summary about the paper.

Credits:

You earn the usual 7 credit points for a seminar if you (i) give a regular presentation of the paper given to you, and (ii) write a short summary (about 5 pages). The summary should be handed in within the first four weeks after the end of the semester. The presentation needs to be discussed with us at least one week before your scheduled talk in the reading group.

If you want credit for the course, please register with Carola by sending her a short mail.

Schedule:

Date	Speaker	Topic	Reference
20.10.	Kurt and Carola	Introduction to the Reading Group and Schedule	[20.10. 1]
	Carola Winzen	Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity	[20.10. 2]
27.10.	Kurt Mehlhorn	Solving sparse symmetric diagonally dominant linear systems	[27.10. 1], [27.10. 2], [27.10. 3]
3.11.	Danny Hermelin	Kernelization Lower Bounds
	Shay Moran	A puzzle I will talk about next week
10.11.	Shay Moran	A set theoretical formulation of "almost everywhere"
	Konstantinos Panagiotou	Hunting the Random k-sat Threshold	[10.11. 1]
17.11.	Cosmina Croitoru	Argumentation Frameworks	[17.11. 1]
	Ruben Becker	Analysis of Agglomerative Clustering	[17.11. 2]
24.11.	Xavier Pérez Giménez	Graphs with Average Degree Smaller than 30/11 are burning slowly	[24.11. 1]
	Rom Pinchasi	On some principles of plane geometry	[24.11. 2]
1.12.	Bernhard Schommer	SAT Modulo Theory	[1.12.]
8.12.	Nabil Mustafa	The Multiplicative Weights Technique in Discrete Geometry	[8.12. 1]
15.12.	Fahimeh Ramezani	Black-Box Randomized Reductions in Algorithmic Mechanism Design	[15.12. 1]
	Svilen Dimitrov	Private Circuits: Securing Hardware against Probing Attacks	[15.12. 2]
22.12.		No reading group. Happy holidays!

12.1.	Alexey Pospelov	Small Private Circuits	[12.1. 1]
19.1.	Yash Raj Shrestha	Linear Problem Kernels for Planar Graph Problems with Small Distance Property	[19.1. 1]
	Marvin Künnemann	On independent sets in random graphs	[19.1. 2]
26.1.	Igor Stassiy	Noisy interpolation of sparse polynomials, and applications	[26.1. 1]
2.2.	Kaloyan Rusev	The Mastermind Game and Variants	[2.2. 1]
	Krishna Narasimhan	Discrepancy Minimization	[2.2. 2], [2.2. 3]
9.2.	Manish Kumar Narang	An improved LP-based approximation for steiner tree	[9.2. 1]
	Yury Bakkanouski	Sustaining the Internet with Hyperbolic Mapping	[9.2. 2]

References:

[20.10. 1] Schedule of last reading group in Algorithms (SS 2011)
[20.10. 2] "Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity" by Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein.
[27.10. 1] "Graph Sparsification by Effective Resistances" by Daniel Spielman and Nikhil Srivastava.
[27.10. 2] "Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems" by Daniel Spielman and Shang-Hua Teng.
[27.10. 3] "A nearly-mlogn time solver for SDD linear systems" by Ioannis Koutis, Gary Miller, and Richard Peng. To appear in FOCS 2011.
[10.11. 1] "Catching the k-NAESAT Threshold" by Amin Coja-Oghlan and Konstantinos Panagiotou.
[17.11. 1] "Weighted argument systems: Basic definitions, algorithms, and complexity results" by Paul E. Dunne, Anthony Hunter, Peter McBurney, Simon Parsons, and Michael Wooldridge.
[17.11. 2] [Carola Winzen] "Analysis of Agglomerative Clustering" by Marcel R. Ackermann, Johannes Blömer, Daniel Kuntze, and Christian Sohler.
[24.11. 1] "Graphs with Average Degree Smaller than 30/11 are burning slowly" by Pawel Pralat.
[24.11. 2] Abstract:
We will present the principle of duality between points and lines in the plane and also Euler's polyhedral formula in the plane. We will demonstrate the use of combination of the two principles by solving a long standing open problem of Erdos, Purdy and Strauss. They conjectured in 1977 the following statement: The minimum number of distinct areas of triangles determined by any set of n noncollinear points in the plane is ⌊ n/2 ⌋. This bound is best possible.
[1.12.] [Kurt Mehlhorn]
SAT Modulo Theory is a generalization of the satisfiability problem. As in the classical sat problem, we are given a Boolean formula. However, the variables are replaced by predicates in some theory, e.g., the variables are replaced by linear inequalities over real valued variables. The question is whether one can assign values to the real variables such that the resulting formula is true.

For example, (a < 2) and (a > 1) is satisfiable. But (a < 2) and (a > 3) is not.

SAT Modulo Theory has widespread applications; even more than SAT; see http://en.wikipedia.org/wiki/Satisfiability_Modulo_Theories for an introduction. Kurt is interested in SAT where the predicates are polynomial inequalities. This version comes up in verification of real time systems.

"Solving SAT and SAT Modulo Theories: From an Abstract Davis-Putnam-Logemann-Loveland Procedure to DPLL(T)" by R. Nieuwenhuis, A. Oliveras, and C. Tinelli is the seminal paper on SAT-Modulo-Theory. In a nutshell the algorithms work as follows.

A classical SAT-solver is run. This SAT-solver asks questions to the underlying theory, namely whether a conjunction of predicates is satisfiable. If the predicates are linear inequalities, this subproblem can be solved by a linear programming solver. Many such questions are asked and usually the answer will be NO. So one needs a fast algorithm to refute unsatisfiable conjunctions. This is not what linear programming solvers are optimized for.

The paper "Minimizing Polynomial Functions" by P. A. Parrilo and B. Sturmfels might lead to a fast refutation method for conjunctions of polynomial inequalities.

This belief is based on discussions with Fritz Eisenbrand.
[8.12. 1] [Nabil Mustafa] Abstract:
I will explain a simple broad technique for converting claims of one type to a different dual-like set of claims. This technique was used to prove three classical results in discrete geometry, which I will present: spanning trees with low stabbing number, approximation algorithm for geometric set-cover, and the simplicial partition theorem.
[15.12. 1] [Khaled Elbassioni] "Black-Box Randomized Reductions in Algorithmic Mechanism Design" by Shaddin Dughmi and Tim Roughgarden.
[15.12. 2] [Alexey Pospelov] "Private Circuits: Securing Hardware against Probing Attacks" by Yuval Ishai, Amit Sahai, David Wagner.
[12.1. 1] [Alexey Pospelov] "Small Private Circuits" by Markus Bläser, Jean-Sébastien Coron, and Alexey Pospelov.
[19.1. 1] [Marek Kosta] "Linear Problem Kernels for Planar Graph Problems with Small Distance Property" by Jianxin Wang, Yongjie Yang, Jiong Guo, and Jianer Chen.
[19.1. 2] [Reto Spöhel] "On independent sets in random graphs" by Amin Coja-Oghlan and Charilaos Efthymiou.
[26.1. 1] [Chandan Saha] "Noisy interpolation of sparse polynomials, and applications" by Shubhangi Saraf and Sergey Yekhanin.
[2.2. 1] [Carola Winzen] "Mastermind" by Vašek Chvátal.
[2.2. 2] [Khaled Elbassioni] "Constructive Algorithms for Discrepancy Minimization" by Nikhil Bansal.
[2.2. 3] [Khaled Elbassioni] "Deterministic Discrepancy Minimization" by Nikhil Bansal and Joel Spencer.
[9.2. 1] [Khaled Elbassioni] "An improved LP-based approximation for steiner tree" by Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità.
[9.2. 2] [Konstantinos Panagiotou] "Sustaining the Internet with Hyperbolic Mapping" by M. Boguna, F. Papadopoulos, and D. Krioukov.

Papers:

A list of papers which are still available for presentation in the reading group follows. We may add more papers. If you are interested in presenting a paper that is not from this list, please let us know well in advance so we can check appropriateness. If you are interested in presenting one of these papers, please write us a short mail or come to our office. The names in brackets indicate who suggested the respective paper. In most cases, he/she will be the supervisor of your presentation. However, please check with us first as your talk might also be supervised by a different person.