| Annual Events - Streaming Video Lectures | |
| View video of ARC's First Anniversary, 2007 |
|
| View video of ARC's Inaugural Event, 2006 | |
ARC Student Fellowships
The following projects were funded in Summer, 2008:
Georgios Amanatidis, Math (Mentor Milena Mihail) -
Models for Routing and Social Complex Networks
Deeparnab Chakrabarty, CS (Mentor Vijay Vazirani) -
Budget-Constrained Auctions
Sam Greenberg, Math (Mentor Dana Randall) -
Random Sampling via Geometric Coupling
Kael Stilp, ISYE (Mentor Ozlem Ergun) -
Searching for the Core with Column Generation
Two colloquium lectures on Mon., Nov. 12 - Prabhakar and Ashlagi
Itai Ashlagi of Technion, Israel will present a talk entitled "Mediators in Position Auctions".
This talk will be held in Room 1116E, Klaus at 11:00 AM.
Abstract:
A mediator is a reliable entity, which plays on behalf of the players who give her the right of play. The mediator is guaranteed to behave in a pre-specified way based on messages received from the agents. However, a mediator cannot enforce behavior; that is, agents can play in the game directly without the mediator's help. A mediator generates a new game for the players, the mediated game. The outcome in the original game of an equilibrium in the mediated game is called a mediated equilibrium.
Monderer and Tennenholtz defined a mediator for games with complete information. We extend the theory of mediators to games with incomplete information, and use the new theory to study position auctions, a central topic in practical and theoretical electronic commerce. We provide minimal sets of conditions on position auctions, which are sufficient to guarantee that the VCG outcome function is a mediated equilibrium in these position auctions
Balaji Prabhakar of Stanford University will present a talk entitled "Title: Turbo-Counters: Efficient network traffic measurement using a sparse graph counter architecture."
This talk will be held in Room 1116E, Klaus at 3:30 PM.
Abstract: Measuring network flow sizes is important for accounting/billing, network forensics and security. Per-flow measurement is considered hard because it requires that many counters be updated at a very high speed, and a flow-to-counter perfect hash function. Therefore, current approaches aim to obtain approximate flow counts; that is, to detect large "elephant" flows and then measure their sizes. We present a novel method for per-flow traffic measurement that is fast, highly
memory efficient and accurate. At the core of this method is an
architecture, which we call "counter braids."
October 29th, 2007 - Julia Chuzhoy, Institute for Advance Study - 3:30 PM, Klaus 1116E
Title: Cuts and Flows in Directed Graphs
Abstract:
Cuts and flows are among the most basic graph theoretic notions.
Applications that require solving graph cut or flow problems arise in almost every area of computer science. The study of the connection between flows and cuts dates back to the late fifties when Ford and Fulkerson proved that in the single-commodity environment, minimum cut equals maximum flow in any graph. A natural generalization of this result would be establishing the relationship between flows and cuts in the presence of multiple commodities.
This relationship is usually expressed via the notion of flow-cut gap: the maximum ratio, achievable for any graph, between the maximum multi-commodity flow and the corresponding cut value, called minimum multicut.Flow-cut gaps have been extensively studied for more than five decades now, and they are widely used in the design and the analysis of algorithms. One of the major breakthroughs in this area is a complete understanding of the flow-cut gap in undirected graphs, which was proved to be logarithmic. In spite of this success, the flow-cut gaps have remained poorly understood in directed graphs. In particular, it has remained an open question whether the flow-cut gap in directed graphs is also logarithmic. In this talk we will answer this question in the negative by showing that, in sharp contrast to the undirected case, the flow-cut gap in directed graphs is polynomial.
Joint work with Sanjeev Khanna.
October 22, 2007 - Ken Brown - 3:30 PM, Klaus 1116E
Title: Quantum Computing Algorithms for Physical ScienceAbstract: A common view of physical scientists is that a quantum computer should be more efficient than a classical computer for solving problems in quantum mechanics. In this talk, I will review the state of quantum algorithms and their potential application to problems in chemistry and physics.
October 15, 2007 - Saugata Basu 1:30 PM, Klaus 1116E
Arc Colloquium will host Saugata Basu who is a faculty member in the Department of Mathematics at Georgia Institute of Technology.Title: Algorithmic and topological complexity of semi-algebraic sets.
Abstract: Semi-algebraic sets are subsets of ${\mathbb R}^n$ defined in terms of a finite number of real polynomial equalities and inequalities. They have important applications in many areas of science and engineering. Moreover, they satisfy important finiteness properties. A semi-algebraic set can have only finitely many connected components, finite Betti numbers etc. It is in fact possible to bound the Betti numbers, as well as the number of topological types, of semi-algebraic sets in terms of the number and the degrees of the polynomials defining them.
In this talk I will give a survey of recent results on obtaining tight bounds on the Betti numbers, as well as on the number of homotopy types, of semi-algebraic sets in terms of the parameters mentioned above. I will also describe how some of these results generalize to the more abstract setting of definable sets in any o-minimal structure. Finally, time permitting, I will describe recent progress in developing efficient algorithms for computing the Betti numbers of semi-algebraic sets.No background in semi-algebraic geometry or topology will be assumed.
Certain parts of this work are joint with R. Pollack, M-F. Roy and (separately) with N. Vorobjov.
October 5, 2007 - Ran Raz 11:00 AM, Klaus 1116E
Arc Colloquium will host Ran Raz of The Weizmann Institute of Science.
Title: Elusive Functions and Lower Bounds for Arithmetic Circuits
Abstract: I will present a family of mathematical problems that are very simple to describe, that seem very natural-to-study in the context of pseudorandomness and explicit constructions of combinatorial objects, and are seemingly unrelated to arithmetic circuit complexity, and whose solution would give strong (up to exponential) lower bounds for the size of general arithmetic circuits.
I may also discuss lower bounds of $n^{1+\Omega(1/d)}$ for the size of arithmetic circuits of depth $d$ (for explicit polynomials of degree $O(d)$)that are proved using related methods.
October 3, 2007 ARC's Anniversary
ARC will celebrate its anniversary on October 3rd! Our distinguished lecturer will be László Lovász . Dr. Lovász is a pioneering mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999. He received his Ph.D. in 1970 at Eötvös Loránd University. Dr. Lovász was a professor at Yale University during the 1990s and was a collaborative member of the Microsoft Research Center until 2006. Currently he is the director of the Mathematical Institute (Eötvös Loránd University, Budapest). He has served as president of the International Mathematical Union since January 1, 2007.
ARC Colloquium, Fall, 2007
The Fall, 2007 Colloquium is currently being organized. Among the guest speakers will be Sergey Yekhanin and Ran Raz.
Workshop on Complex Networks
January 22-24, 2007
Under the auspices of the DIMACS/Georgia Tech Specia Year on Discrete Random Systems, we invite you to a Workshop on Complex Networks and their Applications, on Georgia Tech Campus (TSRB) Jan 22-24. URL http://www-static.cc.gatech.edu/~mihail/indexcomplex.html
Organizers: Fan Chung (UCSD), Ashish Goel (Stanford), Milena Mihail (Georgia Tech) and Chris Wiggins (Columbia).
Discrete Random Systems Kickoff
November 20, 2006
This half-day kickoff event aims to identify some of the research directions and open problems to be addressed during the special focus on Discrete Random Systems. The talks will touch on several major themes of the special focus: properties of large graphs, complex networks and their applications, phase transitions, and Markov chain sampling.
Inaugural Distinguished Lectures
Klaus Auditorium
November 10, 2006
An introductory lecture on Algorithms and Randomness followed by three distinguished speakers: Dick Karp, Ravi Kannan and Dick Lipton.
