The Center for the Theory of Interactive Computation (CTIC,
http://ctic.au.dk/ ) and Center for Massive Data Algorithmics (MADALGO,
http://madalgo.au.dk) announce the workshop "Synergies in Lower Bounds",
to be held at Aarhus University, Denmark, on June 28 to July 1, 2011.
Workshop webpage:
http://ctic.au.dk/events/workshop-synergies-in-lower-bounds/
Synergies in Lower Bounds brings together researchers from multiple
areas of theoretical computer science (complexity, cryptography,
algorithms) whose specialty is proving impossibility results: rigorously
proving that certain tasks cannot be done efficiently, a.k.a. "lower
bounds". There is much in common between impossibility results in
algorithms, complexity, and cryptography, and the goal of the workshop
is to expose these connections, transfer lower-bound techniques between
areas, and explore the boundaries of proving impossibility: What can be
proved impossible? What seems too difficult to prove right now? Which
directions spell new progress? Which areas or problems have not yet
received enough attention by lower bounds experts?
The focus is on unconditional or "information-theoretic" lower bounds.
Workshop topics will include: Communication complexity, circuit
complexity, data structures, streaming algorithms, property testing,
cryptography, and information theory.
The lectures include introductory tutorial-style lectures, as well as
shorter research contributions, and ample time for discussion.
Speakers include: Alex Andoni, Mark Braverman, Joshua Brody, Amit
Chakrabarti, Ivan Damgård, Kristoffer Arnsfelt Hansen, Michal Koucký,
Robert Krauthgamer, Kasper Green Larsen, Shachar Lovett, Kevin
Matulef, Jesper Buus Nielsen, Mihai Patrascu, Rina Panigrahy, Periklis
A. Papakonstantinou, Jaikumar Radhakrishnan, Anup Rao, Elad Verbin, and
Qin Zhang.
Scientific Organizers: Joshua Brody, Kristoffer Arnsfelt Hansen, Elad
Verbin.
General Chair: Peter Bro Miltersen.
The workshop is open to interested participants. For further information
and registration (deadline June 1st), see:
http://ctic.au.dk/events/workshop-synergies-in-lower-bounds/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
