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.
The correct link to the paper by V.Kolmogorov and S.Zivny is:
ReplyDeletehttp://arxiv.org/abs/1110.2809