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.
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
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
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.
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).
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.
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.
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).
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.
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:
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.
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).
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.
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.
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.
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.
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.
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).
Comments on this page are welcome; please send them to xichen-at-cs.columbia.edu