Browse Proceedings

We show that every language in NP has a statistical zero-knowledge argument system under the (minimal) complexity assumption that one-way functions exist. In such protocols, even a computationally unbounded verifier cannot learn anything other than the ...

In this paper, we use random-selection protocols in the full-information model to solve classical problems in distributed computing. Our main results are the following:--An O(log n)-round randomized Byzantine Agreement (BA) protocol in a synchronous ...

A family of subsets C of [n]\underline{\underline {def}}{1, . . . , n} is (r, t)- exclusive if for every S \subset[n] of size at least n - r, there exist S_1, . . . , S_t \in C with S = S_1\cupS_2\cup· · · \cupS_t. These families, also known as ...

Spin systems are a general way to describe local interactions between nodes in a graph. In statistical mechanics, spin systems are often used as a model for physical systems. In computer science, they comprise an important class of families of ...

We draw on the observation that the amount of heat diffusing outside of a heated body in a short period of time is proportional to its surface area, to design a simple algorithm for approximating the surface area of a convex body given by a membership ...

We prove that the hit-and-run random walk is rapidly mixing for an arbitrary logconcave distribution starting from any point in the support. This extends the work of [26], where this was shown for an important special case, and settles the main ...

We study a switch Markov chain on regular graphs, where switches are allowed only between links that are at distance 2; we call this the Flip. The motivation for studying the Flip Markov chain arises in the context of unstructured peer-to-peer networks, ...

We introduce a game theoretic model of network formation in an effort to understand the complex system of business relationships between various Internet entities (e.g., Autonomous Systems, enterprise networks, residential customers). This system is at ...

We consider the problems of Byzantine Agreement and Leader Election, where a constant fraction b \le 1/3 of processors are controlled by a malicious adversary. The first problem requires that all uncorrupted processors come to an agreement on a bit ...

We prove that the function d : \mathbb{R}^3\times \mathbb{R}^3\to [0,\infty ) given by d\left( {(x,y,z),(t,u,v)} \right)= \left( {[((t - x)^2+ (u - y)^2 )^2+ (v - z + 2xu - 2yt)^2 ]^{\frac{1} {2}}+ (t - x)^2+ (u - y)^2 } \right)^{\frac{1} {2}} .is a ...

This paper addresses the non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce and construct optimal Ramsey partitions, and use them to show that for every \varepsilon\in (0, 1), ...

We initiate the study of approximate algorithms on negatively curved spaces. These spaces have recently become of interest in various domains of computer science including networking and vision. The classical example of such a space is the real-...

Spielman and Teng proved that the shadow-vertex simplex method had polynomial smoothed complexity. On a slight random perturbation of arbitrary linear program, the simplex method finds the solution after a walk on the feasible polytope(s) with expected ...

Recently several results appeared that show significant reduction in time for matrix multiplication, singular value decomposition as well as linear (\ell_ 2) regression, all based on data dependent random sampling. Our key idea is that low dimensional ...

We show a worst-case lower bound and a smoothed upper bound on the number of iterations performed by the Iterative Closest Point (ICP) algorithm. First proposed by Besl and McKay, the algorithm is widely used in computational geometry where it is known ...

We investigate variants of Lloyd's heuristic for clustering high dimensional data in an attempt to explain its popularity (a half century after its introduction) among practitioners, and in order to suggest improvements in its application. We propose ...

Lossless condensers are unbalanced expander graphs, with expansion close to optimal. Equivalently, they may be viewed as functions that use a short random seed to map a source on n bits to a source on many fewer bits while preserving all of the min-...

We consider the problem of approximately locally listdecoding direct product codes. For a parameter k, the kwise direct product encoding of an N-bit message msg is an N^{k}-length string over the alphabet {0, 1}^k indexed by ktuples (i_1, . . . , i_k) \...

Motivated by a problem of transmitting data over broadcast channels (Birk and Kol, INFOCOM 1998), we study the following coding problem: a sender communicates with n receivers R_1, . . . , R_n. He holds an input x \in {0, 1}^n and wishes to broadcast a ...

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds [Joh62, Joh63, GS99]. In particular, we show that for arbitrarily large fields \mathbb{F}_N ,|\mathbb{F}_N| = N, for any \...

Given a graph with maximum cut of (fractional) size c, the Goemans-Williamson [GW95] semidefinite programming (SDP) algorithm is guaranteed to find a cut of size .878 · c. However this guarantee becomes trivial when c is near 1/2, since a random cut has ...

We define a new family of error-correcting codes based on algebraic curves over finite fields, and develop efficient list decoding algorithms for them. Our codes extend the class of algebraic-geometric (AG) codes via a (nonobvious) generalization of the ...

There is a vast body of work on implementing anonymous communication. In this paper, we study the possibility of using anonymous communication as a building block, and show that one can leverage on anonymity in a variety of cryptographic contexts. Our ...

Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole ...

We prove that the problem of finding a Nash equilibrium in a two-player game is PPAD-complete.

We consider the minimum cost spanning tree problem under the restriction that all degrees must be at most a given value k. We show that we can efficiently find a spanning tree of maximum degree at most k+2 whose cost is at most the cost of the optimum ...

Given an undirected hypergraph and a subset of vertices S \subseteqV with a specified root vertex r \in S, the STEINER ROOTED-ORIENTATION problem is to find an orientation of all the hyperedges so that in the resulting directed hypergraph the "...