SIAM Journal on Computing

We show that any distribution on $\{-1,+1\}^n$ that is $k$-wise independent fools any halfspace (or linear threshold function) $h:\{-1,+1\}^n\to\{-1,+1\}$, i.e., any function of the form $h(x)=\operatorname{sign}(\sum_{i=1}^{n}w_{i}x_{i}-\theta)$, where ...

We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length $n$ must use space $\Omega(\...

Some systems interact with their environment at physically distributed interfaces, called ports, and in testing such a system it is normal to place a tester at each port. Each tester observes only the events at its port and it is known that this limited ...

We give explicit constructions of $\epsilon$-nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension $n$ and in $\frac{1}{\epsilon}$. To the best of our knowledge no ...

Working in Winfree's abstract tile assembly model, we show that a constant-sized tile assembly system can be programmed through relative tile concentrations to build an $n\times n$ square with high probability for any sufficiently large $n$. This ...

Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for Max Cut and Sparsest Cut use semidefinite programming. ...

In this paper we study variants of the nonpreemptive parallel job scheduling problem in which the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule with length at most $(1+\varepsilon)\,\mathrm{...

Gupta et al. [J. ACM, 54 (2007), article 11] and Gupta, Kumar, and Roughgarden [in Proceedings of the ACM Symposium on Theory of Computing, ACM, New York, 2003, pp. 365-372] recently developed an elegant framework for the development of randomized ...

We present a general framework and algorithmic approach for incremental approximation algorithms. The framework handles cardinality constrained minimization problems, such as the $k$-median and $k$-MST problems. Given some notion of ordering on ...

A class of structures satisfies the extension preservation theorem if, on this class, every first-order sentence is preserved under extensions iff it is equivalent to an existential sentence. We consider different acyclicity notions for hypergraphs ($\...

An equality template is a relational structure with infinite universe whose relations can be defined by Boolean combinations of equalities. We prove a complexity classification for quantified constraint satisfaction problems (QCSPs) over equality ...

We study the question of whether a large population of agents in a traffic network is able to converge to an equilibrium quickly. To that end, we consider a round-based variant of the Wardrop model. Every agent is allowed to reroute its traffic once in ...

We present new deterministic algorithms for several cases of the maximum rank matrix completion problem (for short matrix completion), i.e., the problem of assigning values to the variables in a given symbolic matrix to maximize the resulting matrix ...

We study efficient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as a number of servers implementing the data structure. We ...

We describe algorithms to compute the shortest path homotopic to a given path, or the shortest cycle freely homotopic to a given cycle, on an orientable combinatorial surface. Unlike earlier results, our algorithms do not require the input path or cycle ...

We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having $n$ vertices and $k$ pairwise crossings, where $k$ is smaller than $n$...

Due to their simplicity and effectiveness, gossip-based membership protocols have become the method of choice for maintaining partial membership in large peer-to-peer systems. A variety of gossip-based membership protocols were proposed. Some were shown ...

Synchronization is often necessary in parallel computing, but it can create delays whenever the receiving processor is idle, waiting for the information to arrive. This is especially true for barrier, or global, synchronization, in which every processor ...

This paper studies the inherent trade-off between termination probability and total step complexity of randomized consensus algorithms. It shows that for every integer $k$, the probability that an $f$-resilient randomized consensus algorithm of $n$ ...