Reading seminar in communication complexity and related problems, Spring 2010

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.

Schedule

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.

Participants

  • 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.

Papers and references

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

Previous lectures

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 + n2. (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(m1/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:

  1. pdf. Section 1.4 will not be covered.
  2. 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.

 
comcom.txt · Last modified: 2010/06/08 15:23 by acam
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki