### CANCELLED for now: TBA by Prasad Tetali

- Series
- ACO Seminar
- Time
- Thursday, April 2, 2020 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Peter Winkler – Dartmouth College, NH

TBA

- You are here:
- GT Home
- Home
- News & Events

- Series
- ACO Seminar
- Time
- Thursday, April 2, 2020 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Peter Winkler – Dartmouth College, NH

TBA

- Series
- ACO Seminar
- Time
- Thursday, December 5, 2019 - 13:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Jinyoung Park – Rutgers University

I will introduce an isoperimetric inequality for the Hamming cube and some of its applications. The applications include a “stability” version of Harper’s edge-isoperimetric inequality, which was first proved by Friedgut, Kalai and Naor for half cubes, and later by Ellis for subsets of any size. Our inequality also plays a key role in a recent result on the asymptotic number of maximal independent sets in the cube.

This is joint work with Jeff Kahn.

- Series
- ACO Seminar
- Time
- Tuesday, September 24, 2019 - 13:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Arindam Khan – Computer Science and Automation, Indian Institute of Science, Bangalore – arindamkhan@iisc.ac.in

For online optimization, the input instance is revealed in a sequence of steps and, after each step, the algorithm has to take an immediate and irrevocable decision based on the previous inputs. Online algorithms produce a sequence of decisions for such problems without the complete information of the future. In the worst-case analysis of online optimization problems, sometimes, it is impossible to achieve any bounded competitive ratio. An interesting way to bypass these impossibility results is to incorporate a stochastic component into the input model. In the random-order arrival model, the adversary specifies an input instance in advance but the input appears according to a random permutation. The knapsack problem is one of the classical problems in combinatorial optimization: Given a set of items, each specified by its size and profit, the goal is to find a maximum profit packing into a knapsack of bounded capacity. The generalized assignment problem (GAP) includes, besides the knapsack problem, several important problems related to scheduling and matching. In this talk, we will present improved competitive algorithms under random-order arrival for these two problems. This is joint work with Susanne Albers and Leon Ladewig.

- Series
- ACO Seminar
- Time
- Friday, January 20, 2017 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Dion Gijswijt – TU Delft

A subset of $\mathbb{F}_3^n$ is called a \emph{cap set} if it does not contain three vectors that sum to zero. In dimension four, this relates to the famous card game SET: a cap set corresponds to a collection of cards without a SET. The cap set problem is concerned with upper bounds on the size of cap sets. The central question raised by Frankl, Graham and R\”odl is: do cap sets have exponentially small density? May last year, this question was (unexpectedly) resolved in a pair of papers by Croot, Lev, and Pach and by Ellenberg and myself in a new application of the polynomial method. The proof is surprisingly short and simple.

- Series
- ACO Seminar
- Time
- Tuesday, November 15, 2016 - 13:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Lutz Warnke – Cambridge University and Georgia Tech

Concentration inequalities are fundamental tools in probabilistic
combinatorics and theoretical computer science for proving that
functions of random variables are typically near their means. Of
particular importance is the case where f(X) is a function of
independent random variables X=(X_1,...,X_n). Here the well-known
bounded differences inequality (also called McDiarmid's or
Hoeffding--Azuma inequality) establishes sharp concentration if the
function f does not depend too much on any of the variables.
One attractive feature is that it relies on a very simple Lipschitz
condition (L): it suffices to show that |f(X)-f(X')| \leq c_k
whenever X,X' differ only in X_k. While this is easy to check,
the main disadvantage is that it considers worst-case changes
c_k, which often makes the resulting bounds too weak to be useful.
In this talk we discuss a variant of the bounded differences inequality
which can be used to establish concentration of functions f(X) where
(i) the typical changes are small although (ii) the worst case
changes might be very large.
One key aspect of this inequality is that it relies on a simple
condition that (a) is easy to check and (b) coincides with heuristic
considerations as to why concentration should hold. Indeed, given a
`good' event G that holds with very high probability, we essentially
relax the Lipschitz condition (L) to situations where G occurs. The
point is that the resulting typical changes c_k are often
much smaller than the worst case ones.
If time permits, we shall illustrate its application by considering the
reverse H-free process, where H is 2-balanced. We prove that the
final number of edges in this process is concentrated, and also determine
its likely value up to constant factors.
This answers a question of Bollobás and Erdös.

- Series
- ACO Seminar
- Time
- Tuesday, November 3, 2015 - 16:30 for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Adam Marcus – Mathematics and PACM, Princeton University

Recent work of the speaker with Dan Spielman and Nikhil
Srivastava introduced the ``method of interlacing polynomials''
(MOIP) for solving problems in combinatorial linear algebra.
The goal of this talk is to provide insight into the inner workings of
the MOIP by introducing a new theory that reveals an intimate
connection between the use of polynomials in the manner of the
MOIP and free probability, a theory developed by Dan Voiculescu
as a tool in the study of von Neumann algebras.
I will start with a brief introduction to free probability (for those, like
me, who are not operator theorists).
In particular, I will discuss the two basic operations in free
probability theory (the free additive and free multiplicative
convolutions), and how they relate to the asymptotic eigenvalue
distributions of random matrices.
I will then show how certain binary operations on polynomials act
as finite analogues of the free convolutions and how the MOIP is
effectively transferring the asymptotic bounds obtained in free
probability to bounds in the new theory (which can then be applied
to finite scenarios).
If time permits, I will show how such a theory gives far better
intuition as to how one might apply the MOIP in the future, using
recent results on restricted invertibility and the existence of
Ramanujan graphs as examples.

- Series
- ACO Seminar
- Time
- Monday, October 5, 2015 - 13:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Amir Dembo – Stanford University

The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of M=N d/2 edges, the leading correction to M/2 (the typical cut size), is P_* sqrt(N M/2). Here P_* is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula.
This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.

- Series
- ACO Seminar
- Time
- Monday, April 7, 2014 - 13:00 for 1 hour (actually 50 minutes)
- Location
- Klaus 1116
- Speaker
- Allan Borodin – University of Toronto

We are generally interested in the following ill-defined problem: What is
a conceptually simple algorithm and what is the power and limitations
of such algorithms?
In particular, what is a greedy algorithm or more generally a myopic
algorithm for a combinatorial optimization problem? And to be even more
specific, motivated by the Buchbinder et al
``online double sided greedy algorithm'' for the unconstrained non-monotone
submodular maximization problem, what are (if any) the limitations of
algorithms "of this genre" for the general unconstrained problem and for
specific instances of the problem, such as Max-Di-Cut?Joint work with Norman Huang.

- Series
- ACO Seminar
- Time
- Monday, March 31, 2014 - 16:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Daniel Dadush – New York University

The closest vector problem (CVP) on lattices (i.e. given an n
dimensional lattice L with basis B and target point t, find a closest
lattice point in L to t) is fundamental NP-hard problem with applications
in coding, cryptography & optimization. In this talk, we will consider the
preprocessing version of CVP (CVPP), an important variant of CVP, where we
allow arbitrary time to preprocess the lattice before answering CVP queries.
In breakthrough work, Micciancio & Voulgaris (STOC 2010) gave the first
single exponential time algorithm for CVP under the l_2 norm based on
Voronoi cell computations. More precisely, after a preprocessing step on L
requiring tilde{O}(2^{2n}) time, during which they compute the Voronoi cell
of L (the set of points closer to the origin than to any other point in L),
they show that additional CVP queries on L (i.e. CVPP) can be solved in
tilde{O}(2^{2n}) time.
For our main result, we show that given the Voronoi cell V of L as
preprocessing, CVP on any target t can be solved in expected tilde{O}(2^n)
time. As our main technical contribution, we give a new randomized
procedure that starting from any close enough lattice point to the target
t, follows a path in the Voronoi graph of L (i.e. x,y in L are adjacent if
x+V and y+V share a facet) to the closest lattice vector to t of expected
polynomial size. In contrast, the path used by MV algorithm is only known
to have length bounded by tilde{O}(2^n). Furthermore, for points x,y in L,
we show that the distance between x and y in the Voronoi graph is within a
factor n of ||x-y||_V (norm induced by the Voronoi cell), which is best
possible. For our analysis, we rely on tools from high dimensional convex
geometry. No background in convex geometry or lattices will be assumed.
Time permitting, I will describe related results & open questions about
paths on more general lattice Cayley graphs.
Joint work with Nicolas Bonifas (Ecole Polytechnique).

- Series
- ACO Seminar
- Time
- Wednesday, February 5, 2014 - 12:00 for 1 hour (actually 50 minutes)
- Location
- IC 209
- Speaker
- Marco Molinaro – Georgia Tech

**Please Note:** Joint DOS-ACO Seminar. Food and refreshments will be provided.

Sparse cutting-planes are often the ones used in mixed-integer programing
(MIP) solvers, since they help in solving the linear programs encountered
during branch-&-bound more efficiently. However, how well can we
approximate the integer hull by just using sparse cutting-planes? In order
to understand this question better, given a polyope P (e.g. the integer
hull of a MIP), let P^k be its best approximation using cuts with at most k
non-zero coefficients. We consider d(P, P^k) = max_{x in P^k} (min_{y in
P} |x - y|) as a measure of the quality of sparse cuts.
In our first result, we present general upper bounds on d(P, P^k) which
depend on the number of vertices in the polytope and exhibits three phases
as k increases. Our bounds imply that if P has polynomially many vertices,
using half sparsity already approximates it very well. Second, we present a
lower bound on d(P, P^k) for random polytopes that show that the upper
bounds are quite tight. Third, we show that for a class of hard packing
IPs, sparse cutting-planes do not approximate the integer hull well.
Finally, we show that using sparse cutting-planes in extended formulations
is at least as good as using them in the original polyhedron, and give an
example where the former is actually much better.
Joint work with Santanu Dey and Qianyi Wang.

- Offices & Departments
- News Center
- Campus Calendar
- Special Events
- GreenBuzz
- Institute Communications
- Visitor Resources
- Campus Visits
- Directions to Campus
- Visitor Parking Information
- GTvisitor Wireless Network Information
- Georgia Tech Global Learning Center
- Georgia Tech Hotel & Conference Center
- Barnes & Noble at Georgia Tech
- Ferst Center for the Arts
- Robert C. Williams Paper Museum