Venkat Guruswami
Monday, December 3, 2018
Klaus 1116E - 11:00 am
Title: The polymorphic gateway between structure and algorithms: Beyond CSPs
Abstract: What underlying mathematical structure (or lack thereof) in a computational problem governs its efficient solvability (or dictates its hardness)? In the realm of constraint satisfaction problems (CSPs), the algebraic dichotomy theorem gives a definitive answer: a polynomial time algorithm exists when there are non-trivial local operations called polymorphisms under which the solution space is closed; otherwise the problem is NP-complete. Inspired and emboldened by this, one might speculate a broader polymorphic principle: if there are interesting ways to combine solutions to get more solutions, then the problem ought to be tractable (with context dependent interpretations of "interesting" and "tractable”).
Beginning with some background on the polymorphic approach to understanding the complexity of constraint satisfaction, the talk will discuss some extensions beyond CSPs where the polymorphic principle seems promising (yet far from understood). Specifically, we will discuss promise CSPs where one is allowed to satisfy a relaxed version of the constraints (a framework that includes important problems like approximate graph coloring and discrepancy minimization), and the potential and challenges in applying the polymorphic framework to them. Another interesting direction is fine-grained complexity, where partial polymorphisms govern the runtime of fast exponential-time algorithms. Our inquiries into these directions also reveal some interesting connections to optimization, such as algorithms to solve LPs over different rings (like integers adjoined with sqrt{2}), and a random-walk based algorithm interpolating between 0-1 and linear programming, generalizing Schöning's famous (4/3)^n time algorithm for 3-SAT.
Based on a body of work with Joshua Brakensiek.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Michael Mitzenmacher
Monday, November 26, 2018
Klaus 1116 East – 11:00 am
Title: Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters
Abstract: I will go over some of my past and present work on hashing-based data structures. After presenting some background on Bloom filters and cuckoo hashing, we will describe cuckoo filters, an efficient data structure for approximate set membership that improves on the well-known Bloom filter. We then discuss recent work on how to make cuckoo filters adaptive in response to false positives, which can be important for many practical problems. Finally, I will present some very recent work on how to possibly improve Bloom filters and related data structures using machine learning techniques.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Sampath Kannan
Monday, October 29, 2018
Klaus 1116 East – 11:00 am
Title: Fairness in Algorithmic Decision Making
Abstract: In this talk we survey some formulations of fairness requirements for decision making under uncertainty. We then discuss results from 3 recent papers:
1) Treating individuals fairly is not in conflict with long-term scientific learning goals if the population is sufficiently diverse.
2) When there is a pipeline of decisions, end-to-end fairness is impossible to achieve even in a very simple model.
3) Exploiting the knowledge acquired by others can unfairly advantage the free rider.
These papers are joint work with a number of co-authors:
Christopher Jung, Neil Lutz, Jamie Morgenstern, Aaron Roth, Bo Waggoner, Steven Wu, and Juba Ziani
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Mary Wootters
Monday, October 1, 2018
MiRC Pettit 102A&B - 11:00 am
Title: Improved Decoding of Folded Reed-Solomon and Multiplicity Codes
Abstract: List-decoding is an important primitive in the theory of error correcting codes, and it has long been a goal to obtain explicit constructions of capacity-achieving, efficiently list-decodable codes. Folded Reed-Solomon Codes (Guruswami-Rudra 2008) and Multiplicity codes (Guruswami-Wang 2011, Kopparty 2012) are two such constructions. However, previous analysis of these codes could not guarantee optimal parameters. In particular, the “list-size” of these codes was only shown to be polynomial, while ideally it would be constant. Thus, over the past decade or so, there have been several modifications of these codes aimed at reducing the list size to constant. In this work, we show that in fact the list-sizes were constant all along, with no modifications required! Further, we use our result for univariate multiplicity codes to establish improved local list-decoding results for multivariate multiplicity codes.
In this talk, I’ll define all the terms in the paragraph above (in particular, no prior knowledge of error correcting codes is necessary!), and sketch the proofs of the results mentioned above.
Joint work with Swastik Kopparty, Noga Ron-Zewi, and Shubhangi Saraf.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Leslie Valiant
Monday, October 22, 2018
Klaus 1116 East & West – 11:00 am
Title: Where Computer Science Meets Neuroscience
Abstract: For some problems in science there are several plausible theories and it remains to experimenters to determine which of them, if any, are valid. There exist other problems for which, in contrast, no known theory is widely accepted as plausible. Currently computational neuroscience is a field full of opportunity that offers several fundamental problems of the latter kind. We shall discuss one of these problems: Over a lifetime the brain performs hundreds of thousands of individual cognitive acts, of a variety of kinds, including the formation of new associations. Each such act depends on past experience, and, in turn, can have long lasting effects on future behavior. It is difficult to reconcile such large scale capabilities, including fast reaction times on new inputs when using knowledge acquired at various earlier times, with the known resource constraints on cortex, such as low connectivity and low average synaptic strength. Here we shall describe an approach to this fundamental problem that attempts to explain these phenomena in terms of concrete algorithms for a model of computation that is faithful to the most basic quantitative resources.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Will Perkins
Monday, November 5, 2018
Klaus 1116 East – 11:00 am
Title: Algorithmic Pirogov-Sinai theory
Abstract: We develop efficient algorithms to approximate the partition function and sample from the hard-core and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In contrast, the Glauber dynamics are known to take exponential time to mix in this regime. Our algorithms are based on the cluster expansion and Pirogov-Sinai theory, classical tools from statistical physics for understanding phase transitions, as well as Barvinok's approach to polynomial approximation. Joint work with Tyler Helmuth and Guus Regts.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Tselil Schramm
Monday, September 24, 2018
MiRC Pettit 102 A&B – 11:00 am
Title: (Nearly) Efficient Algorithms for the Graph Matching Problem in Correlated Random Graphs
Abstract: The Graph Matching problem is a robust version of the Graph Isomorphism problem: given two not-necessarily-isomorphic graphs, the goal is to find a permutation of the vertices which maximizes the number of common edges. We study a popular average-case variant; we deviate from the common heuristic strategy and give the first quasi-polynomial time algorithm, where previously only sub-exponential time algorithms were known.
Based on joint work with Boaz Barak, Chi-Ning Chou, Zhixian Lei, and Yueqi Sheng.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Lap Chi Lau
Monday, October 15, 2018
Klaus 1116 East – 11:00 am
Title: The Paulsen problem, continuous operator scaling, and smoothed analysis
Abstract: The Paulsen problem is a basic open problem in operator theory. We define a continuous version of the operator scaling algorithm to solve this problem. A key step is to show that the continuous operator scaling algorithm converges faster in a perturbed input. To this end, we develop some new techniques in lower bounding the operator capacity, a concept introduced by Gurvits to analyze the operator scaling algorithm. The talk will be self-contained. Joint work with Tsz Chiu Kwok, Yin Tat Lee, and Akshay Ramachandran.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Anand Louis (Indian Inst. of Science)
Monday, September 10, 2018
Klaus 1116 East – 11:00 am
Title: On the complexity of clustering problems
Abstract: Euclidean k-means clustering, a problem having numerous applications, is NP-hard in the worst case but often solved efficiently in practice using simple heuristics. A quest for understanding the properties of real-world data sets that allow efficient clustering has lead to the notion of the perturbation resilience. In the first part of the talk, I'll describe an algorithm to recover the optimal k-means clustering in perturbation resilient instances.
In some cases, clustering with the k-means objective may result in a few clusters of very large cost and many clusters of small cost. This can be undesirable when we have a budget constraint on the cost of each cluster. Motivated by this, we study the "min-max k-means" clustering objective. In the second part of the talk, I'll show approximation algorithms for the min-max k-means problem.
Based on joint works with Amit Deshpande and Apoorv Vikram Singh.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Nima Anari
Monday, April 30, 2018
Klaus 1116 East – Noon
Title: Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
Abstract: We give a deterministic 2^O(rank) approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. Based on a lower bound of Azar et al., this is almost the best possible result assuming oracle access to independent sets of matroids.
There are two main ingredients in our result: For the first ingredient, we build upon recent results of Huh et al. and Adiprasito et al. on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. We expect that several new applications in approximation algorithms will be derived from this connection in future. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant. For the second ingredient, we use a general framework for approximate counting in discrete problems, based on convex optimization and sub-additivity of the entropy. For matroids, we prove that an approximate super-additivity of the entropy holds, yielding an approximation algorithm, by relying on log-concavity of the corresponding polynomials.
Joint work with Shayan Oveis Gharan and Cynthia Vinzant.
----------------------------------
Videos of recent talks are available at https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Alexandre Stauffer (Bath)
Monday, April 23, 2018
Klaus 1116 East - 11am
Title: Competition in randomly growing processes
Abstract: We consider random growth processes that compete for space over time.
This is by now a classical topic in probability theory. The usual situation is that when the two processes have different speeds of growth, then one of the processes wins against the other.
It is quite rare to find natural models where both processes coexist forever.
In this talk I will discuss a random growth model, which we introduced as a tool to studying a famous model of dendritic growth from physics.
This growth model can also be regarded as a model for blocking the spread of fake news in a network.
We will discuss the behavior of this processes, its phase transition and the occurrence of coexistence.
This is based on joint works with Elisabetta Candellero (Warwick) and Vladas Sidoravicius (NYU Shanghai).
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>
Yin Tat Lee
Friday, March 16, 2018
MiRC Pettit Rm 102A&B – 11:00 am
Title: l_p regression beyond self-concordance
Abstract: We consider the problem of linear regression where the l_2 norm loss (i.e., the usual least squares loss) is replaced by the l_p norm. We show how to solve such problems up to machine precision in O*(n^|1/2−1/p|) (dense) matrix-vector products and O*(1) matrix inversions, or alternatively in O*(n^|1/2−1/p|) calls to a (sparse) linear system solver. This improves the state of the art for any p not in {1,2,inf}. Furthermore we also propose a randomized algorithm solving such problems in input sparsity time, i.e., O*(Z+poly(d)) where Z is the size of the input and d is the number of variables. Such a result was only known for p=2. Finally we prove that these results lie outside the scope of the Nesterov-Nemirovski's theory of interior point methods by showing that any symmetric self-concordant barrier on the l_p unit ball has self-concordance parameter Ω~(n).
Joint work with Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, Yuanzhi Li
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Piotr Indyk (MIT)
Monday, March 5, 2018
Klaus 1116 East - 11am
Title: "Below P vs. NP: Conditional Quadratic-Time Hardness for Big Data Problems"
Abstract:
The theory of NP-hardness has been very successful in identifying problems that are unlikely to have general purpose polynomial time algorithms. However, many other important problems do have polynomial time algorithms, but large exponents in their time bounds can make them run for days, weeks or more. For example, quadratic time algorithms, although practical on moderately sized inputs, can become inefficient on problems that involve gigabytes or more of data. Although for many problems no subquadratic time algorithms are known, evidence of quadratic-time hardness has remained elusive.
In this talk, I will give an overview of recent research that aims to remedy this situation. In particular, I will describe hardness results for problems in string processing (e.g., edit distance computation or regular expression matching) and machine learning (e.g., support vector machines or batch gradient computation in neural networks). All of them have polynomial time algorithms, but despite an extensive amount of research, no near-linear time algorithms have been found for many variants of these problems. I will show that, under a natural complexity-theoretic conjecture, such algorithms do not exist. I will also describe how this framework has led to the development of new algorithms.
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>
Sanjeev Arora
Princeton University and Institute for Advanced Study
Friday, February 23, 2018
Klaus 2447 (classroom) at 11:00 am
Title: Toward theoretical understanding of deep learning
Abstract: This talk will be a survey of ongoing efforts to develop better theoretical understanding of deep learning, from expressiveness to optimization to generalization theory.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Xiaorui Sun (Microsoft Research)
Monday, March 12, 2018
Klaus 1116 East - 11am
Title: The Query Complexity of Graph Isomorphism: Bypassing Distribution Testing Lower Bounds
Abstract:
We study the edge query complexity of graph isomorphism in the property testing model for dense graphs. We give an algorithm that makes n^{1+o(1)} queries, improving on the previous best bound of O~(n^{5/4}). Since the problem is known to require \Omega(n) queries, our algorithm is optimal up to a subpolynomial factor.
While trying to extend a known connection to distribution testing, discovered by Fischer and Matsliah (SICOMP 2008), one encounters a natural obstacle presented by sampling lower bounds such as the $\Omega(n^{2/3})$-sample lower bound for distribution closeness testing (Valiant, SICOMP 2011). In the context of graph isomorphism testing, these bounds lead to an $n^{1+\Omega(1)}$ barrier for Fischer and Matsliah's approach. We circumvent these limitations by exploiting a geometric representation of the connectivity of vertices. An approximate representation of similarities between vertices can be learned with a near-linear number of queries and allows relaxed versions of sampling and distribution testing problems to be solved more efficiently.
Joint work with Krzysztof Onak
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>
Vivek Madan(UIUC)
Monday, February 19, 2018
Klaus 1116 East – 11:00 am
Title: Approximating Multicut and the Demand graph
Abstract: The Multicut problem is a generalization of the classical $s-t$ cut problem to multiple pairs. Given an edge-weighted directed or undirected supply graph G=(V,E), and k source-sink pairs (s1,t1),\dots,(sk,tk), the goal is to remove a minimum weight subset of edges in G such that all the given (si,ti) pairs are disconnected. Over the past 30 years, Multicut has attracted significant attention in approximation algorithms, and a variety of results have been obtained for general and special classes of supply graphs. Motivated by new applications, I study Multicut with a focus on the demand graph (graph with an edge set {(si,ti) \mid i \in [k]}). We obtain several new approximability and inapproximability results based on a labeling viewpoint of the problem.
1. Approximation algorithms: We present a unified 2-approximation algorithm for undirected multicut problem for tK2-free demand graphs when t is a fixed constant. For directed multiway cut we significantly simplify the 2-approximation algorithm of Naor and Zosin from twenty years ago; our rounding strategy yields a constant factor for much more general classes of demand graphs. For the problem of linear-k-cut (a special case of directed multicut which motivated this work), we show some initial results and prove a tight \sqrt{2}-approximation algorithm when k=3.
2. Hardness of approximation: We prove that for a class of demand graphs, undirected multicut admits a constant factor approximation algorithm iff the class is tK2-free for some constant t. For directed multicut, we prove that assuming the Unique Games Conjecture (UGC), hardness of approximation matches the flow-cut gap for any fixed bi-partite demand graph. As a consequence, we prove that for any fixed k \ge 2, there is no (k-eps) approximation algorithm for Multicut with k pairs, assuming UGC.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Greg Bodwin (MIT)
Friday, February 9, 2018
Skiles 005 - 1pm
Note the non-standard date/time
Title: The Distance Oracle Hierarchy
Abstract: A lot of well-studied problems in CS Theory are about making “sketches” of graphs that occupy much less space than the graph itself, but where the shortest path distances of the graph can still be approximately recovered from the sketch. For example, in the literature on Spanners, we seek a sparse subgraph whose distance metric approximates that of the original graph. In Emulator literature, we relax the requirement that the approximating graph is a subgraph. Most generally, in Distance Oracles, the sketch can be an arbitrary data structure, so long as it can approximately answer queries about the pairwise distance between nodes in the original graph.
Research on these objects typically focuses on optimizing the worst-case tradeoff between the quality of the approximation and the amount of space that the sketch occupies. In this talk, we will survey a recent leap in understanding about this tradeoff, overturning the conventional wisdom on the problem. Specifically, the tradeoff is not smooth, but rather it follows a new discrete hierarchy in which the quality of the approximation that can be obtained jumps considerably at certain predictable size thresholds. The proof is graph-theoretic and relies on building large families of graphs with large discrepancies in their metrics.
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>
Aaron Schild (Berkeley)
Monday, February 12, 2018
Klaus 1116 East – 11:00 am
Title: An almost-linear time algorithm for uniform random spanning tree generation
Abstract: We give an $m^{1+o(1)}\beta^{o(1)}$-time algorithm for generating uniformly random spanning trees in weighted graphs with max-to-min weight ratio $\beta$. In the process, we illustrate how fundamental tradeoffs in graph partitioning can be overcome by eliminating vertices from a graph using Schur complements of the associated Laplacian matrix.
Our starting point is the Aldous-Broder algorithm, which samples a random spanning tree using a random walk. As in prior work, we use fast Laplacian linear system solvers to shortcut the random walk from a vertex $v$ to the boundary of a set of vertices assigned to $v$ called a "shortcutter." We depart from prior work by introducing a new way of employing Laplacian solvers to shortcut the walk. To bound the amount of shortcutting work, we show that most random walk steps occur far away from an unvisited vertex. We apply this observation by charging uses of a shortcutter $S$ to random walk steps in the Schur complement obtained by eliminating all vertices in $S$ that are not assigned to it.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Di Wang (UC Berkeley/Georgia Tech)
Monday, February 5, 2018
Klaus 1116 East - 11:00 am
Title: Capacity Releasing Diffusion for Speed and Locality
Abstract: Diffusion and related random walk procedures on graphs are of central importance in many areas of machine learning, data analysis, and algorithm design. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread mass “too aggressively,” thereby failing to find the “right” clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both faster and stays more local than the classical probability mass diffusion.
The CRD Process follows a carefully-constructed push-relabel rule, using techniques that are well-known from flow-based graph algorithms. While flow and probability mass diffusion (or more generally, spectral methods) have a long history of competing to provide good graph decomposition, local methods are predominantly based on diffusion. Our CRD Process is the first primarily flow-based local method for locating low conductance cuts, and it has exhibited improved theoretical and empirical behavior over classical diffusion methods, e.g. PageRank.
--------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>
Yan Shuo Tan (Michigan)
Monday, January 22, 2018
Pettit Microelectonics Bldg.
Pettit Rm 102A - 2:00 pm
Title: Efficient algorithms for phase retrieval in high dimensions
Abstract: Mathematical phase retrieval is the problem of solving systems of rank-1 quadratic equations. Over the last few years, there has been much interest in constructing algorithms with provable guarantees. Both theoretically and empirically, the most successful approaches have involved direct optimization of non-convex loss functions. In the first half of this talk, we will discuss how SGD for one of these loss functions provably results in (rapid) linear convergence with high probability. In the second half of the talk, we will discuss a semidefinite programming algorithm that simultaneously makes use of a sparsity prior on the solution vector, while overcoming possible model misspecification.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>Cong Han Lim (Wisconsin)
Wednesday, January 17, 2018
Groseclose 402 - 10:00 am
Title: Towards Large-Scale Nonconvex/Stochastic Discrete Optimization
Abstract: Modern data analytics is powered by scalable mathematical optimization methods. For decision-making, we want to be able to solve large-scale mathematical problems that include discrete choices or structures. These can already be very challenging to solve exactly even when the objective and feasible region are convex. We want to be able to model more general concepts that naturally lead to huge or nonconvex formulations, such as robustness to uncertainty, economic ideas like economies of scale, and physical concepts in engineering applications such as power systems and water network design.
In this talk, I will present techniques for handling two such families of problems. I will demonstrate a new class of cutting planes for mixed-integer programs with separable concave costs and show that they can be combined with existing cuts for canonical mixed-integer linear sets. For stochastic mixed-integer programs, I will describe a new subgradient method for solving the dual decomposition that parallelizes significantly better than traditional subgradient on modern distributed and multi-core computer architectures. I will conclude by discussing some future directions in machine learning and (stochastic) mixed-integer programming.
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>