We study a general network design problem with additional degree constraints. Given connectivity requirements r_uv for all pairs of vertices, a Steiner network is a graph in which there are at least r_uv edge-disjoint paths between u and v for all pairs ...

We consider the problem of finding an unknown graph by using two types of queries with an additive property. Given a graph, an additive query asks the number of edges in a set of vertices while a cross-additive query asks the number of edges crossing ...

We prove a lower bound of ω(n^k/4) on the size of constant-depth circuits solving the k-clique problem on n-vertex graphs (for every constant k). This improves a lower bound of ω(n^k/89d2) due to Beame where d is the circuit depth. Our lower bound has the ...

In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of $n$ trials so as to maximize the total payoff of the chosen strategies. While the performance of bandit algorithms with a small finite strategy set is ...

The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an *arbitrary* distribution, we would like to produce an hypothesis whose accuracy ...

The classical Direct-Product Theorem for circuits says that if a Boolean function f: {0,1}ⁿ -> {0,1} is somewhat hard to compute on average by small circuits, then the corresponding k-wise direct product function f^k(x₁,...,x_k)=(f(x₁),...,f(x_k)) (where ...

We give a query algorithm for agnostically learning decision trees with respect to the uniform distribution on inputs. Given black-box access to an *arbitrary* binary function f on the n-dimensional hypercube, our algorithm finds a function that agrees ...

In the 2nd Annual FOCS (1961), C. K. Chow proved that every Boolean threshold function is uniquely determined by its degree-0 and degree-1 Fourier coefficients. These numbers became known as the Chow Parameters. Providing an algorithmic version of Chow'...

We show that unless NP = RP, it is hard to (even) weakly PAC-learn intersection of two halfspaces in Rⁿ using a hypothesis which is a function of up to l linear threshold functions for any integer l. Specifically, we show that for every integer l and an ...

We design a randomized online algorithm for k-server on binary trees with hierarchical edge lengths, with expected competitive ratio O(log Delta), where Delta is the diameter of the metric. This is one of the first k-server algorithms with competitive ...

We show how to construct a variety of "trapdoor" cryptographic tools assuming the worst-case hardness of standard lattice problems (such as approximating the length of the shortest nonzero vector to within certain polynomial factors). Our contributions ...

We study the survivable network design problem (SNDP) for vertex connectivity. Given a graph G(V,E) with costs on edges, the goal of SNDP is to find a minimum cost subset of edges that ensures a given set of pairwise vertex connectivity requirements. ...

We present a simple and fast deterministic algorithm for the minimum k-way cut problem in a capacitated graph, that is, finding a set of edges with minimum total capacity whose removal splits the graph into at least k components. The algorithm packs O(...

We present an O(log n• log k)-approximation algorithm for the problem of finding k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in the input graph, and k is the connectivity requirement. Our algorithm works for ...

A temporal constraint language is a set of relations that has a first-order definition in (b Q,<), the dense linear order of the rational numbers. We present a complete complexity classification of the constraint satisfaction problem (CSP) for temporal ...

The connection between integrality gaps and computational hardness of discrete optimization problems is an intriguing question. In recent years, this connection has prominently figured in several tight UGC-based hardness results. We show in this paper a ...