## Columbia Theory Reading Group, Fall 2005

Abstracts for the talks are given below. See the main page for schedule and location information.

Wed Sept 7:
Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT
Tel Aviv University

Goemans and Williamson obtained an approximation algorithm for the MAX CUT problem with a performance ratio of $\alpha_{GW} ~ 0.87856$. Their algorithm starts by solving a standard SDP relaxation of MAX CUT and then rounds the optimal solution obtained using a random hyperplane. In some cases, the optimal solution of the SDP relaxation happens to lie in a low dimensional space. Can an improved performance ratio be obtained for such instances? We show that the answer is yes in dimensions two and three and conjecture that this is also the case in any higher fixed dimension. In two dimensions an optimal $\frac{32}{25+5\sqrt{5}}$-approximation algorithm was already obtained by Goemans. (Note that $\frac{32}{25+5\sqrt{5}} ~ 0.88456$.) We obtain an alternative derivation of this result using Gegenbauer polynomials. Our main result is an improved rounding procedure for SDP solutions that lie in $R^3$ with a performance ratio of about $0.8818$. The rounding procedure uses an interesting yin-yan coloring of the three dimensional sphere. The improved performance ratio obtained resolves, in the negative, an open problem posed by Feige and Schechtman [STOC'01]. They asked whether there are MAX CUT instances with integrality ratios arbitrarily close to $\alpha_{GW} ~ 0.87856$ that have optimal embedding, i.e., optimal solutions of their SDP relaxations, that lie in $R^3$.

Joint work with Uri Zwick.

Wed Sept 21st:
Separating Models of Learning from Correlated and Uncorrelated Data
Homin Lee
Columbia University

We consider a natural framework of learning from correlated data, in which successive examples used for learning are generated according to a random walk over the space of possible examples. Previous research has suggested that the Random Walk model is more powerful than comparable standard models of learning from independent examples, by exhibiting learning algorithms in the Random Walk framework that have no known counterparts in the standard model. We give strong evidence that the Random Walk model is indeed more powerful than the standard model, by showing that if any cryptographic one-way function exists (a universally held belief in public key cryptography), then there is a class of functions that can be learned efficiently in the Random Walk setting but not in the standard setting where all examples are independent.

Joint work with Ariel Elbaz, Rocco Servedio, and Andrew Wan.

Wed Oct 5:
Fast Leader-Election Protocols with Bounded Cheaters' Edge
Spyros Antonakopoulos
Columbia University

The leader election problem refers to a situation in which n players wish to select a random leader among them, in a distributed computation setting. It is assumed that some of the players -- we don't know exactly who -- may be malicious and collude in order to maximize the probability that one of them is eventually elected. Thus, the goal is to design a protocol that limits any such undue influence from cheating players.

In the first part of this talk, we begin by describing the underlying model, named full- or perfect-information model, which stipulates how players may communicate and what computational resources they possess. Then, the most common performance measure for leader-election protocols is defined, followed by a survey of previous results in this area.

During the second part, we argue why we feel that the aforementioned performance measure, known as resilience, is not the most appropriate from a practical point of view. By contrast, we propose a new quantity, called cheaters' edge, and contend that a good protocol must have bounded cheaters' edge. In game-theoretic terms, such a protocol acts very much like a mechanism and discourages collusion. As far as the majority of existing protocols are concerned, either their analysis fails to guarantee this property, or we can prove directly that they do not satisfy it. Finally, we present new leader-election protocols that exhibit bounded cheaters' edge for any number of malicious players, up to O(n / sqrt(log n loglog n)), which is the best constructive result known to date. Our protocols are also fast, in a very precise sense.

Thur Oct 11:
Equilibria in Online Games
Roee Engelberg
Technion

We initiate the study of scenarios that combine both online decision making and interaction between non-cooperative agents. To this end we introduce the notion of online games that model such scenarios as non-cooperative games, and lay out the foundations for studying this model. Roughly speaking, an online game captures systems in which independent agents serve requests in a common environment. The requests arrive in an online fashion and each is designated to be served by a different agent. The cost incurred by serving a request is paid for by the serving agent, and naturally, the agents seek to minimize the total cost they pay. Since the agents are independent, it is not likely that some central authority can enforce a policy or an algorithm (centralized or distributed) on them, and thus, the agents can be viewed as selfish players in a non-cooperative game. In this game, the players have to choose as a strategy an online algorithm according to which requests are served. To further facilitate the game theoretic approach, we suggest the measure of competitive analysis as the players' decision criteria. As the expected result of non-cooperative games is an equilibrium, the question of finding the equilibria of a game is of central importance, and thus, finding equilibria in online games is the central issue we concentrate on.

We study the following natural examples for online games: the paging game, the file caching game in a distributed system, and the online generalized Steiner tree game. In order to obtain general insights and develop generic techniques, we present an abstract model for the study of online games generalizing metrical task systems.

This is joint work with Seffi Naor.

Wed Oct 26:
On the Possibility of Obfuscation with Auxilary Input
Shafi Goldwasser
Massachusetts Institute of Technology and The Weizmann Institute of Science

Barak et al. formalized the notion of obfuscation, and showed that there exist (contrived) classes of functions that cannot be obfuscated. In contrast, Canetti and Wee showed how to obfuscate point functions, under various complexity assumptions. Thus, it would seem possible that most programs of interest can be obfuscated even though in principle general purpose obfuscators do not exist. We show that this is unlikely to be the case. In particular, we consider the notion of obfuscation w.r.t. auxiliary input, which corresponds to the setting where the adversary, which is given the obfuscated circuit, may have some a priori information. This is essentially the case of interest in any usage of obfuscation we can imagine. We prove that there exist natural classes of functions that cannot be obfuscated w.r.t. auxiliary input, both when the auxiliary input is dependent of the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated. We also give a positive result. In particular, we show that any obfuscator for the class of point functions is also an obfuscator w.r.t. independent auxiliary input.

This is joint work with Yael Tauman Kalai.

Wed Nov 16:
Elastic Block Ciphers: Creating PRPs and Strong PRPs
Debbie Cook
Columbia University

We investigate elastic block ciphers, a method for constructing variable length block ciphers, from a theoretical perspective. We view the underlying structure of an elastic block cipher as a network, which we refer to as an elastic network, and analyze the network in a manner similar to the analysis performed by Luby and Rackoff on Feistel networks. We prove that a three round elastic network is a pseudorandom permutation (PRP) and a four round elastic network is a strong pseudorandom permutation (SPRP) when the round functions are independently chosen pseudorandom permutations. As a result, the elastic network provides a method for creating PRPs and SPRPs with variable length inputs from PRPs with fixed sized inputs.

Joint work with Moti Yung and Angelos Keromytis.

Tue Nov 29:
On the Worst Case Complexity of the K-Means
Sergei Vassilvitskii
Stanford University

The k-means method is an old but popular clustering algorithm known for its speed and simplicity. Until recently, however, no meaningful theoretical bounds were known on its running time. In this talk, we demonstrate that the worst-case running time of k-means is superpolynomial by improving the best known lower bound from $\Omega(n)$ iterations to $2^{\Omega(\sqrt{n})}$. To complement this lower bound, we show a smoothed-analysis type polynomial time upper bound for k-means.

Wed, Nov 30:
Discrete LP-type model and discrete optimization
Nir Halman
Massachusetts Institute of Technology

In the early 90', Sharir and Welzl defined the LP-type framework which generalizes Linear Programming (LP). By using LP-type algorithms, one can solve various geometric optimization problems in randomized linear time. An example for such a problem is the smallest enclosing ball in R^d, where given a set of n points in R^d, one needs to find the smallest ball which encloses all the points.

We discretize" the LP-type model in order to get the discrete LP-type model (DLP). We develop for it several randomized linear time algorithms. We use the DLP model in order to solve discrete optimization problems, such as the discrete version of the smallest enclosing ball, where the center of the ball is restricted to be one of the input points. By applying our DLP algorithms, we give the first linear time solution for this problem.

Somewhat surprisingly, our framework is also useful to solve non-geometric problems such as Simple Stochastic Games in subexponential time - which is the best randomized time result uptodate.

Wed, Dec 7:
Rational Secure Computation and Ideal Mechanism Design
Silvio Micali
Massachusetts Institute of Technology

We prove a general result bridging the fields of Secure Protocols and Game Theory.

We show that ANY mediated game with incomplete information can be perfectly simulated by the players alone, essentially by means of an extensive-form game in which the trusted mediator is replaced by a ballot box---the venerable device used throughout the world to privately and correctly compute the tally of secret votes.

In cryptographic terms, we show that, in ANY joint computation, security can be achieved based solely on the players' RATIONALITY, rather than on the HONESTY of at least some players.

Our result has broad implications for Mechanism Design. In particular, it enables Modular and Competitive Mechanism Design.

Joint work with Sergei Izmalkov and Matt Lepinski.

Back to Fall 2005 Theory Seminar main page