## Columbia Theory Seminar, Fall 2012

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.

• Friday, September 14, 11:30, CSB 453: Dana Ron: A Near Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size (Abstract)
• Friday, October 5, 11:30, CSB 453: Dimitris Paparas: The Complexity of Finding a Market Equilibrium for CES and other types of Markets (Abstract)
• Friday, October 12, 11:30, CSB 453: Lirong Xia: A Manipulability Dichotomy Theorem for Generalized Scoring Rules (Abstract)
• Thursday, October 18, 15:00, CSB 453 (note unusual time and date): Jason Hartline: The Theory of Crowdsourcing Contests (Abstract)
• Friday, October 19, 10:30, CSB 453 (note unusual time): Virginie Lerays: Lower bounds on information complexity via zero-communication protocols and applications (Abstract)
• Friday, October 19, 11:30, CSB 453: Oded Regev: Non-commutative extensions of Grothendieck's inequality (Abstract)
• Thursday, October 25, 15:00, CSB 453 (note unusual time and date): David Witmer: Sparsest Cut on Bounded Treewidth Graphs (Abstract)
• Friday, October 26, 11:30, CSB 453: Grigory Yaroslavtsev: Learning and Testing Submodular Functions (Abstract)
• Friday, November 2, 11:30, CSB 453: Swastik Kopparty: List-Decoding Multiplicity Codes (Abstract)
• Thursday, November 15, 15:00, CSB 477 (Open meeting area) (note unusual place, time, and date): Ilias Diakonikolas: Inverse Problems in Approximate Uniform Generation (Abstract)
• Wednesday, November 28, 15:00, CSB 477 (Open meeting area) (note unusual place, time, and date): Vijay V. Vazirani: Matching: A New Proof for an Ancient Algorithm (Abstract)
• Wednesday, December 5, 15:00, CSB 477 (Open meeting area) (note unusual place, time, and date): Anindya De: Discrete proof of Majority is Stablest and applications to Semidefinite programming (Abstract)
• Thursday, December 6, 15:00, CSB 453 (note unusual time and date): John Lai: Truth, Justice, and Cake Cutting (Abstract)
• Friday, December 7, 11:30, CSB 453: Raghu Meka: Constructive Discrepancy Minimization by Walking on the Edges (Abstract)
• Friday, December 14, 12:00, CSB 477 (Open meeting area) (note unusual place and time): Kobbi Nissim: Characterizing the Sample Complexity of Private Learners (Abstract)
• Wednesday, December 19, 15:00, CSB 453 (note unusual time and date): Li-Yang Tan: Isoperimetric and hypercontractive inequalities via the entropy method (Abstract)

• ### Talk Abstracts

Friday, September 14:
A Near Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
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

Friday, October 5:
The Complexity of Finding a Market Equilibrium for CES and other types of Markets
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

Friday, October 12:
A Manipulability Dichotomy Theorem for Generalized Scoring Rules
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.

Thursday, October 18:
The Theory of Crowdsourcing Contests
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).

Friday, October 19:
Lower bounds on information complexity via zero-communication protocols and applications
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.

Friday, October 19:
Non-commutative extensions of Grothendieck's inequality
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.

Thursday, October 25:
Sparsest Cut on Bounded Treewidth Graphs
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).

Friday, October 26:
Learning and Testing Submodular Functions
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.

Friday, November 2:
List-Decoding Multiplicity Codes
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:

1. They can achieve "list-decoding capacity".
2. 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/
In simple terms, these are algorithms for interpolating a polynomial given evaluations of it and its derivatives, even if many of the given evaluations are wrong.

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.

Thursday, November 15:
Inverse Problems in Approximate Uniform Generation
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).

Wednesday, November 28:
Matching: A New Proof for an Ancient Algorithm
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:

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.

Wednesday, December 5:
Discrete proof of Majority is Stablest and applications to Semidefinite programming
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.

Thursday, December 6:
Truth, Justice, and Cake Cutting
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.

Friday, December 7:
Constructive Discrepancy Minimization by Walking on the Edges
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.

Friday, December 14:
Characterizing the Sample Complexity of Private Learners
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.

Wednesday, December 19:
Isoperimetric and hypercontractive inequalities via the entropy method
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 xichen-at-cs-dot-columbia-dot-edu if you want to volunteer to give a talk (especially for students!). The talk can be about your or others' work. It can be anything from a polished presentation of a completed result, to an informal black-board presentation of an interesting topic where you are stuck on some open problem. It should be accessible to a general theory audience. I will be happy to help students choose papers to talk about.
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