Jan 28	Greg Frederickson Purdue	Approximation algorithms for the traveling repairman and speeding deliveryman problems Abstract: Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling salesman problem, the goal is to find a path that visits the maximum possible number of locations during their time windows. In the second variation, the speeding deliveryman problem, the goal is to find a path that uses the minimum possible speed to visit all locations during their time windows. For both variations, the time windows are of unit length, and the distance metric is baed on a weighted undirected graph. Algorithms with improved approximation ratios are given for the case when the input is defined on a tree rather than a general graph. The algorithms are also extended to handle time windows whose lengths fall in any bounded range. Joint work with Barry Wittman.
Feb 4	Will Perkins Georgia Tech	Random k-SAT and the Power of Two Choices Abstract: I will discuss the random k-satisfiability problem: m k-CNF clauses are chosen uniformly at random from all possible clauses on n boolean variables. It is known that the problem exhibits a swift transition from almost certain satisfiability to almost certain unsatisfiability as the number of clauses increases. I will survey some of the major results and open problems about the random k-SAT problem and this transition and then present new results on an Achlioptas-process version of the problem.
Feb 25	Yury Makarychev TTI	Sorting Noisy Data with Partial Information Abstract: We propose two semi-random models for the Minimum Feedback Arc Set Problem and present approximation algorithms for them. In the first model, which we call the Random Edge Flipping model, an instance is generated as follows. We start with an arbitrary acyclic directed graph and then randomly flip its edges (the adversary may later un-flip some of them). In the second model, which we call the Random Backward Edge model, again we start with an arbitrary acyclic graph but now add new random backward edges (the adversary may delete some of them). For the first model, we give an approximation algorithm that finds a solution of cost (1+delta) OPT+ n polylog(n), where OPT is the cost of the optimal solution. For the second model, we give an approximation algorithm that finds a solution of cost O(planted-cost), where planted-cost is the cost of the planted solution. Additionally, we present an approximation algorithm for semi-random instances of Minimum Directed Balanced Cut. This is joint work with Konstantin Makarychev and Aravindan Vijayaraghavan.
Mar 5	Abram Magner Purdue	LWSN 3102 AB. 10:30 am. Note ROOM CHANGE and non-standard day. Asymptotic Asymmetry of Uniform Attachment Graphs Abstract: I will discuss the problem of characterizing the conditions under which asymmetry arises with high probability in graphs drawn according to a uniform attachment process, a special case of of a generalization of the preferential attachment process, and motivate it with an information theoretic application: asymptotic asymmetry is necessary for an extension of results about structural entropy for Erdos-Renyi graphs to more complicated distributions. I will show how the problem can be boiled down to proving measure concentration, sketch a proof of a weaker result, and demonstrate how standard concentration inequalities fail. Based on joint work with Giorgos Kollias and Wojciech Szpankowski.
Mar 18	Anand Louis Georgia Tech	Graph Multi-partitioning and Higher Order Cheeger Inequalities Abstract: 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 the normalized Laplacian of the graph. I will talk about some natural generalizations of the sparsest cut in a graph: (i) a partition of the vertex set into $k$ parts that minimizes the sparsity of the partition (defined as the ratio of the weight of edges between parts to the total weight of edges incident to the smallest $k-1$ parts); (ii) a partition of the vertex set into $k$ parts $S_1, \ldots, S_k$ that minimize $\max_{i \in [k]} \phi(S_i)$; I will present some near-optimal extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian and some approximation-algorithms for them. Based on joint works with Prasad Raghavendra, Prasad Tetali and Santosh Vempala and Konstantin Makarychev.
Mar 28	Prasad Tetali Georgia Tech	CS/MATH COLLOQUIUM. LWSN 3102. 10:30 am. Note non-standard day and place. Phase transitions in the square lattice gas model Abstract: The hard-core model has attracted much attention across several disciplines, representing lattice gases in statistical physics and (weighted) independent sets in discrete mathematics and computer science. The model considers probability distributions on independent sets in finite and infinite graphs. On finite graphs, the interest is in sampling from the probability distribution using a local Markov chain, and as such in identifying the transition from fast mixing to slow mixing of the local dynamics, as a system parameter is varied. In the infinite setting, the challenge is in determining the transition from when the probability distribution is unique versus non-unique -- the onset of multiple Gibbs states -- as the same system parameter is varied. These problems are believed to be very closely related. We study the above phenomena exhibited by the hard-core model on the square lattice Z^2. In collaboration with several researchers, we prove improved upper and lower bounds on the critical point of the parameter whose existence, while widely believed, remains conjectural. The lower bound proof builds on breakthrough work of D. Weitz, relating the behavior on a regular graph to a regular tree via the tree of (relaxations of) self-avoiding walks on the graph. The upper bound proofs use a combinatorial characterization of configurations based on earlier work of D. Randall and an enumeration of a new class of self-avoiding walks called taxi walks. (Every attempt will be made to keep the talk self-contained.) Bio: Prasad Tetali is a Professor in the School of Mathematics, with a joint appointment in the School of Computer Science, at Georgia Tech. He is currently the Director of Algorithms & Randomness Center (ARC) at Georgia Tech. He is a SIAM Fellow (2009) and an AMS Fellow (2012). His research interests span theoretical computer science, discrete mathematics, probability and functional analysis, and he has been affiliated with Georgia Tech's Ph.D. program in Algorithms, Combinatorics and Optimization (ACO) since 1994.
Apr 12	Alexandra Kolla UIUC	Note non-standard day. LWSN 1106. 10:30-11:30 Title:Maximal Inequality for Spherical Means on the Hypercube and the Unique Games Conjecture. Abstract: In this talk, we establish a dimension-free ell_2 maximal inequality for spherical means on the Hypercube graph {0,1}^n. We explain possible connections to the notorious Unique Games Conjecture. Combinatorially, this inequality implies the following stronger alternative to the union-bound technique: Assume that we have a binary function f (values 0,1) on the n-dimensional hypercube Hn, with N=2^n vertices. Think of the set X={x\in Hn : f(x)=1} as the set vertices that a malicious adversary "spoils". Assume |X|<\epsilon N, i.e. the adversary can only spoil up to \epsilon fraction of the vertices. Fix a threshold \lambda>\epsilon. Say a (hamming) sphere S(x,r) or radius r around a point x is "bad" if the adversary has spoiled more than \lambda fraction of the points in the shpere. We call a point x "ruined" if *there exists* a radius r for which the sphere S(x,r) around x is bad. Our maximal inequality implies that for every \lambda, there is an absolute constant \epsilon (which does not depend on the dimension n) that if the adversary spoils at most \epsilon fraction of the points then the "ruined" set is a strict subset of the hypercube. Note that applying a union-bound over radii instead, we would not get any useful inequality for the size of the ruined set. Joint work with Aram Harrow (UW) and Leonard Schulman (Caltech).
Apr 17	Shiang-Jia Huang Purdue	Post Quantum Cryptography: A Survey (Non-standard DAY and TIME and PLACE) 3pm-4, HAAS 101 Abstract: In the past few decades, public key cryptography has been constructed using primitives whose security is based on the assumption that integer factorization problems an\ d discrete logarithm problems are hard. Advances in quantum computers, however, threaten to undermine these assumptions. In this talk, I'll discuss several cryptosyst\ ems that are believed to be resistant to quantum adversaries. These systems take hash-based, lattice-based, code-based, and knapsack-based approaches to cryptography.
Apr 22	Saugata Basu Purdue	(LWSN 1106, 10:30am) Towards a real analogue of the Bezout inequality and applications to incidence problems Abstract: The classical theorem of Bezout implies that the number of isolated complex zeros of k polynomials in C[X1; : : : ;Xk] is bounded by the product of the degrees of the polynomials. It is also well known that the same statement does not hold over the real numbers, or more generally over real closed fields. In this talk I will explain a new result that could serve as a substitute. I will also explain why this result could be of interest in tackling incidence problems in discrete geometry. Joint work with Sal Barone.

Link to schedule for Fall 2012.