Table of Contents

**Organizer:** Efficient computation

**Scope:** Readings in very recent results in data structures, exact algorithms and parameterized complexity, concerning communication complexity. We will read papers, and take turns presenting the material.

**Time and date:** We will meet Wednesdays or Thursdays, time 10.00-12.00, starting 03/03/2010. The length will be around some weeks, and the goal is to cover 4-5 articles plus to highlight some assessed knowledge in communication complexity. We will use varying ITU's meeting boxes (see schedule below).

**NEWS** The seminar is finished.

03/03/2010 - 10.00-12.00 - room: 4A05 - Thore Husfeldt: The Exponential Time Hypothesis and the Sparsification Lemma.

10/03/2010 - 10.00-12.00 - room: 4A05 - Thore Husfeldt: On the possibility of faster SAT algorithms.

17/03/2010 - 10.00-12.00 - room: 3A18 - Andrea Campagna: Towards polynomial lower bounds for dynamic problems.

07/04/2010 - 10.00-12.00 - room: 4A05 - Philip Bille: An introduction to communication complexity. (E. Kushilevitz, N. Nisan. Communication complexity.

14/04/2010 - 10.00-12.00 - room: 3A08 - Nina Taslaman: SAT and 3-party communication complexity; Rasmus Pagh: Data Structures and (Asymmetric) Communication Complexity.

28/04/2010 - 10.00-12.00 - room: 4A22 - Andrea Campagna: Towards polynomial lower bounds for dynamic problems: a non conditional proof; Rasmus Pagh: Asymmetric Communication Complexity.

- Rasmus Pagh
- Thore Husfeldt
- Nina Sofia Taslaman
- Natalie Elaine Schluter
- Andrea Campagna
- Philip Bille
- Inge Li Gørtz
- David Kofoed Wind
- Carsten Witt
- Morten Mølgaard
- Hjalte Wedel Vildhøj
- Søren Vind
- Mikkel Birkegaard Andersen
- Per Kristian Lehre

Please contact Andrea Campagna (acam [at] itu [dot] dk) to register as a participant.

M. Patrascu. Towards polynomial lower bounds for dynamic programming. **pdf **

M. Patrascu, R. Williams. On the possibility of faster SAT algorithms. **pdf **

E. Kushilevitz, N. Nisan. Communication complexity. **online **

R. Impagliazzo, R. Paturi, and F. Zane. Which Problems Have Strongly Exponential Complexity? **pdf **

I. Baran, E.D. Demaine and M. Patrascu. Subquadratic algorithms for 3SUM. **pdf **

Jeff Erickson “Non lecture Q” **pdf **

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson. On Data Structures and Asymmetric Communication Complexity **pdf**

Philip Bille, Anna Pagh, and Rasmus Pagh. Fast evaluation of union-intersection expressions **pdf**

**03/03/2010** - 10.00-12.00 - room: 4A05 - Thore Husfeldt: The Exponential Time Hypothesis and the Sparsification Lemma.

**Reference**:

* Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, “Which Problems Have Strongly Exponential Complexity?”, *Journal of Computer and System Sciences* 63, 512–530 (2001). Available at http://cseweb.ucsd.edu/~russell/ipz.pdf

* Jeffe Erickson “Non lecture Q” **pdf **

**Easy warmup**:

In an undirected graph with *n* vertices and *m* edges, a clique is a subgraph where each pair of vertices are neighbours. An independent set is a subgraph where no pairs of vertices are neighbours.

* Assume there’s an algorithm for finding a largest clique that runs in time *t*. Show by an easy reduction that there is algorithm for finding a largest independent set that runs in time *t* + *n*^{2}. (And vice versa, if you want. It’s “the same problem”.)

* Show that there’s an algorithm for finding a largest clique that runs in time exp(O(*n*)). (Thus, there’s one for finding a largest independent set as well.)

* Show that there’s an algorithm for finding a largest clique that runs in time exp(o(*m*)) (in fact,
exp(O(*m*^{1/2}))).

Apparent mystery: Can we find an independent set in time exp(o(*m*))?

**17/03/2010** - 10.00-12.00 - room: 3A18 - Andrea Campagna: Towards polynomial lower bounds for dynamic problems.

**Reference**:

**pdf**. Section 1.4 will not be covered.**pdf**. Not necessary for the session, but strictly related to the contents of previous reference.

**07/04/2010** - 10.00-12.00 - room: 4A05 - Philip Bille: An introduction to communication complexity. (E. Kushilevitz, N. Nisan. Communication complexity. **online ** – first chapter)

**14/04/2010** - 10.00-12.00 - room: 3A08 - Nina Taslaman: SAT and 3-party communication complexity PW10, sec. 4; Rasmus Pagh: Data Structures and (Asymmetric) Communication Complexity MNSW98, BPP07, sec. 4.

**28/04/2010** - 10.00-12.00 - room: 4A22 - Andrea Campagna: Towards polynomial lower bounds for dynamic problems: a non conditional proof section 1.4;
Rasmus Pagh: Asymmetric Communication Complexity MNSW98.