- SODA 2009 Invited speakers
- SODA 2009 Accepted papers, without abstracts (by order of submission)
- SODA 2009 Accepted papers, with abstracts (by order of submission)

- Michael I. Jordan, University of California at Berkeley
- Yuval Peres, Microsoft Research
- Volker Strassen, University of Konstanz, Germany

- Jeff Edmonds and Kirk Pruhs.
**Scalably Scheduling Processes with Arbitrary Speedup Curves** - Zdenek Dvorak, Ken-ichi Kawarabayashi and Robin Thomas.
**Three-coloring triangle-free planar graphs in linear time** - Amin Coja-Oghlan, Colin Cooper and Alan Frieze.
**An Efficient Sparse Regularity Concept** - Toniann Pitassi and Nathan Segerlind.
**Exponential Lower Bounds and Integrality Gaps for Lovasz-Schrijver Procedures** - Uriel Feige and Noga Alon.
**On the power of two, three and four probes** - Siu-Wing Cheng and Man-Kwun Chiu.
**Dimension detection via slivers** - Ioannis
Caragiannis, Jason Covey, Michal Feldman, Christopher Homan, Christos
Kaklamanis, Nikos Karanikolas, Ariel Procaccia and Jeffrey Rosenschein.
**On the Approximability of Dodgson and Young Elections** - David Eppstein and Elena Mumford.
**Self-overlapping Curves Revisited** - Jiri Matousek, Martin Tancer and Uli Wagner.
**Hardness of embedding simplicial complexes in R^d** - MohammadTaghi Hajiaghayi and Mohammad H. Bateni.
**The Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location** - Sudipto Guha, Kamesh Munagala and Peng Shi.
**Approximation Algorithms for Restless Bandit Problems** - Vida Dujmovic, John Howat and Pat Morin.
**Biased Range Trees** - Zeev Nutov.
**An almost O(log k)-approximation for k-connected subgraphs** - David Eppstein, Michael Goodrich and Darren Strash.
**Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings** - Moran Feldman, Guy Kortsarz and Zeev Nutov.
**Improved Approximating Algorithms for Directed Steiner Forest** - Haim Kaplan, Natan Rubin and Micha Sharir.
**Line Transversals of Convex Polyhedra in S^3** - Mikkel Thorup.
**String Hashing for Linear Probing** - Anthony Man-Cho So.
**Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints** - Ken-ichi Kawarabayashi and Yusuke Kobayashi.
**Algorithms for Finding an Induced Cycle in Planar Graphs** - Stephan Thomasse.
**A quadratic kernel for feedback vertex set** - Martin Dietzfelbinger and Ulf Schellbach.
**On risks of using cuckoo hashing with simple universal hash classes** - Michael Molloy and Bruce Reed.
**Asymptotically optimal frugal colouring** - Omid Amini, Louis Esperet and Jan van den Heuvel.
**A Unified Approach to Distance-Two Colouring of Planar Graphs** - Nikhil Bansal and Ho-Leung Chan.
**Weighted flow time does not admit O(1)-competitive algorithms** - Paolo Ferragina, Igor Nitto and Rossano Venturini.
**On the bit-complexity of Lempel-Ziv compression** - Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio.
**Testing Halfspaces** - Ke Yi and Qin Zhang.
**Multi-Dimensional Online Tracking** - Krishnendu Chatterjee, Luca de Alfaro and Thomas Henzinger.
**Termination Criteria for Solving Concurrent Safety and Reachability Games** - Philip Klein, Shay Mozes and Oren Weimann.
**Shortest Paths in Directed Planar Graphs with Negative Lengths: a linear-space O(n log^2 n)-time algorithm** - Ioannis Caragiannis.
**Efficient coordination mechanisms for unrelated machine scheduling** - Daniel Marx.
**Approximating fractional hypertree width** - Bodo Manthey and Heiko Roeglin.
**Improved Smoothed Analysis of the k-Means Method** - Christos Boutsidis, Michael Mahoney and Petros Drineas.
**An Improved Approximation Algorithm for the Column Subset Selection Problem** - Michael Drmota and Wojciech Szpankowski.
**(Un)Expected Behavior of Digital Search Tree Profile** - Nikhil Bansal, Zachary Friggstad, Rohit Khandekar and Mohammad Salavatipour.
**A logarithmic approximation for the unsplittable flow on line graphs** - Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup.
**Variance-optimal sampling-based estimation of subset sums** - Sergio Cabello.
**Finding shortest contractible cycles in embedded graphs** - Khaled Elbassioni, Rajiv Raman, Saurabh Ray and Rene Sitters.
**On the approximability of the maximum feasible subsystem problem with 0/1-coefficients** - S. Charles Brubaker.
**Clustering on Noisy Mixtures** - Ashish Goel, Michael Kapralov and Sanjeev Khanna.
**Perfect matchings via uniform sampling in regular bipartite graphs** - David Karger and Debmalya Panigrahi.
**An tilde{O}(m) algorithm for constructing a cactus of an undirected graph** - Joel Tropp.
**Efficient Algorithms for Column Subset Selection** - Gabriel Nivasch.
**Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations** - Raphael Yuster.
**Efficient algorithms on sets of permutations, dominance, and real-weighted APSP** - Gabor Tardos and Ehsan Amiri.
**High rate fingerprinting codes and the fi ngerprinting capacity** - Yury Person and Mathias Schacht.
**Almost all hypergraphs without Fano planes are bipartite** - Amr Elmasry.
**Pairing Heaps with O(loglog n}) decrease Cost** - Haim Kaplan and Uri Zwick.
**A simpler implementation and analysis of Chazelle's Soft Heaps** - Mikkel Thorup, Uri Zwick and Omid Madani.
**Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths** - Alon Shalita and Uri Zwick.
**Efficient algorithms for the 2-gathering problem** - david cohen-steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov.
**Persistent Homology for Kernels, Images, and Cokernels** - Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh.
**Clique-width: On the Price of Generality** - Parinya Chalermsook and Julia Chuzhoy.
**Maximum Independent Set of Rectangles** - Brendan Nagle, Annika Poerschke, Vojtech Rödl and Mathias Schacht.
**On Algorithmic Hypergraph Regularity** - Robi Krauthgamer, Seffi Naor and Roy Schwartz.
**Partitioning Graphs into Balanced Components** - Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs.
**Speed Scaling with an Arbitrary Power Function** - Zdenek Dvorak, Daniel Kral and Robin Thomas.
**Coloring triangle-free graphs on surfaces** - Amitabh Basu, Pierre Bonami, gerard cornuejols and Francois Margot.
**On the Relative Strength of Split, Triangle and Quadrilateral Cuts (Extended Abstract)** - Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild.
**From coding theory to efficient pattern matching** - Ramesh Hariharan and Anand Bhalgat.
**Fast Edge Orientation for Unweighted Graphs** - Viswanath Nagarajan and Maxim Sviridenko.
**On the Maximum Quadratic Assignment Problem** - Bernard Chazelle.
**Natural Algorithms** - Timothy M. Chan.
**Comparison-Based, Time-Space Lower Bounds for Selection** - Peyman Afshani and Timothy M. Chan.
**Optimal Halfspace Range Reporting in Three Dimensions** - Justin Salez and Devavrat Shah.
**Optimality of Belief Propagation for Random Assignment Problem** - Ping Li.
**Compressed Counting** - Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu.
**The Geometry of Binary Search Trees** - Satoru Iwata and James Orlin.
**A Simple Combinatorial Algorithm for Submodular Function Minimization** - Prasad Raghavendra and David Steurer.
**Towards Computing the Grothendieck Constant** - Mordecai J. Golin, Xiaoming Xu and Jiajin Yu.
**A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding** - Ken-ichi Kawarabayashi, Erik Demaine and Mohammad Taghi Haijaghayi.
**Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs** - Ken-ichi Kawarabayashi and Bruce Reed.
**A Nearly Linear Time Algorithm For The Half Integral Parity Disjoint Paths Packing Problem** - Michel Goemans, Nicholas J.A. Harvey, Satoru Iwata and Vahab Mirrokni.
**Approximating Submodular Functions Everywhere** - Baharak Rastegari, Anne Condon and Kevin Leyton-Brown.
**Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity** - Ilia Binder and Mark Braverman.
**The complexity of simulating Brownian Motion** - Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari and Pat Morin.
**Succinct Geometric Indexes Supporting Point Location Queries** - Djamal Belazzougui, Paolo Boldi, Rasmus Pagh and Sebastiano Vigna.
**Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses** - Alexandr Andoni, Piotr Indyk, Robi Krauthgamer and Huy Nguyen.
**Approximate Nearest Neighbors for Affine Subspaces Queries** - Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, ?ukasz Je? and Grzegorz Stachowiak.
**Collecting Weighted Items from a Dynamic Queue** - Boaz Barak, Moritz Hardt and Satyen Kale.
**The Uniform Hardcore Lemma via Approximate Bregman Projections** - Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff.
**Transitive-Closure Spanners** - Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant.
**On the Complexity of Nash Equilibria of Action-Graph Games** - Alexandr Andoni, Piotr Indyk and Robi Krauthgamer.
**Overcoming the L_1 Non-Embeddability Barrier: Algorithms for Product Metrics** - Parikshit Gopalan and Jaikumar Radhakrishnan.
**Finding repeats in a data-stream** - James Aspnes and Keren Censor.
**Approximate Shared-Memory Counting Despite a Strong Adversary** - Ittai Abraham, Yair Bartal and Ofer Neiman.
**On Low Dimensional Local Embeddings** - Michael Bender, Jeremy Fineman and Seth Gilbert.
**Online Topological Ordering** - William Johnson and Assaf Naor.
**The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite** - Klaus Jansen.
**Parameterized approximation scheme for the multiple knapsack problem** - Markus Chimani, Carsten Gutwenger, Petra Mutzel and Christian Wolf.
**Inserting a Vertex into a Planar Graph** - Spyros Angelopoulos and Pascal Schweitzer.
**Paging and List Update under Bijective Analysis** - Adrian Dumitrescu, Csaba Toth and G Xu.
**On stars and Steiner stars. II** - Benjamin Aminof, Orna Kupferman and Robby Lampert.
**Reasoning about Online Algorithms with Weighted Automata** - Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich and Dan Vilenchik.
**On smoothed k-CNF formulas and the Walksat algorithm** - Elad Hazan and Robi Krauthgamer.
**How hard is it to approximate the best Nash equilibrium?** - Ashish Goel, Sanjeev Khanna and Brad Null.
**The Ratio Index for Budgeted Learning, with Applications** - Serge Gaspers and Gregory Sorkin.
**A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between** - Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos.
**Decomposition of Multiple Coverings into More Parts** - Edith Elkind and Dmitrii Pasechnik.
**Computing the nucleolus of weighted voting games** - Konstantinos Panagiotou and Angelika Steger.
**Maximum Biconnected Subgraphs of Random Planar Graphs** - Ken-ichi Kawarabayashi and Bojan Mohar.
**List-Color-Critical Graphs on a Fixed Surface** - Ariel Kulik, Hadas Shachnai and Tami Tamir.
**Maximizing Submodular Set Functions Subject to Multiple Linear Constraints** - Marcel R. Ackermann and Johannes Blömer.
**Coresets and Approximate Clustering for Bregman Divergences** - Benjamin Moseley and Chandra Chekuri.
**Online Scheduling to Minimize the Maximum Delay Factor** - Maria-Florina Balcan, Avrim Blum and Anupam Gupta.
**Approximate Clustering without the Approximation** - Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica and Kunal Talwar.
**Secretary Problems: Weights and Discounts** - Maria-Florina Balcan, Avrim Blum and Yishay Mansour.
**Improved Equilibria via Public Service Advertising** - Yusu Wang, Kevin Buchin and Maike Buchin.
**Exact Algorithm for Partial Curve Matching via the Frechet Distance** - Pankaj K Agarwal, R Sharathkumar and Hai Yu.
**Approximate Euclidean Shortest Path amid convex obstacles** - Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin.
**Sorting and Selection in Posets** - Sergi Elizalde and Peter Winkler.
**Sorting by Placement and Shift** - Ryan O'Donnell and Yi Wu.
**3-Bit Dictator Testing: 1 vs. 5/8** - Siddharth Barman and Shuchi Chawla.
**Packing multiway cuts in graphs** - Frederic Chazal, Leonidas Guibas, Steve Oudot and Primoz Skraba.
**Analysis of Scalar Fields over Point Cloud Data** - Frederic Magniez, Ashwin Nayak, Peter Richter and Miklos Santha.
**On the hitting times of quantum versus random walks** - Elad Hazan and Satyen Kale.
**Better Algorithms for Benign Bandits** - Florin Constantin, Jon Feldman, S Muthukrishnan and Martin Pal.
**An Online Mechanism for Ad Slot Reservations with Cancellations** - Colin Cooper and Alan Frieze.
**The cover time of random geometric graphs** - Lorenz Minder and Alistair Sinclair.
**The extended k-tree algorithm** - Misha Belkin, jian sun and Yusu Wang.
**Constructing Laplace operators from Point Clouds** - Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh and Prabhakar Raghavan.
**Online story scheduling for web advertising** - Mohsen Bayati, Andrea Montanari and Amin Saberi.
**Generating Random Graphs with Large Girth** - Florian Diedrich and Klaus Jansen.
**Improved Approximation Algorithms for Scheduling with Fixed Jobs** - Aurore Amaudruz and Christina Fragouli.
**Combinatorial Algorithms for Wireless Information Flow** - Ran Duan and Seth Pettie.
**Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths** - Mehmet Begen and Maurice Queyranne.
**Appointment Scheduling with Discrete Random Durations** - Navin Goyal, Luis Rademacher and Santosh Vempala.
**Expanders via Random Spanning Trees** - Aaron Williams.
**Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts** - Ran Duan and Seth Pettie.
**Dual-Failure Distance and Connectivity Oracles** - david gamarnik and Dimitry Katz.
**Sequential cavity method for computing limits of the log-partition function for** - Alexander Golynski.
**Lower Bounds for Succinct Data Structures** - Umang Bhaskar, Lisa Fleischer, Darrell Hoy and Chien-Chung Huang.
**Equilibria of Collusive Flow Games are not Unique** - Sam Greenberg, Amanda Pascoe and Dana Randall.
**Sampling Biased Lattice Configurations using Exponential Metrics** - Benoît Hudson, Gary Miller, Todd Phillips and Don Sheehy.
**Size Complexity of Volume Meshes vs. Surface Meshes** - Yury Lifshits and Shengyu Zhang.
**Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.**

For DSF we give an $O(n^\ee \cdot \min\{n^{4/5},m^{2/3}\})$-approximation scheme using a novel LP-relaxation that seeks to connect pairs with ''cheap'' paths. This is the first sub-linear (in terms of $n=|V|$) approximation ratio for the problem; all previous algorithm had ratio $\Omega(n^{1+\ee})$.

For $k$-DSF we give a simple greedy $O(k^{1/2 + \ee})$-approximation algorithm. This improves the best known ratio $\tilde{O}(k^{2/3})$ by Charikar et~al. \cite{CCC}, and (almost) matches in terms of $k$ the best ratio known for the undirected variant \cite{GHNR}. Even when used for the particular case of DSF, our algorithm favorably compares to the one of \cite{CEGS}, which repeatedly solves linear programs and uses complex space and time consuming transformations. Our algorithm is much simpler and faster, since it essentially reduces $k$-DSF to a variant of the Directed Steiner Tree problem. The simplification is due to a new notion of ``junction star-tree'' -- a union of an in-star and an out-branching having the same root, which is of independent interest.

To obtain the above result, we study the set $\TL$ of line transversals which emanate from a fixed line $\ell_0$, establish an almost tight bound of $O(nk^{1+\eps})$ on the complexity of $\TL$, and provide a randomized algorithm which computes $\TL$ in comparable expected time. Slightly improved combinatorial bounds for the complexity of $\TL$, and comparable improvements in the cost of constructing this set, are established for two special cases, both assuming that the polyhedra of $\P$ are pairwise disjoint: the case where $\ell_0$ is disjoint from the polyhedra of $\P$, and the case where the polyhedra of $\P$ are unbounded in a direction parallel to $\ell_0$.

Linear probing is one of the most popular implementations of hash tables in practice. We store all keys in a single array. A new key is hashed. If a different key is in the position hashed to, we scan next positions sequentially until either the key is found, or we hit an empty spot concluding that the key is new. This is compact and it is fast because we typically get all positions considered in single cache-line, and that also holds for deletions. However, linear probing has been known to be a bit unreliable in practice. Analyzing the performance of linear probing with universal hash functions was raised as an open problem by Carter and Wegman in 1979.

At STOC'07, Pagh et al.~studied the expected number of linear probes with worst-case data sets. They showed that with the standard implementation of 2-universal hashing, the expected number of probes could be $\Omega(\log n)$. A worst-case is one or two intervals --- something that could very well appear in practice, possibly explaining the experienced unreliability. On the positive side, they showed that with 5-universal hashing, the expected number of probes is constant.

Unfortunately, we do not have 5-universal hashing for, say, variable length strings. When we want to do such complicated hashing on a complicated domain, the generic standard solution is that we first do collision free hashing (w.h.p.) into a simpler intermediate domain, and second do the complicted hash function on this intermediate domain.

Our contribution is that for an expected constant number of linear probes, it is suffices that each key has $O(1)$ expected collisions with the first hash function, as long as the second hash function is 5-universal. This means that the intermediate domain can be $n$ times smaller. Such a smaller intermediate domain typically means that the both the first and the second hash function run at least twice as fast. This doubling of hashing speed follows not just for variable length strings, but for most domains bigger than 32-bit integers, e.g., fixed length strings and even 64-bit integers.

Unfortunately, the problem of finding an induced cycle passing through two given vertices is NP-complete in a general graph. However, if the input graph is constrained to be planar and $k$ is fixed, then the induced cycle problem can be solved in polynomial time.

In particular, an $O(n^2)$ time algorithm is given for the case $k=2$ by McDiarmid, Reed, Schrijver and Shepherd, where $n$ is the number of vertices of the input graph.

Our main results in this paper are to improve their result in the following sense.

(1) The number of vertices $k$ is allowed to be non-trivially super constant number, up to $k = o((\frac{\log n}{\log \log n})^{\frac{2}{3}})$. More precisely, when $k = o((\frac{\log n}{\log \log n})^{\frac{2}{3}})$, then the ICP in planar graphs can be solved in $O (n^{2 + \varepsilon})$ time for any $\varepsilon > 0$. (2) The time complexity is linear if the given graph is planar and $k$ is fixed. (3) The above results are extended to graphs embedded in a fixed surface.

We note that the linear time algorithm (the second result) is independent from the first result. Let us observe that if $k$ is as a part of the input, then the problem is still NP-complete. So we need to impose some condition on $k$.

Our proofs of the above results basically follow the same line of the proof of the disjoint paths problem by Robertson and Seymour, together with Reed, Robertson, Schrijver, Seymour's result, which improves the time complexity of the algorithm of the disjoint paths by Robertson and Seymour ($O(n^3)$ time algorithm) to linear time when an input graph is planar. However, our cycle must be induced, so some of arguments must be extended to induced paths, which needs much more involved arguments. In addition, we are also interested in the case when $k$ is as a part of the input. Therefore, we need to sharpen the function of $k$. This needs nontrivial amount of work, since both Robertson-Seymour's proof and Reed, Robertson, Schrijver, Seymour's proof do not care much about sharpening the hidden constant of $k$. These proofs just guarantee the existence of the function of $k$, therefore, it is highly expensive, and nonpractical. Our proofs, though, give fairly small function of $k$. Therefore, we believe that this result may be viewed as a much more practical result. Price to pay is to need to analyze the structure of planar graphs and graphs embedded in a fixed surface more closely.

Cuckoo hashing, introduced by Pagh and Rodler (``Cuckoo hashing'', ESA 2001 and J. Algorithms 51, 2004), is a strategy for maintaining hash tables for keys from $U$, $|U|=N$, so that lookups take constant time in the worst case. The data structure consists of two tables of size $m$ each, and it uses two hash functions $h_1, h_2\colon U\to [m]$. For the scheme to work it is necessary and sufficient that $m \ge (1+\eps)n$ for an arbitrary constant $\eps>0$, where $n$ is the number of keys stored.

Pagh and Rodler's analysis establishes expected amortized constant time for insertion; for the analysis to work it is required that the hash functions are $c \log n$-wise independent. In experiments, cuckoo hashing works very well with weaker hash function classes. However, Pagh and Rodler report on experimental results that indicate that cuckoo hashing might not work well in combination with the ``multiplicative class'' (which consists of functions $h_a: [2^k]\to[2^l]$ of the form $h_a(x)=((a x)\bmod 2^k)\div 2^{k-l}$, for $0<a<2^k$ odd, and is close to ``2-universal''). They state that they do not have an explanation for this phenomenon.

In 2008, Mitzenmacher and Vadhan (``Why simple hash functions work: exploiting the entropy in a data stream'', SODA 2008) proved that if a 2-universal hash class $H$ is used and the key set exhibits a certain degree of randomness, and further technical conditions are fulfilled, then the combination of the key set and a hash function chosen at random from $H$ will behave very close to full randomness, in a technical sense.

Our results:

1) We show that if cuckoo hashing with $2^l=m=2n$ is employed (this table size is way above the threshold sufficient for the standard analysis), then all function pairs from the multiplicative hash class will work badly with high probability for fully random key sets of size $n$, if $n/N > N^{1-\gamma}$ for some constant $\gamma>0$. On the one hand, this explains the experimental results obtained by Pagh and Rodler and justifies a warning against using this simple class, on the other hand, it shows that one of the ``further technical conditions'' of the Mitzenmacher/Vadhan result, namely the requirement that key sets must be relatively sparse in $U$, is really necessary for their result to be true.

2) We show that cuckoo hashing with a standard almost 2-wise independent class of hash functions (functions of the form $h_{a,b}=((ax+b)\bmod p)\bmod m$, $p \ge |U|$ a prime number) exhibits a similar behavior as the class in 1), again in the case where the key set is relatively dense in $U$. This is true even in the case when the two hash functions use different prime moduli.

Further related work:

Cohen and Kane (``Bounds on the independence required for cuckoo hashing'', unpublished manuscript, 2005, http://web.mit.edu/dankane/www/Independence%20Bounds.pdf) construct $2$-, $3$-, and even $5$-wise independent hash families, for which cuckoo hashing has high failure probability. However, these families are quite contrived and far from being common.

Our results are based on a strong structural lemma for planar graphs which also implies that the size of a clique in the square of a planar graph of maximum degree~$\Delta$ is at most $\frac32\,\Delta$ plus a constant.

In this paper we investigate three issues pertaining to the bit-complexity of LZ-based compressors, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. These theoretical results will be sustained by some experiments that will compare our novel LZ-based compressors against the most popular compression tools (like Gzip, Bzip) and state-of-the-art compressors (like the Compression Booster [Ferragina-Giancarlo-Manzini-Sciortino, J.ACM 52(4), 2005]).

Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: the first gives an exact relationship between the expected value of a halfspace $f$ and the sum of the squares of $f$'s degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube $\{-1,1\}^n$ (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over $\bits^n$ poses significant additional complications and requires other ingredients. These include ``cross-consistency'' versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas \cite{FKR+:02}.

Our result is significant because the strategy improvement algorithm provides, for the first time, a way to approximate the value of a concurrent safety game from below. Since a value iteration algorithm, or a strategy improvement algorithm for reachability games, can be used to approximate the same value from above, the combination of both algorithms yields a method for computing a converging sequence of upper and lower bounds for the values of concurrent reachability and safety games. Previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.

Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our first coordination mechanism has approximation ratio $O(\log m)$ and always guarantees that the induced game has pure Nash equilibria to which the system converges in at most $n$ rounds. This result improves a recent bound of $O(\log^2 m)$ due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio $O\left(\frac{\log m}{\log \log m}\right)$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice ``cost-revealing'' potential function. Besides in proving the existence of equilibria, we use this potential function in order to upper-bound the price of stability of the induced game by $O(\log m)$, the price of anarchy by $O(\log^2m)$, and the convergence time to $O(\log^2m)$-approximate assignments by a polynomial number of best-response moves. Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.

We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in $n^{\sqrt k}$ and $1/\sigma$. Second, we prove an upper bound of $k^{kd} \poly(n, 1/\sigma)$, where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for $k, d \in O(\sqrt{\log n/\log \log n})$.

Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances.

We present the first polynomial-time $O(\log n)$-approximation algorithm for this problem. This significantly advances the state-of-the-art, as no polynomial-time $o(n)$-approximation was known previously. Previous results for this problem were known only in more restrictive settings. In particular, either if instance satisfies the so-called ``no-bottleneck'' assumption: $\max_i d_i \leq \min_t c_t$, or else if the ratio of both the maximum to the minimum demands and the maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in $n$. Our result, on the other hand, does not require any of these assumptions.

Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an $\Omega(n)$ integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

VarOpt_k provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, it is the first online scheme with this property and the optimality is against any off-line sampling scheme tailored for the concrete set of items seen: no off-line scheme based on k samples can perform better than our on-line scheme when it comes to average variance over any subset size. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible, even by an offline scheme. It is efficient, handling each new item of the stream in O(log k) time, which is optimal even on the word RAM. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting.

This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri. The method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. This factorization, which is due to Grothendieck, is regarded as a central tool in modern functional analysis. The primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the Grothendieck factorization. These ideas also result in a novel approximation algorithm for the $(\infty, 1)$ norm of a matrix, which is generally {\sf NP}-hard to compute exactly. As an added bonus, this work reveals a surprising connection between matrix factorization and the famous {\sc maxcut} semidefinite program.

First, we prove that lambda_s(n) <= n * 2^{1/t! alpha(n)^t + O(alpha(n)^{t-1})} for s>=4 even, and lambda_s(n) <= n * 2^{1/t! alpha(n)^t log_2 alpha(n) + O(alpha(n)^t)} for s>=3 odd, where t = floor((s-2)/2), and alpha(n) denotes the inverse Ackermann function. This constitutes an improvement for s>=6, since the previous bounds, by Agarwal, Sharir, and Shor (1989), had a leading coefficient of 1 instead of 1/t! in the exponent. The bounds for even s>=6 are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al.

More importantly, we also present a new technique for deriving upper bounds for lambda_s(n). This new technique is based on some recurrences very similar to the ones used by the author, together with Alon, Kaplan, Sharir, and Smorodinsky (SODA 2008), for the problem of stabbing interval chains with j-tuples. With this new technique we: (1) re-derive the upper bound of lambda_3(n) <= 2n alpha(n) + O(n sqrt alpha(n)) (first shown by Klazar, 1999); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport-Schinzel sequences considered by Adamec, Klazar, and Valtr (1992).

Regarding lower bounds, we show that lambda_3(n) >= 2n alpha(n) - O(n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds of lambda_s(n) >= n * 2^{1/t! alpha(n)^t - O(alpha(n)^{t-1})} for s>=4 even.

A set of permutations $P \subset S_n$ is {\em expanding} if the product of any two elements of $P$ yields a distinct permutation. Stated otherwise, $|P^2|=|P|^2$ where $P^2 \subset S_n$ is the set of products of two elements of $P$. Our first result is a randomized algorithm that computes $|P^2|$ and hence decides if $P$ is expanding. The algorithm also produces a table that, for any $\sigma_1,\sigma_2,\sigma_3,\sigma_4 \in P$, answers the query $\sigma_1\sigma_2 = \sigma_3\sigma_4$ in $\tilde{O}(1)$ time. The algorithm uses, among other ingredients, a combination of fast matrix multiplication and polynomial identity testing. In particular, for $|P|=n$ our algorithm runs in $O(n^\omega)$ time where $\omega < 2.376$ is the matrix multiplication exponent. We note that the naive deterministic solution for this problem requires $\Theta(n^3)$ time.

For a set of permutations $P \subset S_n$ we say that $i$ $k$-dominates $j$ if the number of permutations $\pi \in P$ for which $\pi(i) < \pi(j)$ is $k$. The {\em dominance matrix} of $P$ is the $n \times n$ matrix $D_P$ where $D_P(i,j)=k$ if and only if $i$ $k$-dominates $j$. We give an efficient algorithm for computing $D_P$ using fast {\em rectangular} matrix multiplication. In particular, when $|P|=n$ our algorithm runs in $O(n^{2.684})$ time. Computing the dominance matrix of permutations is computationally equivalent to the dominance problem in computational geometry. In particular, our algorithm slightly improves upon a well-known $O(n^{(\omega+3)/2})$ time algorithm of Matousek for the dominance problem. Permutation dominance is used, together with a few other ingredients, to obtain a truly sub-cubic algorithm for the {\em All Pairs Shortest Paths} (APSP) problem in real-weighted directed graphs, where the number of distinct weights emanating from each vertex is $O(n^{0.338})$. A very special case of this algorithm implies an $O(n^{2.842})$ time algorithm for real vertex-weighted APSP, which slightly improves a recent result of Chan [STOC-07].

In this paper we consider fingerprinting with the marking assumption and design codes that achieve much higher rates than previous constructions. We conjecture that these codes attain the maximum possible rate (the fingerprinting capacity) for any fixed number of pirates. We prove new upper bounds for the fingerprinting capacity that are not far from the rate of our codes.

We introduce the novel model of weak fingerprinting codes where one pirate should be caught only if the identity of all other pirates are revealed. We construct fingerprinting codes in this model with improved rates but our upper bound on the rate still applies. In fact, these improved codes achieve the fingerprinting capacity of the weak model by a recent upper bound.

Using analytic techniques we compare the rates of our codes in the standard model and the rates of the optimal codes in the weak model. To our surprise these rates asymptotically agree, that is, their ratio tends to $1$ as $t$ goes to infinity. Although we cannot prove that each one of our codes in the standard model achieves the fingerprinting capacity, this proves that asymptotically they do.

These results seem to be interesting in the light of the well-known fact, that to decide whether a given $3$-uniform hypergraph is bipartite is $NP$-complete. On the other hand, the property of being bipartite is known to be testable. We hope that understanding better the structure of (hyper-)graph properties might be useful for average case analysis of running time of coloring algorithms on restricted hypergraph classes, and also advantageous in developing efficient property testers.

Chazelle's soft heaps are derived from the BINOMIAL HEAPS data structure in which each priority queue is composed of a collection of BINOMIAL TREES. We describe a simpler and more direct implementation of soft heaps in which each priority queue is composed of a collection of standard BINARY trees. Our implementation has the advantage that no CLEAN-UP operations similar to the ones used in Chazelle's implementation are required. We also present a concise and unified potential-based amortized analysis of the new implementation.

We also present algorithms for finding discounted all-pairs shortest paths.

Polynomial time algorithms for the 2-gathering problem can be obtained via reductions to the \{K_{2},K_{3}\}-packing problem studied by Hell and Kirkpatrick, the general factor problem studied by Cornue'jols, and to the simplex matching problem studied recently by Anshelevich and Karagiozova. The resulting algorithms, however, are much slower than the new algorithm presented.

We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. This problem is known as Maximum Independent Set on d-box graphs. Our results for MISR imply an O((log n)^{d-2}loglog n) approximation algorithm for this problem, improving upon the best previously known O((log n)^{d-1})-approximation.

Here, we study several notions of quasi-randomness for 3-uniform hypergraphs which correspond to the regularity lemmas of Frankl and Rödl, Gowers and Haxell, Nagle and Rödl. We establish an equivalence among the three notions of regularity of these lemmas. Since the regularity lemma of Haxell et al. is algorithmic, we obtain algorithmic versions of the lemmas of Frankl-Rödl (a special case thereof) and Gowers as corollaries. As a further corollary, we show that the special case of the Frankl-Rödl lemma (which we can make algorithmic) suffices for an application of its corresponding Counting Lemma.

We present a bi-criteria approximation algorithm that achieves an approximation factor of $O(\sqrt{\log{n}\log{k}})$, which matches or improves over previous algorithms for all relevant values of $k$. Our algorithm uses a semidefinite relaxation which combines $\ell _2^2$ metrics with spreading metrics. Surprisingly, we show that the integrality gap of the semidefinite relaxation is $\Omega (\log{k})$ even for large values of $k$ (e.g., $k=n^{\Omega(1)}$), implying that the dependence on $k$ of the approximation factor is necessary. This is in contrast to the situation with previous approximation algorithms for $k$-balanced partitioning which are based on linear programming relaxations and where the approximation factor is independent of $k$.

Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface S guarantees the existence of (and can be converted to a linear-time algorithm to find) a subgraph H, whose size depends only on S, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the ``winding number" of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends (a.k.a. integral multicommodity flows) to find a 3-coloring.

If the input triangle-free graph G drawn in S is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates S then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.

Our algorithm uses the fast edge splitting paradigm introduced by Bhalgat et al. \cite{BHKP08}. We seek to split out a large fraction of the vertices, recurse on the resulting graph, and then put back the split-off vertices. The main challenge we face is that only vertices with even degree may be split-off in an undirected graph and there may not be any such vertex in the current graph. The edge orientation algorithms of Gabow and Nagamochi-Ibaraki as well as Frank's proof are based on showing the existence of at least two even degree vertices (in fact, vertices with degree $2k$) in a $2k$ minimally connected graph. We generalize this to show that in any edge minimal $2k$ connected graph, there are at least $n/3$ even degree vertices. These vertices are then split-off.

Our next challenge is to drop edges from the given graph so it remains $2k$ connected and yet has $\Omega(n)$ even degree vertices. We provide two algorithms for this. The first algorithm produces an edge-minimal $2k$ connected graph in time $\tilde{O}(nk^5+m)$; this improves the previous best $\tilde{O}(n^2k^2 + m)$ algorithm for this task due to by Gabow \cite{G94}. The second algorithm speeds this up by a factor of $k$ by giving up the minimality criterion; it discards edges specifically to produce $\Omega(n)$ even degree vertices while maintaining connectivity $2k$ and takes time $\tilde{O}(nk^4+m)$.

When one of the matrices satisfies triangle inequality, we give an algorithm achieving approximation ratio ~ 3.16, which improves over the previous best factor of 4 (Arkin et al. 2001).

See complete abstract in pdf file.

We also prove that any comparison-based, deterministic, multi-pass streaming algorithm for finding the median requires $\Omega(n\log^*(n/s) + n\log_s n)$ worst-case time (in scanning plus comparisons), if we have $s$ cells of space. This bound is also tight for all $s\gg\log^2 n$. We can get similar deterministic lower bounds for I/O-efficient algorithms, or for the two-dimensional linear programming problem.

All proofs are ``elementary''.

We mention consequences to external-memory data structures, and as an aside, we partially answer another open question concerning the crossing number in Matou\v sek's {\em shallow partition theorem\/} in the 3-d case (a tool used in known halfspace range reporting methods).

Compressed Counting (CC) is proposed for efficiently computing the $\alpha$th frequency moment, also for $0<\alpha\leq2$. In the neighborhood of $\alpha = 1$, its sample complexity is $O\left(1/\epsilon\right)$, instead of $O\left(1/\epsilon^2\right)$. The underlying technique of CC is maximally-skewed stable random projections.

Our contributions include:

1) Compressed Counting (CC) is the first proposal of using skewed projections in data stream computations. We also show that maximally-skewed projections can achieve the best performance.

2) CC is the first algorithm which captures the intuition that, when $\alpha =1$ a simple counter suffices, and when $\alpha = 1\pm\Delta$ with small $\Delta$, the sample complexity should be low. We show the sample complexity of a proposed estimator $= \frac{G}{\epsilon^2}\log\left(\frac{2}{\delta}\right)$, where $G= O\left(\epsilon\right)$ as $\Delta\rightarrow 0$. In other words, for small $\Delta$, CC has the complexity $=O\left({1}/{\epsilon}\right)$. Previous results only achieved $O\left(1/\epsilon^2\right)$ (even for $\alpha =1$), which in general is expected and can not be improved, according to the central limit theorem.

3) We show, when $\alpha = 1\pm\Delta$, the asymptotic variance of a proposed estimator is $\propto \Delta$. As $\alpha \rightarrow 1$, CC achieves ``an infinite improvement'' over the previous results, in terms of the asymptotic variances.

4) Our results (especially when $\alpha=1\pm\Delta\approx 1$) have important applications. In some situation, $\Delta$ might be interpreted as the ``decay rate'' or ``interest rate,'' which is usually small. The method of moments is popular for statistical inference, which requires computing frequency moments. Also, some important summary statistics such as Renyi entropy and Tsallis entropy are functions of frequency moments and hence CC naturally provides an efficient algorithm to compute them. Very importantly, CC may serve the basic building element for developing other algorithms, for example, approximating the Shannon entropy using Renyi entropy and Tsallis entropy with $\alpha\approx 1$.

4) Our results enrich the fundamental theory of skewed stable distributions.

Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees

Abstract: We present a novel connection between binary search trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results:

1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality.

2. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86].

3. The first proposal for dynamic optimality not based on splay trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.

The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.

We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality. To achieve this, we give a direct conversion from dictatorship tests to integrality gap instances bypassing the use of a reduction from \textsc{UniqueGames} and the Khot-Vishnoi \cite{khotvishnoi} integrality gap instances for \textsc{UniqueGames}.

In this paper we show that the top-down approach can be sped up, permitting an order of magnitude improvement in the running time of many algorithms in the literature for such Huffman-coding variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.

In this paper, we are interested in sparse graphs. More specifically, we deal with minor-closed class of graphs, i.e., graphs without $K_k$-minors. We develop the seminal structure theorem of Robertson and Seymour, and then give an additive approximation for list-coloring within $k-2$ of the list-chromatic number. This improves the $O(k)$-multiplicative-approximation algorithm by Kawarabayashi and Mohar (STOC'06). Clearly our result gives rise to an additive approximation algorithm for graph-coloring of minor-closed class of graphs too. This result is comparable to the 2-approximation algorithm of graph-coloring by Demaine, Hajiaghayi and Kawarabayashi (FOCS'05), since our additive approximation algorithm may give a better graph-coloring. This result also answers a question posed by Robin Thomas (who conjectured that there is an additive approximation algorithm for graph-coloring of minor-closed class of graphs).

Our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected $H$-minor-free graphs. In particular, this class of graphs can be easily decomposed into two parts so that one part has bounded tree-width and the other part is disjoint union of bounded genus graphs. Moreover, we can control the number of edges between two parts. Also, the proof method itself tells us how knowledge of a local structure can be used to gain a global structure. This may be of interest, since this gives a new insight how to decompose a graph, with help of a local structure information.

\medskip

{\bf Input}: A graph $G$, $k$ pair of vertices $(s_1,t_1),(s_2,t_2),\dots, (s_k,t_k)$ in $G$ (which are sometimes called {\it terminals}), and a parity $l_i$ for each $i$ with $1 \leq i \leq k$, where $l_i=0$ or $1$.

\medskip

{\bf Output} : Paths $P_1,\dots,P_k$ in $G$ such that $P_i$ joins $s_i$ and $t_i$ for $i=1,2,\dots,k$ and parity of length of the path $P_i$ is $l_i$, i.e, if $l_i=0$, then length of $P_i$ is even, and if $l_i=1$, then length of $P_i$ is odd for $i=1,2,\dots,k$.

In addition, each vertex is on at most two of these paths.

\medskip

We present an $O(m \alpha(m,n) \log n)$ algorithm for fixed $k$, where $n,m$ are the number of vertices and the number of edges, respectively, and the function $\alpha(m,n)$ is the inverse of the Ackermann function. This is the first polynomial time algorithm for this problem, and generalizes polynomial time algorithms by Kleinberg (STOC'98) and Kawarabayashi and Reed (SODA'08), respectively, for the half integral disjoint paths packing problem, i.e., without the parity requirement.

As with the Robertson-Seymour algorithm to solve the $k$ disjoint paths problem, in each iteration, we would like to either use a huge clique minor as a ''crossbar", or exploit the structure of graphs in which we cannot find such a minor. Here, however, we must maintain the parity of the paths and can only use an ''odd clique minor". We must also describe the structure of those graphs in which we cannot find such a minor and discuss how to exploit it.

In fact, we also have algorithms running in $O(m^{(1+\epsilon)})$ time for any $\epsilon > 0$ for this problem, if $k$ is up to $o(\log{\log{\log n}})$ for general graphs, up to $o(\log{\log n})$ for planar graphs, and up to $o(\log{\log n/g})$ for graphs on the surface, where $g$ is Euler genus. Furthermore, if $k$ is fixed, then we have linear time algorithms for the planar case and for the bounded genus case.

In this paper, we consider the problem of approximating a monotone submodular function $f$ on a ground set of size $n$ {\it everywhere}, after only polynomially many oracle queries. Our main result is a deterministic algorithm that make polynomially many oracle queries to derive a function $\hat{f}$ of the form $\hat{f}(S)=\sqrt{\sum_{i\in S} c_i}$ such that, for {\it every} set $S$, $\hat{f}(S)$ approximates $f(S)$ within a factor $\alpha(n)$, where $\alpha(n)=\sqrt{n+1}$ for rank functions of matroids and $\alpha(n)=O(\sqrt{n} \log{n})$ for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. We should point out that the general algorithm of Grötschel, Lov\'asz and Schrijver for finding a large inscribed ellipsoid in a centrally symmetric convex body given by a separation oracle would only give us an approximation factor of $O(n)$.

Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than $\Omega(\sqrt{n} / \log(n))$, even for rank functions of a matroid.

More formally, we characterize a class of randomized mechanisms defined for known single-minded bidders that are strategyproof and revenue monotonic, and furthermore satisfy some other desirable properties, namely participation, consumer sovereignty and maximality, representing the mechanism as a solution to a quadratically constrained linear program. We prove that the QCLP is always feasible (i.e., for all bidder valuations) and give its solution analytically. Furthermore, we give an algorithm for running such a mechanism in time quadratic in the number of bidders; this is interesting because constructing an instance of such mechanisms from our QCLP formulation in a naive way can be of exponential time.

Ilia Binder and Mark Braverman. The complexity of simulating Brownian Motion Abstract: We analyze the complexity of the Walk on Spheres algorithm for simulating Brownian Motion in a domain Omega in R^d. The algorithm, which was first proposed in the 1950s, produces samples from the hitting probability distribution of the Brownian Motion process on boundary of Omega within an error of epsilon. The algorithm is used as a building block for solving a variety of differential equations, including the Dirichlet Problem.

The WoS algorithm simulates a BM starting at a point X_0=x in a given bounded domain Omega until it gets epsilon-close to the boundary of Omega. At every step, the algorithm measures the distance d_k from its current position X_k to the boundary of Omega and jumps a distance of d_k/2 in a uniformly random direction from X_k to obtain X_{k+1}. The algorithm terminates when it reaches X_n that is epsilon-close to the boundary of Omega.

It is not hard to see that the algorithm requires at least Omega(\log 1/epsilon) steps to converge. Only partial results with respect to upper bounds existed. In 1959 M. Motoo established an O(\log 1/epsilon) bound on the running time for convex domains. The results were later generalized for a wider, but still very restricted, class of planar and 3-dimensional domains by G.A. Mikhailov (1979). In our earlier work (2007), we established an upper bound of O(\log^2 1/epsilon) on the rate of convergence of WoS for arbitrary planar domains.

In this paper we introduce subharmonic energy functions to obtain very general upper bounds on the convergence of the algorithm. Special instances of the upper bounds yield the following results for bounded domains Omega:

* if Omega is a planar domain with connected exterior, the WoS converges in O(\log 1/epsilon) steps;

* if Omega is a domain in R^3 with connected exterior, the WoS converges in O(\log^2 1/epsilon)$ steps;

* for d>2, if Omega is a domain in R^d, the WoS converges in O((1/epsilon)^{2-4/d}) steps;

* for d>3 if Omega is a domain in R^d with connected exterior, the WoS converges in O((1/epsilon)^{2-4/(d-1)}) steps;

* for any d if Omega is a domain in R^d bounded by a smooth surface, the WoS converges in O(\log 1/epsilon) steps.

We also demonstrate that the bounds are tight, i.e. we construct a domain from each class for which the upper bound is exact. Our results give the optimal upper bound of O(\log1/epsilon) in many cases for which only a bound polynomial in 1/epsilon was previously known.

Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari and Pat Morin. Succinct Geometric Indexes Supporting Point Location Queries Abstract: We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence, to support geometric queries in optimal time. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using $\lg n + 2\sqrt{\lg n} + O(\lg^{1/4} n)$ point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location queries in O(H+1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that use O(n) words or O(n lg n) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in $O(\lg^2 n)$ time.

For approximation 1+\epsilon, we achieve a query time of n^{0.5+t}, for arbitrary small $t>0$, with a polynomial space. To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time.

We study the online version of the dynamic queue problem. It is quite easy to see that the greedy algorithm that always collects the maximum-value item is 2-competitive, and that no deterministic online algorithm can be better than 1.618-competitive. We improve both bounds: We give a 1.89-competitive algorithm for general dynamic queues and we show a lower bound of 1.632 on the competitive ratio. We also provide other upper and lower bounds for restricted versions of this problem.

The dynamic queue problem is a generalization of the well-studied buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.

Our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. The algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate Bregman projection. Bregman projections are widely used in convex optimization and machine learning. We present an algorithm which efficiently approximates the Bregman projection onto the set of high density measures when the Kullback-Leibler divergence is used as a distance function. Our algorithm has a logarithmic runtime over any domain provided that we can efficiently sample from this domain. High density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. Hence, our technique may be of independent interest.

We study the approximability of the size of the sparsest k-TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family.

[Algorithms.] We present two efficient deterministic algorithms that find k-TC-spanners of size approximating the optimum. The first algorithm gives an O-tilde(n^{1-1/k})-approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) DIRECTED k-SPANNER, a well-studied generalization of k-TC-SPANNER, and (2) its variants CLIENT/SERVER DIRECTED k-SPANNER, and the k-DIAMETER SPANNING SUBGRAPH. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k-TC-spanner problem, gives an O-tilde(n/(k^2))-approximation. It shows that for k = Omega(\sqrt{n}), our problem has a provably better approximation ratio than DIRECTED k-SPANNER and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).

[Inapproximability.] Our main technical contribution is a pair of strong inapproximability results. We resolve the approximability of 2-TC-spanners, showing that it is Theta(log n) unless P=NP. For constant k>2, we prove that the size of the sparsest k-TC-spanner is hard to approximate within 2^{\log^{1-\epsilon} n}, for any \epsilon > 0, under standard complexity assumptions. Our hardness result helps explain the difficulty in designing general efficient solutions for the applications above, and it cannot be improved without resolving a long-standing open question in complexity theory. It uses an involved application of generalized butterfly and broom graphs, as well as noise-resilient transformations of hard problems, which may be of independent interest.

[Structural bounds.] Finally, we study the size of the sparsest TC-spanner for H-minor-free digraphs, which include planar, bounded genus, and bounded tree-width graphs, explicitly investigated in applications above. We show that every H-minor-free digraph has an efficiently constructable k-TC-spanner of size O-tilde(n), which implies an O-tilde(1)-approximation algorithm for this family. Furthermore, using our insight that 2-TC-spanners yield property testers, we obtain a monotonicity tester with O(log^2 n /\epsilon)) queries for any poset whose transitive reduction is an H-minor free digraph. This improves and generalizes the previous Theta(\sqrt{n} \log n/\epsilon)-query tester of Fischer et al (STOC, 2002).

We propose a new approach, of embedding the difficult space into richer host spaces, namely iterated products of standard spaces like $L_1$ and $L_\infty$. We show that this class is /rich/ since it contains useful metric spaces with only a constant distortion, and, at the same time, it is /tractable/ and admits efficient algorithms. Using this approach, we obtain for example the first nearest neighbor data structure with $O(\log \log d)$ approximation for edit distance in non-repetitive strings (the Ulam metric). This approximation is exponentially better than the {\em lower bound} for embedding into $L_1$. Furthermore, we give constant factor approximation for two other computational problems. Along the way, we answer positively a question left open in [Ajtai-Jayram-Kumar-Sivakumar, STOC'02]. One of our algorithms has already found applications for smoothed edit distance over 0-1 strings [Andoni-Krauthgamer, ICALP'08].

In contrast, we show that any deterministic single-pass algorithm for finding a repeated element needs space at least $m$, even if $n$ is arbitrarily large compared to $m$. However, we show that when we have access to a clock that records the number of input symbols read so far, the space required drops to $\log m + O(1)$ if $n \geq 2^m$; thus for this problem non-uniformity adds considerable power to deterministic algorithms. For non-uniform deterministic algorithms we show that finding a repeated element in a stream of length $n$ requires space at least $m-\log n$; we show that this lower bound is close to optimal for a range of values of $n$.

An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from $O(n \log n)$ to an optimal $O(n)$, resolving one of the last remaining open problems concerning consensus in this model.

Our embedding results have immediate applications to local Distance Oracles. We show how to preprocess a graph in polynomial time to obtain a data structure of $O(n k^{1/t} \log^2 k)$ bits, such that distance queries from any node to its $k$ nearest neighbors can be answered with stretch $t$.

The decision version of MKP is strongly NP-complete, since it is a generalization of the classical knapsack and bin packing problem. Furthermore, MKP does not admit an FPTAS even if the number $m$ of bins is two. Kellerer gave a PTAS for MKP with identical capacities and Chekuri and Khanna presented a PTAS for MKP with general capacities with running time $n^{O(\log(1/\epsilon) / \epsilon^8)}$. In this paper we propose an EPTAS with parameterized running time $2^{O(\log(1/\epsilon)/\epsilon^5)} \cdot poly(n) + O(m)$ for MKP.

It has been an open problem whether the star insertion problem is polynomially solvable. We give an affirmative answer by describing the first efficient algorithm for this problem. This algorithm uses the SPQR-tree data structure to handle the exponential number of possible embeddings, in conjunction with dynamic programming schemes for which we introduce \emph{partitioning cost} subproblems.

In this paper we study these two fundamental online problems under the framework of bijective analysis [Angelopoulos, Dorrigiv and Lopez-Ortiz, SODA 2007 and LATIN 2008]. This is an intuitive technique which is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. Coupled with a well-established model of locality of reference due to Albers, Favrholdt and Giel [JCSS 2005], we show that Least-Recently-Used and Move-to-Front are the unique optimal algorithms for paging and list update, respectively. Prior to this work, only measures based on average-cost analysis have separated LRU and MTF from all other algorithms. Given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense LRU and MTF stand out as the best algorithms.

Our method exploits the connection with the classical problem of estimating the maximum sum of pairwise distances among $n$ points on the unit sphere, first studied by L\'aszl\'o Fejes T\'oth. It is quite general and yields the first non-trivial estimates below $\sqrt2$ on the star Steiner ratios in arbitrary dimensions. We show, however, that the star Steiner ratio in $\RR^d$ tends to $\sqrt{2}$, the upper bound given by Fekete and Meijer, as $d$ goes to infinity. Our estimates on the star Steiner ratios are therefore much closer to the conjectured values in higher dimensions! %The quality of our estimates on the star Steiner %ratios is therefore much better for higher dimensions! As it turns out, our estimates as well as the conjectured values of the Steiner ratios (in the limit, for $n$ going to infinity) are related to the classical infinite Wallis product: $ \frac{\pi}{2}= \prod_{n=1}^{\infty} \left(\frac{4n^2}{4n^2-1}\right) = \frac21 \cdot \frac23 \cdot \frac43 \cdot \frac45 \cdot \frac65 \cdot \frac67 \cdot \frac87 \cdot \frac89 \cdots $.

We show that a lower density that behaves roughly like $\epsilon^{-k+1}$ suffices for this purpose. We also show that our bound on $d$ is nearly best possible in the sense that there are $k$-CNF formulas $F$ of slightly lower density that whp remain satisfiable after smoothing. Moreover, the well known Walksat algorithm will whp find a satisfying assignments in these smoothed formulas (whenever $\epsilon\geq 1/k$).

Our proof (when setting $\epsilon = 1/2$) gives a new lower bound of $\Omega(2^k/k^2)$ on the density in which for most $k$-CNF formulas the Walksat algorithm whp terminates successfully in polynomial time. We are not aware of any previous rigorous analysis that shows that Walksat is successful at densities that are increasing as a function of $k$.

A related problem of special interest is that of finding an equilibrium maximizing a certain objective, such as the social welfare. This optimization problem was shown to be NP-hard by Gilboa and Zemel [Games and Economic Behavior 1989]. However, this NP-hardness is unlikely to extend to finding an approximate equilibrium, since the latter admits a quasi-polynomial time algorithm, as proved by Lipton, Markakis and Mehta [EC, 2003].

We show that this optimization problem, namely, finding in a two-player game an approximate equilibrium achieving large social welfare is unlikely to have a polynomial time algorithm. One interpretation of our results is that the quest for a PTAS for Nash equilibrium should NOT extend to a PTAS for finding the best Nash equilibrium, which stands in contrast to certain algorithmic techniques used so far (e.g. sampling and enumeration).

Technically, our result is a reduction from a notoriously difficult problem in modern combinatorics, of finding a planted (but hidden) clique in a random graph G(n,1/2). Our reduction starts from an instance with planted clique size k=O(log n). For comparison, the currently known algorithms due to Alon, Krivelevich and Sudakov [RSA, 1998], and Krauthgamer and Feige [RSA, 2000], are only effective for a much larger clique size $k=\Omega(\sqrt n)$.

The ratio index has several interesting structural properties. First, we show that it can be computed in strongly polynomial time; the techniques we develop may be useful for deriving strongly polynomial algorithms for other Markov Decision Problems. Second, we show that with the appropriate discount factor, the Gittins index and our ratio index are constant factor approximations of each other, and hence the Gittins index also gives a constant factor approximation to the budgeted learning problem. Finally, we show that the ratio index can be used to create an index based policy that achieves an $O(1)$-approximation for the finite horizon version of the multi-armed bandit problem. Moreover, the policy does not require any knowledge of the horizon (whereas we compare its performance against an optimal strategy that is aware of the horizon). This yields the following surprising result: there is an index based policy that achieves an $O(1)$-approximation for the multi-armed bandit problem, oblivious to the underlying discount factor.

That is, parametrizing an instance by the fraction p of non-simple clauses, we give a single algorithm which is the fastest known for p=0 (which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses); the only efficient algorithm for mixtures of AND, OR, and general integer-weighted clauses; and tied for fastest for general Max 2-CSP (p=1). Since a pure 2-Sat input instance may be transformed to a general instance in the course of being solved, the algorithm's efficiency and generality go hand in hand.

Our novel analysis results in a family of running-time bounds, each optimized for a particular value of p, but valid for all p. The algorithm uses some new reductions introduced here, as well as recent reductions such as "clause-learning" and "2-reductions" adapted to our setting's mixture of simple and general clauses. Each reduction imposes constraints on various parameters, the running-time bound is an "objective function" of these parameters and p, and the optimal running-time bound is obtained by solving a convex nonlinear program, which can be done efficiently and with a certificate of optimality.

In this paper we study the structure of $\SP_n$. More precisely, let $b(\ell;\, \SP_n)$ be the number of blocks (i.e.\ maximal biconnected subgraphs) of $\SP_n$ that contain exactly $\ell$ vertices, and let~$lb(\SP_n)$ be the number of vertices in the largest block of $\SP_n$. We show that with high probability $\SP_n$ contains a \emph{giant} block that includes up to lower order terms $cn$ vertices, where $c \approx 0.959$ is an analytically given constant. Moreover, we show that the \emph{second} largest block contains only $n^{2/3}\text{polylog}(n)$ vertices, and prove sharp concentration results for $b(\ell;\, \SP_n)$, for all~$2\le\ell\le n^{2/3}$.

In fact, we obtain this result as a consequence of a much more general result that we prove in this paper. Let $\CG$ be a class of labeled connected graphs, and let $\SG_n$ be a graph drawn uniformly at random from graphs in $\CG$ that contain exactly $n$ vertices. Under certain assumptions on~$\CG$, and depending on the behavior of the singularity of the generating function enumerating the elements of $\CG$, $\SG_n$ belongs with high probability to one of the following three categories, which differ vastly in complexity. $\SG_n$ either \begin{itemize} \item[(1)] behaves like a random planar graph, i.e.\ $lb(\SG_n) \sim cn$, for some analytically given $c = c(\CG)$, and the second largest block is of order $n^{\alpha}$, where $1 > \alpha = \alpha(\CG)$, or \item[(2)] $lb(\SG_n) = \mathcal{O}(\log n)$, i.e., all blocks contain at most logarithmically many vertices, or \item[(3)] $lb(\SG_n) = \Theta(n^{\alpha})$, for some $\alpha = \alpha(\CG)$. \end{itemize} Planar graphs belong to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2), and differ thus substantially from planar graphs.

Our proofs exploit recent progress in the development of Boltzmann samplers by Duchon, Flajolet, Louchard and Schaeffer [dfls04] and basic tools from modern probability theory.

\medskip

There are only finitely many list-color-critical graphs with all lists of cardinality 5 on a fixed surface.

\medskip

This generalizes the well-known result of Thomassen on the usual graph coloring case.

We use this theorem to address the complexity status of the following question on list-coloring graphs on a fixed surface $S$.

\medskip

{\bf Input}: A graph $G$ in the surface $S$.

{\bf Output}: Is $G$ $k$-list-colorable? If not, provide a certificate (a list-color-critical subgraph) for this. If yes, given any lists of cardinality $k$, then give a $k$-list-coloring.

\medskip

In fact, together with our recent algorithmic result, we give a linear time algorithm for the problem when $k \geq 5$. The cases $k=3,4$ are known to be NP-hard, and the cases $k=1,2$ are easy. This generalizes the well-known linear time algorithms for planar graphs by Nishizeki and Chiba (for 5-coloring), and Thomassen (for 5-list-coloring).

We also give a polynomial time algorithm to address the following algorithmic question:

\medskip

{\bf Input}: A graph $G$ in the surface $S$, and lists of cardinality $k \geq 5$.

{\bf Output}: Does $G$ have a valid coloring from the lists? If not, provide a certificate for this. If yes, then give a $k$-list-coloring.

\medskip

This is different from the first algorithmic one in the sense that some list-color-critical graph $H$ may have a valid coloring from some lists of $H$. Therefore, the second one is strictly stronger than the first one. We give a polynomial time algorithm for this problem too.

We also use our main theorem to prove the following conjecture, made recently by Thomassen:

\medskip

For every fixed surface $S$, there exists a positive constant $c$ such that every $5$-list-colorable graph with $n$ vertices embedded on $S$, and any lists of cardinality 5, has at least $c \times 2^{n}$ distinct 5-list-colorings.

\medskip

Thomassen himself proved that this conjecture holds for the usual 5-coloring.

In addition to these results, we also made partial progress toward a conjecture of Albertson concerning coloring extension.

In this paper we present the first known approximation algorithms for the problem of maximizing a non-decreasing submodular set function subject to multiple linear constraints. Given an oracle for a non-decreasing submodular set function $f$ over a universe $U$, where each element $e \in U$ is associated with a $d$-dimensional cost vector and a $d$-dimensional budget vector $\bL$, for some $d \geq 1$, we seek a subset of elements $\mathbf{S} \subseteq U$ whose total cost is at most $\bL$, such that $f(\mathbf{S})$ is maximized.

We develop a framework for maximizing submodular functions subject to $d$ linear constraints that yields a $(1-\eps)(1-e^{-1})$-approximation to the optimum for any $\eps > 0$, where $d >1$ is some constant. Our study is motivated from a variant of the classical maximum coverage problem that we call {\em maximum coverage with multiple packing constraints}. We use our framework to obtain the same approximation ratio for this problem. To the best of our knowledge, this is the first time the theoretical bound of $1-e^{-1}$ is (almost) matched for both of these problems.

References

[ABS08] M. R. Ackermann, J. Blömer, and C. Sohler. Clustering for metric and non-metric distance measures. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), pages 799--808, 2008.

We prove strong lower bounds on the achievable competitive ratios for delay factor scheduling even with unit-time requests. Motivated by this, we consider resource augmentation analysis and prove the following positive results. For the unicast model we give algorithms that are $(1 + \eps)$-speed $O({1 \over \eps})$-competitive in both the single machine and multiple machine settings. In the broadcast model we give an algorithm for similar-sized pages that is $(1+ \eps)$-speed $O({1 \over \eps^2})$-competitive. Online algorithms have been difficult to design for the broadcast setting and ours is the first to give a $(1+\eps)$-speed analysis for a natural measure of performance.

This quest for better approximation algorithms is further fueled by the implicit hope that these better approximations also give us better clusterings. E.g., for many problems such as clustering proteins by function, or clustering images by subject, there is some unknown ``correct'' target clustering---one that clusters proteins by function, or that clusters images by content---and there is an implicit hope is that approximately optimizing these objective functions will in fact produce a clustering that is close (in symmetric difference) to the truth.

In this paper, we show that if we make this implicit assumption explicit---that is, if we assume that any $c$-approximation to the given clustering objective $F$ is $\epsilon$-close to the target---then we can produce clusterings that are $O(\epsilon)$-close to the target, {\em even for values $c$ for which obtaining a $c$-approximation is NP-hard}. In particular, for $k$-median and $k$-means objectives, we show that we can achieve this guarantee for any constant $c > 1$, and for min-sum objective we can do this for any constant $c > 2$.

Our results also highlight a somewhat surprising conceptual difference between assuming that the {\em optimal} solution to, say, the $k$-median objective is $\epsilon$-close to the target, and assuming that any {\em approximately optimal} solution is $\epsilon$-close to the target, even for approximation factor say $c=1.01$. In the former case, the problem of finding a solution that is $O(\epsilon)$-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.

We study the following two extensions of the secretary problem:

1. In the discounted secretary problem, there is a time-dependent ``discount'' factor $d(t)$, and the benefit derived from selecting an element/secretary $e$ at time $t$ is $d(t)\cdot v(e)$. For this problem with arbitrary (not necessarily decreasing) functions $d(t)$, we show a constant-competitive algorithm when the expected optimum is known in advance. With no prior knowledge, we exhibit a lower bound of $\Omega(\frac{\log n}{\log \log n})$, and give a nearly-matching $O(\log n)$-competitive algorithm. 2. In the weighted secretary problem, up to $K$ secretaries can be selected; when a secretary is selected (s)he must be irrevocably assigned to one of $K$ positions, with position $k$ having weight $w(k)$, and assigning object/secretary $e$ to position $k$ has benefit $w(k)\cdot v(e)$. The goal is to select secretaries and assign them to positions to maximize $\sum_{e,k}w(k)\cdot v(e)\cdot x_{ek}$ where $x_{ek}$ is an indicator variable that secretary $e$ is assigned position $k$. We give constant-competitive algorithms for this problem.

Most of these results can also be extended to the \emph{matroid secretary} case (Babaioff et al., \emph{SODA~2007}) for a large family of matroids with a constant-factor loss, and an $O(\log \text{rank})$ loss for general matroids. These results are based on a reduction from various matroids to partition matroids which present a unified approach to many of the upper bounds of Babaioff et al.

These problem is closely connected with online mechanism design (see, e.g., Hajiaghayi et al., \emph{Elec.~Comm.~2004}). All our algorithms are monotone, and hence lead to truthful mechanisms for the corresponding online auction problem.

We consider several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random $\alpha$ fraction of the population following the given advice is sufficient to get behavior within an $O(1/\alpha)$ factor of the price of stability for any $\alpha > 0$. However, for some games such as consensus and cut games, there is a strict threshold (in this case, $\alpha < 1/2$ yields almost no benefit, yet $\alpha > 1/2$ is enough to reach near-optimal behavior), and for some games, such as scheduling, no value $\alpha < 1$ is sufficient. We also consider a ``viral marketing'' model in which certain players are specifically targeted, and analyze the ability of such targeting to influence behavior using a much smaller number of targeted players.

Yusu Wang, Kevin Buchin and Maike Buchin. Exact Algorithm for Partial Curve Matching via the Frechet Distance

Abstract: Curve matching is a fundamental problem that occurs in many applications. In this paper, we study the problem of measuring \emph{partial} similarity between curves. More specifically, given two curves, we wish to maximize the total length of subcurves of them that are \emph{close} to each other, where the \emph{closeness} is measured by the Frechet distance, a common distance measure for curves. The resulting maximal length is called the \emph{partial Frechet similarity} between the two input curves. Given two polygonal curves $P$ and $Q$ in $\reals^d$ of sizes $n$ and $m$, respectively, we present the first exact algorithm that runs in polynomial time to compute $\PFDist(P,Q)$, the partial Frechet similarity between $P$ and $Q$, under the $L_1$ and the $L_\infty$ norms. Specifically, we reduce the problem of computing $\PFDist(P,Q)$ to $O(nm(n+m))$ instances of a simpler problem, each of which can be solved in $O((n+m)\log (nm))$ time. Hence the partial Frechet similarity between $P$ and $Q$ under the $L_1$ or the $L_\infty$ norm can be computed in $O(nm(n+m)^2 \log (nm))$ time. To the best of our knowledge, this is the first paper to study this natural definition of partial curve similarity between curves under the continuous setting (where all points in the curve are considered), and present a polynomial-time exact algorithm for it.

Our results represent significant progress over previous results from two decades ago by Faigle and Turan. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n (w + log n)). We also describe a variant of Mergesort with query complexity O(w n log(n/w)) and total complexity O(w^2 n log(n/w)); an algorithm with the same query complexity was given by Faigle and Turan, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations.

We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(w n) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.

We show that in fact the algorithm terminates after at most $2^{n-1}-1$ steps in the worst case (confirming a conjecture of L. Larson), and that there are super-exponentially many permutations for which this exact bound can be achieved. The proof involves a curious symmetrical binary representation.

In this work we show that Fourier analysis techniques *can* produce a Dictator Test based on NTW with completeness 1 and soundness 5/8. Our test's analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness *ower bound* of 5/8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick [Zwi98].

Our work completes the determination of the 3-query "Dictatorship Testing curve". Although this represents progress on Zwick's conjecture, current PCP "outer verifier" technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result.

We present an LP-based algorithm for the multiway cut packing problem in general graphs that guarantees a maximum edge load of at most $8\OPT+4$. Our rounding approach is based on the observation that every instance of the problem admits a laminar solution (that is, no pair of cuts in the solution crosses) that is near-optimal. For the special case where each commodity has only two terminals and all commodities share a common sink (the ``common sink $s$-$t$ cut packing" problem) we guarantee a maximum load of $\OPT+1$. Both of these variants are NP-hard; for the common-sink case our result is optimal.

Then, extending a recent theorem of Tulsi [2007] for the 2D grid, we show that for any state-transitive Markov chain with unique marked state, the quantum hitting time is of the same order for both the detection and finding problems. We conjecture that this remains true for all reversible Markov chains and any number of marked states.

Perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining $\tilde{O}(\sqrt{T})$ regret was discovered in this setting.

In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of $\tilde{O}(\sqrt{Q})$, where $Q$ is the total variation in the cost functions. This regret bound shows that it is possible to incur much less regret in a slowly changing environment, and in fact, matches regret bounds that are attainable in the simpler stochastic setting, when the cost functions are obtained from a probability distribution. This regret bound, previously conjectured to hold in the full information case, is surprisingly attainable even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling.

We propose and study a simple model for auctioning such ad slot reservations in advance. There is one seller with a set of slots to be displayed at some point T in the future. Until T, bidders arrive sequentially and place a bid on the slots they are interested in. The seller must decide immediately whether or not to grant a reservation. Our model allows the seller to cancel at any time any reservation made earlier, in which case the holder of the reservation incurs a utility loss amounting to a fraction of its value for the reservation, and may also receive a cancellation fee from the seller.

Our main result is an online mechanism for allocation and pricing in this model with many desirable game-theoretic properties. It is individually rational; winners have an incentive to be honest and bidding one's true value dominates any lower bid. Further, it bounds the earnings of speculators who are in the game to obtain the cancellation fees. The mechanism in addition has optimization guarantees. Its revenue is within a constant fraction of the a posteriori revenue of the famed Vickrey-Clarke-Groves (VCG) auction which is known to be truthful (in the offline case). Our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. If efficiency also takes into account the utility losses of bidders whose reservation was canceled, we show that our mechanism matches (for appropriate values of the parameters) an upper bound on the competitive ratio of any deterministic online algorithm.

The technical core of the mechanism is a variant of the online weighted bipartite matching problem where unlike prior variants in which one randomizes edge arrivals or bounds edge weights, we need to consider revoking previously committed edges. On top of an online competitive algorithm for this problem, we impose an appropriate payment structure to obtain the main game-theoretic and optimization guarantees of our mechanism. Our results make no assumptions about the arrival order or value distribution of bidders. They still hold if we replace items with elements of a matroid and matchings with independent sets of the matroid, or if all bidders have linear (additive) value for a set of items.

In many applications, however, it is necessary to work with lists of smaller length, where the above algorithm breaks down. In this paper we generalize the algorithm to work for significantly smaller values of the list length $m$, all the way down to the minimum value for which a solution exists with reasonable probability. Our algorithm exhibits a tradeoff between the value of $m$ and the running time. We also provide rigorous bounds on the failure probability of both our algorithm and that of Wagner and Blum et al.

The resulting algorithm is easy to implement. We present experimental results indicating that even for point sets sampled from a uniform distribution, PCD Laplace converges faster than the weighted graph Laplacian. We also show that certain geometric invariants, such as manifold area, can be estimated directly from the point cloud using our PCD Laplacian with reasonable accuracy. We make the software publically available at the authors' webpages.

We consider two models based on the maximum delay that can be allowed between the arrival and scheduling of a job. In the first, a job can be scheduled anytime after its arrival; in the second a job is lost unless scheduled immediately upon arrival, pre-empting a currently running job if needed. The two settings correspond to two natural models of how long an advertiser retains interest in a relevant user. We show that there is, in fact, a {\em sharp separation} between what an online scheduler can achieve in these two settings. In the first setting with no deadlines, we give a natural deterministic algorithm with a constant competitive ratio against the offline scheduler. In contrast, we show that in the sharp deadline setting, no (deterministic or randomized) online algorithm can achieve better than a polylogarithmic ratio.

Our approach is based on \emph{sequential} methods that have been recently successful for efficiently counting and generating random graphs.

Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the interactions between the signals in a wireless network, i.e., broadcasting and interference, and ignores the effect of noise. The argument is that for high Signal-to-Noise-Ratio, it is these signal interactions that will dominate the performance, and thus the capacity of the deterministic could be very close to that of the noisy network. Thus networks of deterministic channels can be used as approximate models for wireless networks.

Constructively taking interference into account allows to achieve, even for a single unicast session, a capacity that can be $O(N)$ larger than the capacity when only broadcasting and routing are employed, where $N$ is the number of network nodes, as we show through a developed example.

To characterize how much the capacity of a unicast session is, Avestimehr, Diggavi and Tse generalized the min-cut max-flow theorem for graphs to networks of deterministic channels. They showed that the value of the minimum cut is in this case the minimum rank of all the binary adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes very fast infeasible.

Avestimehr et al. also proved that the value of the minimum cut can be achieved, by using information theoretical tools, where intermediate network nodes have no complexity constraints, and perform random mappings using arbitrarily long blocks of bits. In practical networks, it is not realistic to envisage such operations; thus the natural question that arises is whether the calculated capacity can be achieved or approximated in practice, using bounded complexity operations at the network nodes, and how well.

In this paper, we develop a polynomial time algorithm that allows to achieve the min-cut value in binary linear deterministic networks, for the case of a unicast connection. Our algorithm crucially uses a notion of Linear Independence between edges, and cannot be derived as direct consequence of the Ford-Fulkerson algorithm or other path-augmenting techniques over graphs. Using our algorithm we can calculate the capacity in polynomial time; moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes.

In a similar fashion to Vassilevska et al., we reduce $(\max,\min)$-product to computing the {\em dominance product} of sparse real-valued matrices. However, our reduction is different and we use a completely new sparse dominance product algorithm whose running time is incomparable to that of Vassilevska et al. The running time of our $(\max,\min)$-multiplier matches that of the best dominance product algorithm but is slightly slower than the $O(n^{2.575})$-time APBP algorithm of Shapira et al.~that assumes {\em vertex}-capacitated graphs.

We also give faster algorithms for the \emph{all-pairs bottleneck shortest path} (APBSP) problem on both edge- and vertex-capacitated graphs. The problem here is to find the maximum flow that can be sent from $s$ to $t$ along a {\em shortest} path w.r.t.~the unit length function. For edge-capacitated graphs, the running time of our APBSP algorithm is $O(n^{(3+\omega)/2})$, matching the time bound of our APBP algorithm. For vertex-capacitated graphs the running time is $O(n^{2.65})$, which improves significantly on the $O(n^{2.86})$ time algorithm of Shapira et al.

A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger as well as Spielman-Srivastava have shown sparsifiers with $O(n \log n/\eps^2)$ edges that achieve approximation within factors $1+\eps$ and $1-\eps$. Their methods, based on independent sampling of edges, need $\Omega(n\log n)$ edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size $O(n)$ that approximate every cut to within a factor of $O(\log n)$.

Alexander Golynski. Lower Bounds for Succinct Data Structures

Abstract: In this paper, we consider several data structure problems in the static deterministic cell probe model. % We develop a new technique for proving lower bounds for succinct data structures, where the redundancy in the storage can be small compared to the information-theoretic minimum. % The lower bounds are truly succinct in the sense that we try to match (up to constant factors) the lower order terms of the existing data structures with the lower order terms provided by our lower bound. % Using this technique, we obtain (i) the first lower bound for the problem of searching and retrieval of a substring in text; (ii) a cell probe lower bound for the problem of representing permutation $\pi$ with queries $\pi(i)$ and $\pi^{-1}(i)$ that matches the lower order term of the existing data structures, and (iii) a lower bound for representing binary matrices that is also matches upper bounds for some set of parameters. % The nature of all these problems is that we are to implement two operations that are in a reciprocal relation to each other (search and retrieval, computing forward and inverse element, operations on rows and columns of a matrix). % As far as we know, this paper is the first to provide an insight to such problems.

Without collusion, it follows from well-known convexity arguments that equilibria are unique (up to induced latencies). The question is, does this uniqueness continue to hold in the presence of collusion?

We answer no: We show that if collusion is allowed in nonatomic routing games, there may be multiple equilibria. We demonstrate this multiplicity via 2 specific examples. In addition, we show our examples are topologically minimal by giving a complete characterization of network topologies for which, up to induced latencies, unique equilibria exist.

Though the oracle gives much less information compared to the standard general metric space model where distance values are given, one can still design very efficient algorithms for various fundamental computational tasks. For nearest neighbor search we present deterministic and exact algorithm with almost linear time and space complexity of preprocessing, and near-logarithmic time complexity of search. Then, for near-duplicate detection we present the first known deterministic algorithm that requires just near-linear time + time proportional to the size of output. Finally, we show that for any dataset satisfying the disorder inequality a visibility graph can be constructed: all out-degrees are near-logarithmic and greedy routing deterministically converges to the nearest neighbor of a target in logarithmic number of steps. The later result is the first known work-around for Navarro's impossibility of generalizing Delaunay graphs.

The technical contribution of the paper consists of handling "false positives" in data structures and an algorithmic technique up-aside-down-filter.