Seminars and Colloquia by Series

Friday, October 28, 2016 - 15:05 , Location: Skiles 005 , Sharath Raghvendra , Virginia Tech , Organizer: Esther Ezra
Motivated by real-time logistics, I will present a deterministic online algorithm for the Online Minimum Metric Bipartite Matching Problem. In this problem, we are given a set S of server locations and a set R of request locations.The requests arrive one at a time and when it arrives, we must immediately and irrevocably match it to a ``free" server. The cost of matching a server to request is given by the distance between the two locations (which we assume satisfies triangle inequality). The objective of this problem is to come up with a matching of servers to requests which is competitive with respect to the minimum-cost matching of S and R.In this talk, I will show that this new deterministic algorithm performs optimally across different adversaries and metric spaces. In particular, I will show that this algorithm simultaneously achieves optimal performances in two well-known online models -- the adversarial and the random arrival models. Furthermore, the same algorithm also has an exponentially improved performance for the line metric resolving a long standing open question.
Friday, October 21, 2016 - 15:05 , Location: Skiles 005 , Esther Ezra , Georgia Tech , Organizer: Esther Ezra

Joint work with Micha Sharir (Tel-Aviv University).

Following a recent improvement of Cardinal etal. on the complexity of a linear decision tree for k-SUM, resulting in O(n^3 \log^3{n}) linear queries, we present a further improvement to O(n^2 \log^2{n}) such queries. Our approach exploits a point-location mechanism in arrangements of hyperplanes in high dimensions, and, in fact, brings a new view to such mechanisms. In this talk I will first present a background on the k-SUM problem, and then discuss bottom-vertex triangulation and vertical decomposition of arrangements of hyperplanes and how they serve our analysis.
Friday, October 7, 2016 - 15:05 , Location: Skiles 005 , John Wilmes , Georgia Tech , Organizer: Esther Ezra
A graph is ``strongly regular'' (SRG) if it is $k$-regular, and every pair of adjacent (resp. nonadjacent) vertices has exactly $\lambda$ (resp. $\mu$) common neighbors. Paradoxically, the high degree of regularity in SRGs inhibits their symmetry. Although the line-graphs of the complete graph and complete bipartite graph give examples of SRGs with $\exp(\Omega(\sqrt{n}))$ automorphisms, where $n$ is the number of vertices, all other SRGs have much fewer---the best bound is currently $\exp(\tilde{O}(n^{9/37}))$ (Chen--Sun--Teng, 2013), and Babai conjectures that in fact all primitive SRGs besides the two exceptional line-graph families have only quasipolynomially-many automorphisms. In joint work with Babai, Chen, Sun, and Teng, we make progress toward this conjecture by giving a quasipolynomial bound on the number of automorphisms for valencies $k > n^{5/6}$. Our proof relies on bounds on the vertex expansion of SRGs to show that a polylogarithmic number of randomly chosen vertices form a base for the automorphism group with high probability.
Monday, September 12, 2016 - 16:05 , Location: Skiles 169 , Anastasios Sidiropoulos , The Ohio State University , Organizer: Esther Ezra
The computational complexity of many geometric problems depends on the dimension of the input space. We study algorithmic problems on spaces of low fractal dimension. There are several well-studied notions of fractal dimension for sets and measures in Euclidean space. We consider a definition of fractal dimension for finite metric spaces, which agrees with standard notions used to empirically estimate the fractal dimension of various sets. When the fractal dimension of the input is lower than the ambient dimension, we obtain faster algorithms for a plethora of classical problems, including TSP, Independent Set, R-Cover, and R-Packing. Interestingly, the dependence of the performance of these algorithms on the fractal dimension closely resembles the currently best-known dependence on the standard Euclidean dimension. For example, our algorithm for TSP has running time 2^O(n^(1-1/delta) * log(n)), on sets of fractal dimension delta; in comparison, the best-known algorithm for sets in d-dimensional Euclidean space has running time 2^O(n^(1-1/d)).
Friday, September 9, 2016 - 15:05 , Location: Skiles 005 , Emma Cohen , Georgia Tech , Organizer: Esther Ezra

Joint work with Will Perkins and Prasad Tetali.

We consider the extremal counting problem which asks what d-regular, r-uniform hypergraph on n vertices has the largest number of (strong) independent sets. Our goal is to generalize known results for number of matchings and independent sets in regular graphs to give a general bound in the hypergraph case. In particular, we propose an adaptation to the hypergraph setting of the occupancy fraction method pioneered by Davies et al. (2016) for use in the case of graph matchings. Analysis of the resulting LP leads to a new bound for the case r=3 and suggests a method for tackling the general case.
Friday, August 26, 2016 - 15:05 , Location: Skiles 005 , Lutz Warnke , Georgia Tech , Organizer: Esther Ezra
One of the most interesting features of Erdös-Rényi random graphs is the `percolation phase transition', where the global structure intuitively changes from only small components to a single giant component plus small ones. In this talk we discuss the percolation phase transition in the random d-process, which corresponds to a natural algorithmic model for generating random regular graphs (starting with an empty graph on n vertices, it evolves by sequentially adding new random edges so that the maximum degree remains at most d).  Our results on the phase transition solve a problem of Wormald from 1997, and verify a conjecture of Balinska and Quintas from 1990.   Based on joint work with Nick Wormald (Monash University).
Friday, April 22, 2016 - 15:00 , Location: Skiles 005 , Thomas Rothvoss , University of Washington , , Organizer: Esther Ezra
A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2). Recent exciting work of Bansal, Lovett and Meka shows that such colorings can be found in polynomial time. In fact, the Lovett-Meka algorithm finds a half integral point in any "large enough" polytope. However, their algorithm crucially relies on the facet structure and does not apply to general convex sets. We show that for any symmetric convex set K with measure at least exp(-n/500), the following algorithm finds a point y in K \cap [-1,1]^n with Omega(n) coordinates in {-1,+1}: (1) take a random Gaussian vector x; (2) compute the point y in K \cap [-1,1]^n that is closest to x. (3) return y. This provides another truly constructive proof of Spencer's theorem and the first constructive proof of a Theorem of Gluskin and Giannopoulos.
Tuesday, April 19, 2016 - 14:05 , Location: Skiles 006 , Annie Raymond , University of Washington, Seattle, WA , Organizer: Prasad Tetali
The Frankl union-closed sets conjecture states that there exists an element present in at least half of the sets forming a union-closed family. We reformulate the conjecture as an optimization problem and present an integer program to model it. The computations done with this program lead to a new conjecture: we claim that the maximum number of sets in a non-empty union-closed family in which each element is present at most a times is independent of the number n of elements spanned by the sets if n is greater or equal to log_2(a)+1. We prove that this is true when n is greater or equal to a. We also discuss the impact that this new conjecture would have on the Frankl conjecture if it turns out to be true. This is joint work with Jonad Pulaj and Dirk Theis.
Friday, April 15, 2016 - 15:00 , Location: Skiles 005 , Ohad Noy Feldheim , Stanford University , Organizer: Esther Ezra

Joint work with Yinon Spinka.

Consider a random coloring of a bounded domain in the bipartite graph Z^d with the probability of each color configuration proportional to exp(-beta*N(F)), where beta>0, and N(F) is the number of nearest neighboring pairs colored by the same color. This model of random colorings biased towards being proper, is the antiferromagnetic 3-state Potts model from statistical physics, used to describe magnetic interactions in a spin system. The Kotecky conjecture is that in such a model with d >= 3, Fixing the boundary of a large even domain to take the color $0$ and high enough beta, a sampled coloring would typically exhibits long-range order. In particular a single color occupies most of either the even or odd vertices of the domain. This is in contrast with the situation for small beta, when each bipartition class is equally occupied by the three colors. We give the first rigorous proof of the conjecture for large d. Our result extends previous works of Peled and of Galvin, Kahn, Randall and Sorkin, who treated the zero beta=infinity case, where the coloring is chosen uniformly for all proper three-colorings. In the talk we shell give a glimpse into the combinatorial methods used to tackle the problem. These rely on structural properties of odd-boundary subsets of Z^d. No background in statistical physics will be assumed and all terms will be thoroughly explained. 
Friday, April 1, 2016 - 15:00 , Location: Skiles 005 , Christian Houdré , Georgia Tech , Organizer: Esther Ezra
Both for random words or random permutations, I will present a panoramic view of  results on the (asymptotic) behavior of the length of the longest common subsequences . Starting with, now, classical results on expectations dating back to the nineteen-seventies I will move to recent results obtained by Ümit Islak and myself giving the asymptotic laws of this length and as such answering a decades-old well know question.