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
]]>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
]]>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
]]>
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
]]>