Monthly Archives: September 2011

Exponential Time Algorithms at SODA 2012

Accepted papers for the algorithms conference SODA 2012 are announced. Best conference ever! (Compare my SODA post from last year.)

Based on my quick perusal of list of accepted papers [PDF], here’s a list of papers related to exponential time computation, together with references to online version — I’m probably missing some. Updates are welcome.

  • Counting Perfect Matchings as Fast as Ryser [ 1107.4466], by Andreas Björklund
  • Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset, by Rajesh Chitnis, Mohammadtaghi Hajiaghayi and Dániel Marx
  • Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem [arxiv 1107.3704], by Stefan Kratsch
  • Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization [ECCC 2011-072], by Danny Hermelin and Xi Wu
  • Subexponential Parameterized Algorithm for Minimum Fill-in [arxiv 1104.2230] by Fedor V. Fomin and Yngve Villanger
  • A Satisfiability Algorithm for AC0 [arxiv 1107.3127], by Russel Impagliazzo, William Matthews and Ramamohan Paturi
  • Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal [arxiv 1107.3068] by Stefan Kratsch and Magnus Wahlström
  • Fast zeta transforms for point lattices, by Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof and Pekka Parviainen
  • Shortest Cycle Through Specified Elements [PDF], by Andreas Björklund, Thore Husfeldt and Nina Taslaman
  • Kernelization of Packing Problems, by Holger Dell and Dániel Marx
  • Linear Kernels for (Connected) Dominating Set on H-minor-free graphs [PDF], by Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos
  • Bidimensionality and Geometric Graphs [arxiv 1107.2221], by Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh

An amazing number of kernelisation (and, I presume non-kernelisation) papers. And lots and lots of exciting papers in many other fields as well.