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

Algorithms

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:
    http://arxiv.org/abs/1110.2809

    ReplyDelete