Saturday, September 17, 2011

SODA 2012 papers on Arxiv

Here are the Soda papers that have an Arxiv version - not quite one third of them. I probably missed a few (searched for the exact title, and got a few syntax errors in my search); will complete the list if people send me corrections. This is part of my desire to make conferences less important in our field. One of their purposes used to be fast dissemination of new research, but now that purpose may be served better, faster, and more cheaply by Arxiv.

Sublinear Time, Measurement-Optimal, Sparse Recovery For All

Ely Porat and Martin Strauss

Counting Perfect Matchings as Fast as Ryser

Andreas Björklund

A Proof of the Boyd-Carr Conjecture

Frans Schalekamp, David Williamson and Anke Van Zuylen

Approximate Counting via Correlation Decay in Spin Systems

Liang Li, Pinyan Lu and Yitong Yin

Physarum Can Compute Shortest Paths

Vincenzo Bonifaci, Kurt Mehlhorn and Girish Varma

Metastability of Logit Dynamics for Coordination Games

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale and Giuseppe Persiano

The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash
Bargaining Game

Vijay Vazirani

Submodular Functions are Noise Stable

Homin Lee, Pravesh Kothari, Adam Klivans and Mahdi Cheraghchi

A Linear Time Algorithm for Seeds Computation

Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen

The condensation transition in random hypergraph 2-coloring

Amin Coja-Oghlan and Lenka Zdeborova

Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts

Anne Driemel and Sariel Har-Peled

Subexponential Parameterized Algorithm for Minimum Fill-in

Fedor V. Fomin and Yngve Villanger

The Set of Solutions of Random XORSAT Formulae

Yashodhan Kanoria, Andrea Montanari, Morteza Ibrahimi and Matt Kraning

Sparser Johnson-Lindenstrauss Transforms

Daniel Kane and Jelani Nelson

Random Walks, Electric Networks and The Transience Class problem of Sandpiles

Ayush Choure and Sundar Vishwanathan

Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

Stefan Kratsch and Magnus Wahlström

Approximate Tree Decompositions of Planar Graphs in Linear Time

Frank Kammer and Torsten Tholey

Computing all maps into a sphere

Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek and Uli Wagner

Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

Josef Cibulka and Jan Kyncl

Partial match queries in random quadtrees

Nicolas Broutin, Ralph Neininger and Henning Sulzbach

Mechanism Designs via Consensus Estimate and Cross-Check

Bach Ha and Jason Hartline

Packing anchored rectangles

Adrian Dumitrescu and Csaba Toth

Directed Nowhere Dense Classes of Graphs

Stephan Kreutzer and Siamak Tazari

The Entropy Rounding Method in Approximation Algorithms

Thomas Rothvoss

Confluent Persistence Revisited

Sebastien Collette, John Iacono and Stefan Langerman

Using Hashing to Solve the Dictionary Problem \\(In External Memory)

John Iacono and Mihai Patrascu

Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson and Eli Upfal

The complexity of conservative valued CSPs

Vladimir Kolmogorov and Stanislav Zivny

Linear Index Coding via Semidefinite Programming

Eden Chlamtac and Ishay Haviv

A simple algorithm for random colouring G(n, d/n) using (2+\epsilon)d colours

Charilaos Efthymiou

Optimal Column-Based Low-Rank Matrix Reconstruction

Venkatesan Guruswami and Ali Sinop

Private Data Release Via Learning Thresholds

Moritz Hardt, Guy Rothblum and Rocco Servedio

Computing distance between piecewise linear bivariate functions

Boris Aronov and Guillaume Moroz

Matroidal Degree-Bounded Minimum Spanning Trees

Rico Zenklusen

Deterministic Construction of l-type Ellipsoids and its Application to Derandomizing Lattice


Daniel Dadush and Santosh Vempala

Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation

Michael Goodrich, Michael Mitzenmacher, Olga Ohrimenko and Roberto Tamassia

Dimension reduction for finite trees in l_1

James Lee, Arnaud De Mesmay and Mohammad Moharrami

Expanders are Universal for the Class of all Spanning Trees

Daniel Johannsen, Michael Krivelevich and Wojciech Samotij

Stochastic coalescence in logarithmic time

Po-Shen Loh and Eyal Lubetzky

Bidimensionality and Geometric Graphs

Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh.

Testing Odd-Cycle-Freeness in Boolean Functions

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, and Asaf Shapira.

1 comment:

  1. The correct link to the paper by V.Kolmogorov and S.Zivny is: