Now showing items 1-20 of 151

• #### 100 Years of Digital Data ﻿

(Georgia Institute of Technology, 2008-01-23)
The Information Age has brought with it a deluge of digital data. Current estimates are that in 2006, 161 exabytes (10¹⁸ bytes) of digital data were created from cell phones, computers, iPods, DVDs, sensors, satellites, ...
• #### 86 Years of Ramsey R(3,k) (and counting!) ﻿

(2017-11-03)
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 ...
• #### Abstract polymer models, the cluster expansion, and applications ﻿

(2019-05-06)
Will introduces abstract polymer models and the cluster expansion from statistical physics. He describes some of the original applications of these tools in statistical physics to understand phase transitions in lattice ...
• #### Accurate Inference of Phylogenetic Relationships from Multi-locus Data ﻿

(Georgia Institute of Technology, 2010-03-09)
Accurate inference of phylogenetic relationships of species, and understanding their relationships with gene trees are two central themes in molecular and evolutionary biology. Traditionally, a species tree is inferred by ...
• #### The Aha! Moment: From Data to Insight ﻿

(Georgia Institute of Technology, 2014-02-07)
The amount of data in the world is increasing at incredible rates. Large-scale data has potential to transform almost every aspect of our world, from science to business; for this potential to be realized, we must turn ...
• #### Algorithmic Discrete Choice ﻿

(2019-11-04)
In this talk we consider random utility models for discrete choice. In discrete choice, the task is to select exactly one element from a discrete set of alternatives. We focus on algorithmic questions in this and related ...
• #### Algorithmic Pricing ﻿

(Georgia Institute of Technology, 2013-04-08)
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 ﻿

(2018-05-16)
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 non-constructive. In this ...
• #### Algorithms for Circuits and Circuits for Algorithms ﻿

(Georgia Institute of Technology, 2011-11-11)
Connections have been recently developed between the existence of non-trivial circuitanalysis algorithms and proofs of circuit size lower bounds. Algorithms that can check whether a given circuit from some class satisfies ...
• #### An almost-linear time algorithm for uniform random spanning tree generation ﻿

(2018-02-12)
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 ...
• #### Amplification Theorems for Differentially Private Machine Learning ﻿

(2019-04-01)
A rigorous foundational approach to private data analysis has emerged in theoretical computer science in the last decade, with differential privacy and its close variants playing a central role. We have recently been able ...
• #### An analytical GPU performance model and a dynamic compilation system for CPU/GPU systems ﻿

(Georgia Institute of Technology, 2009-09-11)
• #### Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple ﻿

(2016-11-28)
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 ...
• #### Approximating Profile Maximum Likelihood Efficiently ﻿

(2019-09-09)
Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single estimator that maximizes ...
• #### Approximation Schemes for Planar Graphs: A Survey of Methods ﻿

(2017-03-27)
In addressing an NP-hard 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. ...
• #### Automating Topology Aware Task Mapping on Large Supercomputers ﻿

(Georgia Institute of Technology, 2010-03-30)
Parallel computing is entering the era of petascale machines. This era brings enormous computing power to us and new challenges to harness this power efficiently. Machines with hundreds of thousands of processors already ...
• #### Black Holes, Firewalls, and the Limits of Quantum Computers ﻿

(2017-12-04)
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 ...
• #### Blocked Plane Rotations for Band Reduction and Sparse SVD ﻿

(Georgia Institute of Technology, 2009-08-26)
With the success of Basic Linear Algebra Subroutines (BLAS) in using the memory efficiently, the algorithms with vector operations (BLAS2) have given way to algorithms with matrix operations (BLAS3). In some cases, BLAS3 ...
• #### Bloom Filters, Cuckoo Hashing, Cuckoo Filters, Adaptive Cuckoo Filters, and Learned Bloom Filters ﻿

(2018-11-26)
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 ...
• #### A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times ﻿

(2017-11-27)
There are several works characterizing the total-variation 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 ...