Abstract:
In the first part we will analyze extended formulations of polytopes and we solve a 20-year old problem posed by Yannakakis: there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope.
In view of the aforementioned lower bounds we then turn our attention, in the second part, to approximate extended formulations which approximately project to the desired polytope. We develop a framework for proving approximation limits of polynomial-size linear programs. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^{1/2−ε})-approximations for CLIQUE require linear programs of size 2^{n^Ω(ε)}. Moreover, we establish a similar result for approximations of semidefinite programs by linear programs.
This is joint work with G ́abor Braun, Samuel Fiorini, Serge Massar, David Steurer, Hans Raj Tiwary, and Ronald de Wolf
]]>
Abstract:
A basic problem in classifying, or searching for similar objects in, a large set of geometric objects is computing similarity between two objects. This has led to extensive work on computing geometric similarity between two objects. This talk discusses some old and some new geometric algorithms for computing similarity between two point sets, with an emphasis on transportation and Frechet distance. The talk will also touch upon a few open problems in this area.
]]>]]>
The Internet is composed of tens of thousands of interconnected diverse, self-owned smaller networks, called Autonomous Systems (ASes). These ASes engage in strategic decision making to maximize their profits, reliability and performance. The business agreements (e.g. peering and transit) between these ASes play a major role in how the Internet is structured today and how it evolves over time. This important aspect creates a strong connection between networking research, economics and game-theoretic network formation models.
The aim of this workshop is to bring together these different communities from research (Internet Topology Measurement, Economics, Theoretical Computer Science, Network Science) and related industry (ISPs, Content Providers, CDNs etc.) to help narrow the gap between research and operational practice.
]]>
]]>
Abstract
A substantial part of extremal combinatorics studies relations existing between densities with which given combinatorial structures (fixed size ``templates'') may appear in unknown (and presumably very large) structures of the same type.
Using basic tools and concepts from algebra, analysis and measure theory, we develop a general framework that allows to treat all problems of this sort in an uniform way and reveal mathematical structure that is common for many known arguments in the area. The backbone of this structure is made by certain commutative algebras depending on the problem in question.
Once understood, it gives rise to the possibility of computer-aided theorem proving in this area based upon semi-definite programming.
In this talk I will give a general impression of how things work in this framework, and we will pay a special attention to concrete applications of our methods.
]]>
Abstract:
In many applications, we face the challenge of modeling the interactions between multiple observations. A popular and successful approach in machine learning and AI is to hypothesize the existence of certain latent (or hidden) causes which help to explain the correlations in the observed data. The (unsupervised) learning problem is to accurately estimate a model with only samples of the observed data. For example, in document modeling, we may wish to characterize the correlational structure of the "bag of words" in documents. Here, a standard model is to posit that documents are about a few topics (the hidden variables) and that each active topic determines the occurrence of words in the document. The learning problem is, using only the observed words in the documents (and not the hidden topics), to estimate the topic probability vectors (i.e discover the strength by which words tend to appear under different topcis). In practice, a broad class of latent variable models is most often fit with either local search heuristics (such as the EM algorithm) or sampling based approaches.
This talk will discuss how generalizations of standard linear algebra tools (e.g. spectral methods) to tensors provide provable and efficient estimation methods for various latent variable models (under appropriate assumptions), including mixtures of Gaussians models, hidden Markov models, topic models, latent Dirichlet allocation, latent parse tree models (PCFGs and dependency parsers), and models for communities in social networks. The talk will also briefly discuss how matrix and tensor decomposition methods can be used for the structure learning problem of determining both the existence of certain hidden causes and the underlying graphical structure between these hidden causes and the observed variables.
Title: Diameter of Polyhedra: Abstractions, new upper bounds and open problems
Abstract:
One of the most prominent mysteries in convex geometry is the question whether the diameter of a polyhedron is bounded by a polynomial in the number of facets. The gap between the best known lower bound (linear) and the best known upper bound (n^{log d} by Kalai and Kleitman) is impressive.
After Francisco Santos refuted the classical Hirsch conjecture in 2010, the polynomial Hirsch conjecture, stating that the answer to the question above is "Yes", has received considerable attention. In this talk I present the best known bounds mentioned above in a very simple abstract setting that does not involve any geometry. The polynomial Hirsch conjecture is also open in this abstract setting. I furthermore show polynomial upper bounds on the diameter of polyhedra that are defined by matrices with small sub-determinants and close with open problems.
]]>Abstract:
Expander graphs are known to facilitate effective routing and most real-world networks have expansion properties. At the other extreme, it has been shown that in some special graphs, removing certain edges can lead to more efficient routing. This phenomenon is known as Braess¹s paradox and is usually regarded as a rare event. In contrast to what one might expect, we show that Braess¹s paradox is ubiquitous in expander graphs. Specifically, we prove that Braess¹s paradox occurs in a large class of expander graphs with continuous convex latency functions. Our results extend previous work which held only when the graph was both denser and random and for random linear latency functions. We identify deterministic sufficient conditions for a graph with as few as a linear number of edges, such that Braess¹s Paradox almost always occurs, with respect to a general family of random latency functions. (Joint work with Fan Chung and Wenbo Zhao.)
]]>
Abstract:
In many applications, fairly fast clustering algorithms seem to yield the desired solution. Theoretically, two types of assumptions lead to provably fast algorithms for clustering:
(i) stochastic (mixture) models of data and (ii) uniqueness of optimal solution even under perturbations of data. We show that under an assumption weaker than either of these, Lloyd's (k-means) algorithm converges to the correct solution. We apply the result to the planted clique problem.
Joint work with Amit Kumar.
]]>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. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure. 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 Raghu Meka
]]>Abstract:
The study of random Cayley graphs of finite groups is related to the investigation of Expanders and to problems in Combinatorial Number Theory and in Information Theory. I will discuss this topic, describing the motivation and focusing on the question of estimating the chromatic number of a random Cayley graph of a given group with a prescribed number of generators. The investigation of this problem combines combinatorial, algebraic and probabilistic tools. Several intriguing questions that remain open will be mentioned as well.
]]>
Title: On graphs, arithmetic progressions and communication
Abstract:
Tools from Extremal Graph Theory are helpful in the study of problems in Additive Number Theory, Theoretical Computer Science, and Information Theory. I will illustrate this fact by several closely related examples focusing on a recent one in a joint paper with Moitra and Sudakov.
Speaker: Persi Diaconis
Title: "An Introduction to additive combinatorics via 'carries'"
Abstract
When numbers are added in the usual way, "carries" occur. The chance of a carry is about .45 (base 10). There are other choices of digits that lead to fewer carries (balanced digits). These balanced systems turn out to be best (fewest carries). Showing this requires an excursion into additive combinatorics a la Gowers-Green-Szemeredi-Tao. This is joint work with Shao and Soundarajan.
See All Workshop presentations and videos here
Schedule
The workshop on Computation and Phase Transitions brings together researchers from Statistical Physics, Probability, Discrete Mathematics, and Theoretical Computer Science. The convergence of ideas from these fields has led to breakthroughs in our understanding of the limits of computation for approximate counting and random sampling problems. For example, recent algorithmic work of Dror Weitz and inapproximability work of Allan Sly shows that the computational complexity of approximately counting weighted independent sets in general graphs undergoes a phase transtion on trees.
http://www.cc.gatech.edu/~vigoda/new-workshop/
]]>
We consider a switched (queueing) network in which there are constraints on which queues may be served simultaneously; such net-works have been used to effectively model input-queued switches and wireless networks. The scheduling policy for such a network specifies which queues to serve at any point in time, based on the current state or past history of the system. As the main result, we provide a new class of online scheduling policies that achieve optimal average queue-size scaling for a class of switched networks including input-queued switches. In particular, it establishes the validity of a long-standing conjecture about optimal queue-size scaling for input-queued switches.
This is based on joint work with Neil Walton (Univ of Amsterdam) and Yuan Zhong (MIT).
Bio
Devavrat Shah is currently a Jamieson associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS) and Operations Research Center (ORC). His research focus is on theory of large complex networks which includes network algorithms and statistical inference. He has received 2008 ACM Sigmetrics Rising Star Award and 2010 Erlang Prize from the Applied Probability Society of INFORMS. He currently serves as an associate editor of Operations Research.
]]>The objective of this workshop is to bring together leading researchers/developers from industry with leading researchers from academia to discuss challenges, opportunities and new trends in logistics, material handling, optimization, and related algorithms.
http://robotics.gatech.edu/content/arc-rim-industry-day
]]>
Abstract: Systems wherein strategic agents compete for limited resources are ubiquitous: the economy, computer networks, social networks, congestion networks, etc. Auction theory governs the design and analysis of these systems. I will describe a method for using approximation in auction theory to identify simple, practical, and robust auction mechanisms that perform nearly as well as the complex optimal ones. A main goal of this approach is to understand the extent to which important intuition from optimal auctions for ideal models extends to approximately optimal auctions for more realistic models.
Auction theory is well understood only in ideal models where agents have single-dimensional, linear preferences. I.e., each agent has a value for receiving a service and her utility is the difference between her value and her payment. For these models optimal auctions can be interpreted as "marginal revenue" maximizers (Myerson, 1981; Bulow and Roberts 1989). In more realistic models, i.e., where bidders have multi-dimensional preferences for different outcomes or non-linear utility, similar intuitive characterizations are unknown. Understanding good auctions for these environments is considered to be the main challenge in auction theory. In these more realistic environments maximizing marginal revenue may not be optimal, and furthermore, there is sometimes no direct way to implementing the marginal revenue maximization mechanism. I will present two results: I will give procedures for implementing marginal revenue maximization in general, and I will show that marginal revenue maximization is approximately optimal. The approximation factor smoothly degrades in a term that quantifies how far the environment is from an ideal one (i.e., where marginal revenue maximization is optimal).
Joint work with Saeed Alaei, Hu Fu, Nima Haghpanah, and Azarakhsh Malekian.
]]>Abstract: In this talk I present an iterative combinatorial auction that offers modularity in the choice of price structure, drawing on ideas from kernel methods and the primal-dual paradigm of auction design. The auction is able to automatically detect, as the rounds progress, whether price expressiveness must be increased to clear the market, and converges to a sparse representation of nonlinear clearing prices. I show that by introducing regularization the auction is able to compute approximate truth-inducing payments in just a single run, in contrast to VCG payments which require as many runs as there are bidders. An empirical evaluation demonstrates the performance gains that can be obtained in allocative efficiency, revenue, and rounds to convergence through various configurations of the auction design against established linear- and bundle- price auctions.
]]>Abstract: A subgraph H of a weighted graph G is a t-spanner of G provided that for every edge xy in G, the weight of the shortest path between x and y in H is at most t times the weight of xy. It is known that the Delaunay triangulation of a point set P (where the empty region is an equilateral triangle) is a 2-spanner of the complete Euclidean graph. We present a new and simple proof of this spanning ratio that allows us to route competitively on this graph. Specifically, we present a deterministic local routing scheme that is guaranteed to find a short path between any pair of vertices in this Delaunay triangulation. We guarantee that the length of the path is at most 5/sqrt(3) times the Euclidean distance between the pair of vertices. Moreover, we show that no local routing scheme can achieve a better competitive spanning ratio thereby implying that our routing scheme is optimal. This is somewhat surprising since the spanning ratio is 2.
]]>Title: Multidimensional Revenue Optimization
In his seminal paper, Myerson [1981] provided a revenue-optimal auction for a seller who is looking to sell a single item to multiple bidders. Extending this auction to simultaneously selling multiple heterogeneous items has been one of the central problems in Mathematical Economics. We provide such an extension that is also computationally efficient.
(joint work with Yang Cai and Matt Weinberg)
]]>Videos of all the tutorial sessions:
See all workshop presentations and videos
]]>For a {0,1}-valued matrix M let CC(M) denote the deterministic communication complexity of the boolean function associated with M. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC(M) <= log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank of M over the field of real numbers.
We show that CC(M) <= c rank(M)/ log rank(M) for some absolute constant c, assuming a well-known conjecture from additive combinatorics, known as the Polynomial Freiman-Ruzsa (PFR) conjecture.
Our proof is based on the study of the "approximate duality conjecture" which was recently suggested by Ben-Sasson and Zewi [STOC 2011], and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, and this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995].
Joint work with Shachar Lovett and Noga Zewi
]]>