Browsing ARC Talks and Events by Title
Now showing items 120 of 63

86 Years of Ramsey R(3,k) (and counting!)
(20171103)The search for the asymptotics of the Ramsey function R(3,k) has a long and fascinating history. It begins in the hill country surrounding Budapest and winding over the decades through Europe, America, Korea and Rio de ... 
Algorithmic PirogovSinai theory
(20181105)We develop efficient algorithms to approximate the partition function and sample from the hardcore and Potts models on lattices at sufficiently low temperatures in the phase coexistence regime. In contrast, the Glauber ... 
Algorithmic Pricing
(Georgia Institute of Technology, 20130408)Pricing and allocating goods to buyers with complex preferences in order to maximize some desired objective (e.g., social welfare or profit) is a central problem in Algorithmic Mechanism Design. In this talk I will discuss ... 
An algorithmic version of Banaszczyk's discrepancy theorem
(20180516)In the 90's Banaszczyk developed a very powerful method for discrepancy problems, that goes beyond the partial coloring method. His result was based on deep results from convex geometry and was nonconstructive. In this ... 
An almostlinear time algorithm for uniform random spanning tree generation
(20180212)We give an $m^{1+o(1)}\beta^{o(1)}$time algorithm for generating uniformly random spanning trees in weighted graphs with maxtomin weight ratio $\beta$. In the process, we illustrate how fundamental tradeoffs in graph ... 
Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple
(20161128)We show how to perform sparse approximate Gaussian elimination for Laplacian matrices. We present a simple, nearly linear time algorithm that approximates a Laplacian by a matrix with a sparse Cholesky factorization – the ... 
Approximation Schemes for Planar Graphs: A Survey of Methods
(20170327)In addressing an NPhard problem in combinatorial optimization, one way to cope is to use an approximation scheme, an algorithm that, for any given ϵ>0, produces a solution whose value is within a 1+ϵ factor of optimal. ... 
Black Holes, Firewalls, and the Limits of Quantum Computers
(20171204)Quantum computers are proposed devices that would exploit quantum mechanics to solve certain specific problems dramatically faster than we know how to solve them with today's computers. In the popular press, quantum ... 
Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters
(20181126)I will go over some of my past and present work on hashingbased data structures. After presenting some background on Bloom filters and cuckoo hashing, we will describe cuckoo filters, an efficient data structure for ... 
A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times
(20171127)There are several works characterizing the totalvariation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast, there is no known analog ... 
The Complexity of Learning Neural Networks
(20171030)The empirical successes of neural networks currently lack rigorous theoretical explanation. A first step might be to show that data generated by neural networks with a single hidden layer, smooth activation functions and ... 
A Computer Science View of the Brain
(Georgia Institute of Technology, 20170315)Computational perspectives on scientific phenomena have often proven to be remarkably insightful. Rapid advances in computational neuroscience, and the resulting plethora of data and models highlight the lack of an ... 
A Constant‐Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem
(Georgia Institute of Technology, 20170921)We give a constantfactor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured ... 
The Contextual Bandits Problem: Techniques for Learning to Make HighReward Decisions
(20171030)We consider how to learn through experience to make intelligent decisions. In the generic setting, called the contextual bandits problem, the learner must repeatedly decide which action to take in response to an observed ... 
Cutoff with window for the random to random shuffle
(20180517)Cutoff is a remarkable property of many Markov chains in which they after number of steps abruptly transition in a smaller order window from an unmixed to a mixed distribution. Most random walks on the symmetric group, ... 
Decay of correlations and nonlocal Markov chains
(20171030)In this talk we consider Markov chains for spin systems on the integer lattice graph Z^d. It has been well known since pioneering work from the early 1990’s that a certain decay of correlation property, known as strong ... 
Differentially Private Analysis of Graphs
(20161107)Many types of data can be represented as graphs, where nodes correspond to individuals and edges capture relationships between them. Examples include datasets capturing “friendships” in an online social network, financial ... 
Distributed PCP Theorems for Hardness of Approximation in P
(20171106)We present a new model of probabilistically checkable proof (PCP), which we call "Distributed PCP": A satisfying assignment (x in {0,1}^n) to a CNF formula is shared between two parties (Alice knows x_1, ... x_{n/2}, ... 
Entropy, LogConcavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
(20180430)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 ... 
Explicit TwoSource Extractors and Resilient Functions
(20161114)We explicitly construct an extractor for two independent sources on n bits, each with minentropy at least log^C n for a large enough constant C. Our extractor outputs one bit and has error n^{\Omega(1)}. The best previous ...