SIAM Journal on Computing

We give an efficient deterministic algorithm that extracts $\Omega(n^{2\gamma})$ almost-random bits from sources where $n^{\frac{1}{2}+\gamma}$ of the $n$ bits are uniformly random and the rest are fixed in advance. This improves upon previous ...

We analyze the efficiency of the random walk algorithm on random $3$-CNF instances and prove linear upper bounds on the running time of this algorithm for small clause density, less than $1.63$. This is the first subexponential upper bound on the ...

Given a p-order $A$ over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if $(x, y) \in A$, then $|x|$ is polynomially bounded by $|y|$), an interval size function of $A$ returns, for each string $x$ in the ...

We propose simple and efficient CCA-secure public-key encryption schemes (i.e., schemes secure against adaptive chosen-ciphertext attacks) based on any identity-based encryption (IBE) scheme. Our constructions have ramifications of both theoretical and ...

Let $G=(V,E)$ be an edge-weighted undirected graph with $n$ vertices and $m$ edges. We present a deterministic algorithm to compute a minimum $k$-way cut of $G$ for a given $k$. Our algorithm is a divide-and-conquer method based on a procedure that ...

We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every ...

We study practically efficient methods for performing combinatorial group testing. We present efficient nonadaptive and two-stage combinatorial group testing algorithms, which identify the at most $d$ items out of a given set of $n$ items that are ...

The metric labeling problem is an elegant and powerful mathematical model capturing a wide range of classification problems. The input to the problem consists of a set $L$ of labels and a weighted graph $G=(V,E)$. Additionally, a metric distance ...

We exhibit an explicitly computable pseudorandom generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g., PARITY, MAJORITY). This ...

In this work we study two, seemingly unrelated, notions. Locally decodable codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial identity testing (PIT) is one of the ...

We consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge weights. Using an improved “patching”...

We study the problem of waking up a collection of $n$ processors connected by a multihop ad hoc ratio network with unknown topology, no access to a global clock, and no collision detection mechanism available. Each node in the network either wakes up ...

A strong direct product theorem says that if we want to compute $k$ independent instances of a function, using less than $k$ times the resources needed for one instance, then our overall success probability will be exponentially small in $k$. We ...

The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow-based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For ...