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

Series: ACO Student Seminar

Sampling permutations from S_n is a fundamental problem from probability theory. The nearest neighbor transposition chain M_n is known to converge in time \Theta(n^3 \log n) in the uniform case and time \Theta(n^2) in the constant bias case, in which we put adjacent elements in order with probability p \neq 1/2 and out of order with probability 1-p. In joint work with Prateek Bhakta, Dana Randall and Amanda Streib, we consider the variable bias case where the probability of putting an adjacent pair of elements in order depends on the two elements, and we put adjacent elements x < y in order with probability p_{x,y} and out of order with probability 1-p_{x,y}. The problem of bounding the mixing rate of M_n was posed by Fill and was motivated by the Move-Ahead-One self-organizing list update algorithm. It was conjectured that the chain would always be rapidly mixing if 1/2 \leq p_{x,y} \leq 1 for all x < y, but this was only known in the case of constant bias or when p_{x,y} is equal to 1/2 or 1, a case that corresponds to sampling linear extensions of a partial order. We prove the chain is rapidly mixing for two classes: ``Choose Your Weapon,'' where we are given r_1,..., r_{n-1} with r_i \geq 1/2 and p_{x,y}=r_x for all x < y (so the dominant player chooses the game, thus fixing his or her probability of winning), and ``League Hierarchies,'' where there are two leagues and players from the A-league have a fixed probability of beating players from the B-league, players within each league are similarly divided into sub-leagues with a possibly different fixed probability, and so forth recursively. Both of these classes include permutations with constant bias as a special case. Moreover, we also prove that the most general conjecture is false. We do so by constructing a counterexample where 1/2 \leq p_{x,y} \leq 1 for all x < y, but for which the nearest neighbor transposition chain requires exponential time to converge.

Series: ACO Student Seminar

In the last 10 years, compressed sensing has arisen as an entirely new area of mathematics, combining ideas from convex programming, random matrices, theoretical computer science and many other fields. Candes (one of the originators of the area) recently spoke about two quite recent and exciting developments, but it might be interesting to revisit the fundamentals, and see where a lot of the ideas in the more recent works have developed. In this talk, I will discuss some of the earlier papers (Candes-Romberg-Tao), define the compressed sensing problem, the key restricted isometry property and how it relates to the Johnson-Lindenstrauss lemma for random projections. I'll also discuss some of the more TCS ideas such as compressed sensing through group testing, and hopefully some of the greedy algorithm ideas as well. Finally, if time allows, I'll draw parallels with other problems, such as matrix completion, phase retrieval etc. The talk will be quite elementary, requiring only a knowledge of linear algebra, and some probability.

Series: ACO Student Seminar

This work develops approximation algorithms for a stochastic
knapsack problem involving an expected utility objective. The values
of the items in the knapsack can only be sampled from an oracle, and
the objective function is a concave function of the total value of the
items in the knapsack. We will first show a polynomial number of
samples is enough to approximate the true expected value close enough.
Then we will present an algorithm that maximizes a class of submodular
function under knapsack constraint with approximation ratio better
than 1-1/e. We will also see better bounds when the concave function
is a power function. At last, if time permits, we will give an FPTAS
of the problem when the number of scenarios is fixed.

Series: ACO Student Seminar

The theory of Groebner bases is the foundation of many algorithms in computational algebra. A Groebner basis is a special generating set of an ideal of polynomials. In this expository talk, I will introduce Groebner bases and explain how they can be used in integer programming. In particular, for an integer program, we can associate an ideal whose Groebner basis gives a set of directions that takes any feasible solution to an optimal solution.

Series: ACO Student Seminar

A linear coloring of a graph is a proper coloring of the vertices of the graph so that each pair of color classes induce a union of disjoint paths. In this talk, I will prove that for every connected graph with maximum degree at most three and every assignment of lists of size four to the vertices of the graph, there exists a linear coloring such that the color of each vertex belongs to the list assigned to that vertex and the neighbors of every degree-two vertex receive different colors, unless the graph is $C_5$ or $K_{3,3}$. This confirms a conjecture raised by Esperet, Montassier, and Raspaud. Our proof is constructive and yields a linear-time algorithm to find such a coloring. This is joint work with Gexin Yu.

Series: ACO Student Seminar

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. conductance of $S$ or the sparsity of the cut $(S,\bar{S})$)is bounded as follows: \phi(S) = w(S,S') /w(S) \leq \sqrt{2 \lambda_2},where $w$ is the total edge weight of a subset or a cut and $\lambda_2$ is the second smallest eigenvalue of thenormalized Laplacian of the graph.We study natural generalizations of the sparsest cut in a graph: (i) a partition ofthe vertex set into $k$ parts that minimizes the sparsity of the partition (defined as the ratio of theweight of edges between parts to the total weight of edges incident to the smallest $k-1$ parts); (ii) a collection of $k$ disjoint subsets $S_1, \ldots, S_k$ that minimize $\max_{i \in [k]} \phi(S_i)$; (iii) a subset of size $O(1/k)$ of the graph with minimum expansion. Our main results are extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian.In particular, for the sparsest $k$-partition, we prove that the sparsity is at most $8\sqrt{\lambda_k} \log k$where $\lambda_k$ is the $k^{th}$ smallest eigenvalue of the normalized Laplacian matrix.For the $k$ sparse cuts problem we prove that there exist$ck$ disjoint subsets $S_1, \ldots, S_{(1 - \eps)k}$, such that \max_i \phi(S_i) \leq C \sqrt{\lambda_{k} \log k}where $C>0$ are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for any $k$, there is a subset $S$ whoseweight is at most a $\bigO(1/k)$ fraction of the total weight and $\phi(S) \le C \sqrt{\lambda_k \log k}$. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger's method.Based on joint work with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.

Series: ACO Student Seminar

Thomassen proved that there are only finitely many 6-critical graphs
embeddable on a fixed surface. He also showed that planar graphs are
5-list-colorable. We develop new techniques to prove a general theorem
for 5-list-coloring graphs embedded on a fixed surface. Namely, for every surface S and every integer C > 0, there exists D
such that the following holds: Let G be a graph embedded in a surface S
with edge-width at least D and a list assignment L such that, for every
vertex v in G, L(v) has size at least five. If F is a collection of any
number of facial cycles of length at most C such that every two cycles
in F are distance at least D apart and every cycle in F has a locally
planar neighborhood up to distance D/2, then any proper L-coloring of F
extends to an L-coloring of G.
This theorem implies the following results. In what follows, let S be a
fixed surface, G be a graph embedded in S (except in 4, where G is drawn
in S) and L a list assignment such that, for every vertex v of G, L(v)
has size at least five.
1. If G has large edge-width, then G is 5-list-colorable. (Devos, Kawarabayashi and Mohar)
2. There exists only finitely many 6-list-critical graphs embeddable in
S. (Conjectured by Thomassen, Proof announced by Kawarabayashi and
Mohar) As a corollary, there exists a linear-time algorithm for deciding
5-list-colorability of graphs embeddable on S. Furthermore, we exhibit
an explicit bound on the size of such graphs.
3. There exists D(S) such that the following holds: If X is a subset of
the vertices of G that are pairwise distance at least D(S) apart, then
any L-coloring of X extends to an L-coloring G. For planar graphs, this
was conjectured by Albertson and recently proved by Dvorak, Lidicky,
Mohar, and Postle.
4. There exists D(S) such that the following holds: If G is a graph
drawn in S with face-width at least D(S) such that any pair of crossings
is distance at least D apart, then G is L-colorable. For planar graphs,
this was recently proved by Dvorak, Lidicky and Mohar.
Joint work with Robin Thomas.

Series: ACO Student Seminar

A mixed integer point is a vector in $\mathbb{R}^n$ whose first $n_1$ coordinates are integer. We present necessary and sufficient conditions for the convex hull of mixed integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones and strictly convex sets. Furthermore, by using these results, we show that there exists a polynomial time algorithm to check the closedness of the convex hull of the mixed integer points contained in the feasible region of a second order conic programming problem, for the special case this region is defined by just one Lorentz cone and one rational matrix. This is joint work with Santanu Dey.

Series: ACO Student Seminar

Consider a series of n single-server queues each with unlimited waiting
space and FIFO discipline. At first the system is empty, then m customers
are placed in the first queue. The service times of all the customers at
all the queues
are iid. We are interested in the exit time of the last customer from the
last
server and that's when queues meet random matrices and
GUEs. If the number of customers
is a small fractional power of the number of servers, and as such
customers stay within a tube, that's when queues encounter Tracy and Widom.
This talk will be self contained and accessible to graduate students.

Series: ACO Student Seminar

In a celebrated result, Raghavendra [Rag08] showed that, assuming Unique Game Conjecture, every Max-CSP problem has a sharp approximation threshold that matches the integrality gap of a natural SDP relaxation. Raghavendra and Steurer [RS09] also gave a simple and unified framework for optimally approximating all the Max-CSPs.In this work, we consider the problem of approximating CSPs with global cardinality constraints. For example, Max-Cut is a boolean CSP where the input is a graph $G = (V,E)$ and the goal is to find a cut $S \cup \bar S = V$ that maximizes the number of crossing edges, $|E(S,\bar S)|$. The Max-Bisection problem is a variant of Max-Cut with an additional global constraint that each side of the cut has exactly half the vertices, i.e., $|S| = |V|/2$. Several other natural optimization problems like Small Set Expansion, Min Bisection and approximating Graph Expansion can be formulated as CSPs with global constraints.In this talk, I will introduce a general approach towards approximating CSPs with global constraints using SDP hierarchies. To demonstrate the approach, I will present an improved algorithm for Max-Bisection problem that achieves the following:- Given an instance of Max-Bisection with value $1-\epsilon$, the algorithm finds a bisection with value at least $1-O(\sqrt{\epsilon})$ with running time $O(n^{poly(1/\eps)})$. This approximation is near-optimal (up to constant factors in $O()$) under the Unique Games Conjecture.- Using computer-assisted proof, we show that the same algorithm also achieves a 0.85-approximation for Max-Bisection, improving on the previous bound of 0.70 (note that it is UGC-hard to approximate better than 0.878 factor). As an attempt to prove matching hardness result, we show a generic conversion from SDP integrality gap to dictatorship test for any CSP with global cardinality constraints. The talk is based on joint work with Prasad Raghavendra.