For Fall 2012, the usual time for the meetings will be Friday at 11:30 - 13:00 in the CS conference room, CSB 453. Abstracts for talks are given below the talk schedule.

Dana Ron

Tel-Aviv University

**Abstract:**
We give a nearly optimal sublinear-time algorithm for approximating
the size of a minimum vertex cover in a graph G. The algorithm
may query the degree [;\deg(v);] of any vertex v of its choice, and
for each [;1 \leq i \leq \deg(v);], it may ask for the i-th neighbor of
v. Letting [;VCopt(G);] denote the minimum size of vertex cover
in G, the algorithm outputs, with high constant success probability,
an estimate [;wVC(G);] such that [;VCopt(G) \leq wVC(G) \leq 2 VCopt(G) + \epsilon n;],
where [;\epsilon;] is a given additive approximation parameter. We refer to
such an estimate as a [;(2,\epsilon);]-estimate. The query complexity and
running time of our algorithm are [;\tilde{O}(d \cdot {\rm poly}(1/\epsilon));],
where d denotes the average vertex degree in the graph.

The best previously known sublinear algorithm, of Yoshida et al. (STOC 2009), has query complexity and running time [;O(d^4/\epsilon^2);], where d is the maximum degree in the graph. Given the lower bound of [;\Omega(d);] (for constant [;\epsilon;]) for obtaining such an estimate (with any constant multiplicative factor) due to Parnas and Ron (TCS 2007), our result is nearly optimal.

In the case that the graph is dense, that is, the number of edges is [;\Theta(n^2);], we consider another model, in which the algorithm may ask, for any pair of vertices u and v, whether there is an edge between u and v. We show how to adapt the algorithm that uses neighbor queries to this model and obtain an algorithm that outputs a [;(2,\epsilon);]-estimate of the size of a minimum vertex cover whose query complexity and running time are [;\tilde{O}(n) \cdot {\rm \poly}(1/\epsilon);].

Joint work with Krzysztof Onak, Michal Rosen, and Ronitt Rubinfeld

Dimitris Paparas

Columbia University

**Abstract:**
We introduce the notion of non-monotone utilities, which covers a
wide variety of utility functions in economic theory, and prove that
it is PPAD-hard to find an approximate Arrow-Debreu Market
Equilibrium for Markets with linear and non-monotone utilities.
Building on this result, we settle the complexity of finding an
approximate Arrow-Debreu Market Equilibrium in a market with
CES utilities by proving that it is PPAD-complete when the Constant
Elasticity of Substitution parameter, [;\rho;], is any constant less than -1.

Joint work with Xi Chen and Mihalis Yannakakis

Lirong Xia

Harvard University

**Abstract:**
Social choice studies ordinal preference aggregation with applications
ranging from high-stakes political elections to low-stakes movie rating
websites. One recurring concern is that of the robustness of a social
choice (voting) rule to manipulation, bribery and other kinds of strategic
behavior. A number of results have identified ways in which computational
complexity can provide a new barrier to strategic behavior, but most of
previous work focused on case-by-case analyses for specific social
choice rules and specific types of strategic behavior. In this talk,
I present a dichotomy theorem for the manipulability of a broad class
of generalized scoring rules and a broad class of strategic behavior
called vote operations. When the votes are i.i.d., then with high probability
the number of vote operations that are needed to achieve the strategic
individual's goal is 0, [;\Theta(\sqrt{n});], [;\Theta(n);], or infinity. This theorem
significantly strengthens previous results and implies that most social
choice situations are more vulnerable to many types of strategic behavior
than previously believed.

Jason Hartline

Northwestern University

**Abstract:**
Crowdsourcing contests have been popularized by the Netflix challenge and
websites like TopCoder and 99designs. What is a crowdsourcing contest?
Imagine you are designing a new web service, you have it all coded up, but
the site looks bad because you haven't got any graphic design skills. You
could hire an artist to design your logo, or you could post the design task
as a competition to crowdsourcing website 99designs with a monetary reward
of $100. Contestants on 99designs would then compete to produce the best
logo. You then select your favorite logo and award that contestant the $100
prize.

In this talk, I discuss the theory of crowdsourcing contests. First, I will show how to model crowdsourcing contests using auction theory. Second, I will discuss how to solve for contestant strategies. I.e., suppose you were entering such a programming contest on TopCoder, how much work should you do on your entry to optimize your gains from winning less the cost of doing the work? Third, I will discuss inefficiency from the fact that the effort of losing contestants is wasted (e.g., every contestant has to do work to design a logo, but you only value your favorite logo). I will show that this wasted effort is at most half of the total amount of effort. A consequence is that crowdsourcing is approximately as efficient a means of procurement as conventional methods (e.g., auctions or negotiations). Finally, I will give a structural characterization of optimal crowdsourcing contests (in terms of procuring the highest quality work).

Virginie Lerays

Universite Paris-Sud 11

**Abstract:**
The information complexity of a protocol is a lower bound on its
communication complexity. One open question is whether these
quantities are equal or not. We show that almost all known lower
bound methods for communication complexity are also lower bounds
for information complexity. To do that, we define a relaxed version of
the partition bound of Jain and Klauck, which subsumes all rectangle
and norm-based techniques, and we show that it lower bounds the
information complexity.

Our result uses a recent connection between rectangle techniques and zero-communication protocols where players can abort (Laplante, Lerays, Roland 2012). More precisely, the maximum achievable probability that the protocol doesn't abort, which is called efficiency, gives a lower bound on communication complexity which corresponds to the relaxed partition bound. We use compression techniques to relate IC to efficiency.

In this talk, I will first make the link between zero communication protocols, communication complexity and rectangle techniques and then present the compression technique which is similar to those of Braverman and Weinstein 2012 and Braverman 2012. Finally I will present some applications of our theorem.

Oded Regev

Courant Institute, NYU

**Abstract:**
The classical Grothendieck inequality has applications to the design of
approximation algorithms for NP-hard optimization problems. Here show
that a similar algorithmic interpretation may be given to a **noncommutative**
generalization of the Grothendieck inequality due to Pisier and Haagerup.
Our main result, an efficient rounding procedure for this inequality, leads
to a constant-factor polynomial time approximation algorithm for an
optimization problem which generalizes the Cut Norm problem of Frieze
and Kannan, and is shown here to have additional applications to robust
principle component analysis and the orthogonal Procrustes problem.

Time permitting, we will mention the so-called operator space Grothendieck inequality, its applications to quantum information theory, and a new proof on ideas from quantum information.

Based on several joint papers with Assaf Naor and Thomas Vidick.

David Witmer

CMU

**Abstract:**
We consider the non-uniform sparsest cut problem. Given an underlying
capacitated graph G and demands between the vertices of G (forming a
demand graph H), the goal is to find a bipartition of the vertices that
minimizes the ratio of the capacity of edges separated to the total
demand separated by this partition. This is a generalization of the
uniform sparsest cut problem, obtained by placing unit demand
between every pair of vertices. These problems have been well-studied
over the past 25 years for the purpose of developing approximation
algorithms.

In this talk, we give a 2-approximation algorithm for the non-uniform sparsest cut problem with running time [;n^{O(k)};], where k is the treewidth of the underlying graph G. We complement this result by showing a hardness-of-approximation (even for treewidth-2 graphs) of 1/c, where c is the hardness of the max-cut problem on general graphs. This implies a hardness of 17/16 assuming P!=NP and 1/0.878 assuming the Unique Games Conjecture for treewidth-2 graphs G.

Our algorithm rounds a Sherali-Adams LP relaxation. We also show that the integrality gap of this LP remains at least 2-epsilon, even after polynomially many rounds of Sherali-Adams and even for treewidth-2 graphs G.

This is joint work with Anupam Gupta (CMU) and Kunal Talwar (Microsoft Research SVC).

Grigory Yaroslavtsevv

Penn State

**Abstract:**
Submodular functions capture the law of diminishing returns and can be
viewed as a generalization of convexity to functions over the Boolean
cube. Such functions arise in different areas, such as combinatorial
optimization, machine learning and economics. In this talk we will
focus on positive results about learning such functions from examples
and testing whether a given function is submodular with a small number
of queries.

For the class of submodular functions taking values in discrete integral range of size R we show a structural result, giving concise representation for this class. The representation can be described as a maximum over a collection of threshold functions, each expressed by an R-DNF formula. This leads to efficient PAC-learning algorithms for this class, as well as testing algorithms with running time independent of the size of the domain.

Swastik Kopparty

Rutgers

**Abstract:**
Multiplicity Codes allow one to encode data with just an epsilon
fraction redundancy, so that even if a constant fraction of the
encoded bits are corrupted, any one bit of the original data can
be recovered in sublinear time with high probability. These codes
were introduced and studied recently in joint work with Shubhangi
Saraf and Sergey Yekhanin.

I will talk about a new result showing that multiplicity codes also tolerate a large fraction of errors:

- They can achieve "list-decoding capacity".
- They can be locally list-decoded beyond half their minimum distance. In particular, we give the first polynomial time algorithms for decoding multiplicity codes upto half their minimum distance/

The first of these results is based on solving some kinds of algebraic differential equations. The second is based on a family of algebraically repelling "space-filling" curves.

Ilias Diakonikolas

University of Edinburgh

**Abstract:**
We initiate the study of **inverse** problems in approximate uniform
generation, focusing on uniform generation of satisfying assignments
of various types of Boolean functions. In such an inverse problem, the
algorithm is given uniform random satisfying assignments of an unknown
function f belonging to a class C of Boolean functions, and the goal
is to output a probability distribution D which is [;\epsilon;]-close, in total
variation distance, to the uniform distribution over [;f^{-1}(1);].

-- Positive results: We prove a general positive result establishing sufficient
conditions for efficient inverse approximate uniform generation for a class
C. We define a new type of algorithm called a **densifier** for C,
and show (roughly speaking) how to combine (i) a densifier, (ii) an
approximate counting / uniform generation algorithm, and (iii) a Statistical
Query learning algorithm, to obtain an inverse approximate uniform
generation algorithm. We apply this general result to obtain a
poly(n,1/[;\epsilon;])-time algorithm for the class of halfspaces; and a
quasipoly(n,1/[;\epsilon;])-time algorithm for the class of poly(n)-size
DNF formulas.

-- Negative results: We prove a general negative result establishing that the existence of certain types of signature schemes in cryptography implies the hardness of certain inverse approximate uniform generation problems. This implies that there are no {subexponential}-time inverse approximate uniform generation algorithms for 3-CNF formulas; for intersections of two halfspaces; for degree-2 polynomial threshold functions; and for monotone 2-CNF formulas.

Finally, we show that there is no general relationship between the complexity of the "forward" approximate uniform generation problem and the complexity of the inverse problem for a class C -- it is possible for either one to be easy while the other is hard.

The talk will be based on joint work with Anindya De (Berkeley) and Rocco Servedio (Columbia).

Vijay V. Vazirani

Georgia Tech

**Abstract:**
For all practical purposes, the Micali-Vazirani algorithm, discovered
in 1980, is still the most efficient known maximum matching algorithm
(for very dense graphs, slight asymptotic improvement can be obtained
using fast matrix multiplication). However, this has remained a "black
box" result for the last 32 years. We hope to change this with the help
of a recent paper giving a simpler proof and exposition of the algorithm:

http://arxiv.org/abs/1210.4594

In the interest of covering all the ideas, we will assume that the audience is familiar with basic notions such as augmenting paths and bipartite matching algorithm.

Anindya De

Berkeley

**Abstract:**
We give a new and simple induction based proof of the well-known
'Majority is Stablest' theorem. Unlike the previous proof, the new
proof completely avoids use of sophisticated tools from Gaussian
analysis. As the main application, we show that a constant number
of rounds of the Lasserre hierarchy can refute the Khot-Vishnoi
instance of MAX-CUT.

Joint work with Elchanan Mossel and Joe Neeman.

John Lai

Harvard University

**Abstract:**
Cake cutting is a common metaphor for the division of a heterogeneous
divisible good. There are numerous papers that study the problem of
fairly dividing a cake; a small number of them also take into account
self-interested agents and consequent strategic issues, but these papers
focus on fairness and consider a strikingly weak notion of truthfulness.
In this paper we investigate the problem of cutting a cake in a way that
is truthful, Pareto-efficient, and fair, where for the first time our notion
of dominant strategy truthfulness is the ubiquitous one in social choice
and computer science. We design both deterministic and randomized
cake cutting mechanisms that are truthful and fair under different
assumptions with respect to the valuation functions of the agents.

Raghu Meka

Institute for Advanced Study

**Abstract:**
Minimizing the discrepancy of a set system is a fundamental problem
in combinatorics. One of the cornerstones in this area is the celebrated
six standard deviations result of Spencer (AMS 1985): In any system of
n sets in a universe of size n, there always exists a coloring which
achieves discrepancy [;6\sqrt{n};]. The original proof of Spencer was
existential in nature, and did not give an efficient algorithm to find
such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010)
gave an efficient algorithm which finds such a coloring. In this work we
give a new randomized algorithm to find a coloring as in Spencer's result
based on a restricted random walk we call "Edge-Walk". Our algorithm
and its analysis use only basic linear algebra and is "truly" constructive
in that it does not appeal to the existential arguments, giving a new
proof of Spencer's theorem and the partial coloring lemma.

Joint work with Shachar Lovett.

Kobbi Nissim

Ben-Gurion University

**Abstract:**
The notion of private learning [Kasiviswanathan el al. 08] is a combination
of PAC (probably approximately correct) learning [Valiant 84] and differential
privacy [Dwork et al. 06]. Kasiviswanathan el al. presented a generic
construction of private learner for finite concept classes, where the sample
complexity depends logarithmically in the size of the concept class. For
concept classes of small VC dimension, this sample complexity is significantly
larger than what is sufficient for non-private learning.

In this talk I will present some of the known bounds on the sample complexity of private learners, and a recent characterization of the sample complexity as a combinatorial measure of the learned concept class.

Joint work with Amos Beimel and Uri Stemmer, ITCS 2013.

Li-Yang Tan

Columbia University

**Abstract:**
In the past few decades ideas and techniques from information theory
have been successfully applied to solve problems in numerous areas of
theoretical computer science: data structures, communication
complexity, gap amplification, compression, PRGs, extractors, etc. In
this talk I will describe on-going work exploring connections between
information theory and the analysis of Boolean functions, and give a
few examples of how information-theoretic methods can be used to prove
(and sometimes sharpen) classical isoperimetric and hypercontractive
inequalities.

Joint works with Eric Blais (MIT) and Andrew Wan (Harvard).

Contact

There is a mailing list for the reading group. General information about the mailing list (including how to subscribe yourself to it) is available here. If you want to unsubscribe or change your options, send email to theoryread-request@lists.cs.columbia.edu with the word `help' in the subject or body (don't include the quotes), and you will get back a message with instructions.

Comments on this page are welcome; please send them to
` xichen-at-cs.columbia.edu
`