The ACO Program sponsors a Colloquium Series which brings visiting speakers to the campus.
Please look at the ACO research page to learn more about current research areas involved in the ACO program; and at the ACO events page for a current schedule of events related to the program.
Can (Theoretical Computer) Science Get a Grip on Consciousness?
5:00 pm, LeCraw Auditorium, College of Management
| To come to grips with consciousness, I postulate that living entities in general, and human beings in particular, are mechanisms... marvelous mechanisms to be sure but not magical ones... just mechanisms. On this basis, I look to explain some of the paradoxes of consciousness such as Samuel Johnson's "All theory is against the freedom of the will; all experience is for it."
I will explain concepts of self-awareness and free will from a mechanistic view. My explanations make use of computer science and suggest why these phenomena would exist even in a completely deterministic world. This is particularly striking for free will. The impressions of our senses, like the sense of the color blue, the sound of a tone, etc. are to be expected of a mechanism with enormously many inputs categorized into similarity classes of sight, sound, etc. Other phenomena such as the "bite" of pain are works in progress. I show the direction that my thinking takes and say something about what I've found and what I'm still looking for. Fortunately, the sciences are discovering a great deal about the brain, and their discoveries help enormously in guiding and verifying the results of this work. Reception at 4:10 in LeCraw Atrium |
Reflections on a favorite child
4:30 pm, Klaus 1116
| Fifty five years ago, two results of the Hungarian
mathematicians, Koenig and Egervary, were combined using the duality
theory of linear programming to construct the Hungarian Method for the
Assignment Problem. In a recent reexamination of the geometric
interpretation of the algorithm (proposed by Schmid in 1978) as a steepest
descent method, several variations on the algorithm have been uncovered,
which seem to deserve further study.
The lecture will be self-contained, assuming little beyond the duality theory of linear programming. The Hungarian Method will be explained at an elementary level and will be illustrated by several examples.
We shall conclude with account of a posthumous paper of Jacobi containing an
algorithm developed by him prior to 1851 that is essentially identical to the
Hungarian Method, thus anticipating the results of Koenig (1931),
Egervary (1931), and Kuhn (1955) by many decades.
|
Image Segmentation using Spectral Graph Theory
4:30pm, Skiles 255
| In this talk we present a new image segmentation algorithm,
Spectral Rounding (SR), and a fast solver. The combination is used for
segmenting 2D and 3D images. Applying SR to the Berkeley data base of
human segmented images, and medical examples such as tumors in mammograms
and 3D retinal scans gives robust quality segmentations. When used with
our fast solver SR is nearly nearly time.
The key idea in SR is to view an image as a 2D mattress of springs. Two neighboring pixels are connected by a spring where the spring constant is determined by local similarity in the pixel intensity. Shi and Malik proposed the important idea of using the fundamental modes of vibration of this mattress, the eigenvectors, to segment the image. The straightforward method for partitioning a graph using its eigenvectors, however, does not seem to work well in practice. We propose a relaxation method based on eigenvectors for finding these graph cuts. At each round a few fundamental eigenvectors are computed, from which the spring constants are updated and these eigenvectors are recomputed using the new spring constants. Thus the spring constants are successively readjusted until the mattress disconnects, an image segmentation. SR compares favorably with hand-segmented images from the Berkeley database and the normalized cut metric. We also show convergence in general and termination for several important cases. The second issue addressed is fast algorithms for finding the associated eigenvectors and solving related linear systems. This is a critical issue because modern 3D medical images may contain a billion nodes (voxels). A related and important first step to finding eigenvector and of interest on its own is solving 2D and 3D Laplacians. For instance, Siemens uses Laplacians for their new assisted image segmentation algorithm. We present the first linear-time algorithm for 2D and more general planar Laplacians. This represents joint work with Yiannis Koutis and David Tolliver. |
Turbo-Counters: Efficient network traffic measurement using a sparse graph counter architecture
3:30pm, Klaus 1116
| 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." We present two results: (i) The optimality of counter braids, in the sense that the total number of bits needed store flow sizes losslessly equals the entropy lower bound. Since network traffic has an entropy rate less than 3 bits per flow, this makes possible an implementation in an on-chip SRAM. (ii) A low-complexity message-passing estimation algorithm, that recovers flow sizes with vanishing error at link speed. Evaluation on Internet traces demonstrates that almost all flow sizes are estimated error-free with only 5 bits per flow. Joint work with: Sarang Dharmapurikar, Abdul Kabbani, Yi Lu, Andrea Montanari. |
The power of quantum systems on a line
4:30pm, Skiles 269
| In this talk, we discuss the computational strength of
finite dimensional quantum particles arranged on a line. We prove that
adiabatic computation is equivalent to standard quantum computation even when
the adiabatic quantum system is restricted to 2-local interactions of nearest
neighbors on a line. The particles in this construction require 9 states
per particle. We then adapt this construction to show that the 2-local
Hamiltonian for 12 state particles on a line is QMA-complete. QMA is
the quantum analog of NP. This result contrasts with the classical analog
in which one-dimensional Max-2-SAT with nearest neighbor constraints is
in known to be in P. Similar results were obtained independently by
Aharonov, Gottesman and Kempe. The work appears jointly in FOCS 2007.
Refreshments at 4:00PM in Skiles 236 |
Van der Waerden/Schrijver-Valiant like Conjectures and Stable Homogeneous
4:30pm, Skiles 255
| Abstract
Refreshments at 4:00PM in Skiles 236 |
Iterative Methods in Combinatorial Optimization
4:30pm, Klaus 1116E
| Linear programming has been a successful tool in combinatorial optimization to achieve polynomial time algorithms for problems in P and also to achieve good approximation algorithms for problems which are NP-hard. We demonstrate that iterative methods give a general framework to analyze linear programming formulations of combinatorial optimization problems. We show that iterative methods are well-suited for problems in P and lead to new proofs of integrality of linear programming formulations for various problems in P. This understanding provides us the basic groundwork to address various problems that are NP-hard and to achieve good approximation algorithms. In this talk, we focus on degree bounded network design problems. The most well-studied problem in this class is the Minimum Bounded Degree Spanning Tree problem. We present a polynomial time algorithm that returns a spanning tree of optimal cost such that the degree of any vertex in the tree exceeds its degree bound by at most an additive one. This generalizes a result of Furer and Raghavachari to weighted graphs, and thus settles a 15-year-old conjecture of Goemans affirmatively. This is essentially the best possible result for this problem. For degree constrained versions of more general network design problems, we obtain strong bi-criteria approximation algorithms using the iterative method. |
Games in Networks
4:30pm, Tennenbaum Auditorium in the Instructional Center
| Many large networks operate and evolve through interactions of large numbers of diverse participants. Such networks play a fundamental role in many domains, ranging from communication networks to social networks. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the success of these networks in game theoretic terms; what principles of interaction lead selfish participants to form such efficient networks? In this talk we present a number of network formation and routing games. We focus on simple games that have been analyzed in terms of the efficiency loss that results from selfishness. In each setting our goal is to quantify the degradation of quality of solution caused by the selfish behavior of users, comparing the selfish outcome to a centrally designed optimum, or comparing outcomes with different levels of cooperation. |
Correlation Inequalities
4:30pm, Skiles 255
| Correlation inequalities --- e.g. the Harris, FKG and
BK inequalities --- are basic tools in probability and have also had some
beautiful combinatorial consequences. Here we will mention a few relatively
recent inequalities, but mainly want to give some indication of how little
we actually know about such things.
Refreshments at 4:00PM in Skiles 236 |
Controllable random permutations
4:30pm, Skiles 255
|
In this talk, we propose a new procedure for generating random permutations.
We discuss applications of this technique to some scheduling problems.
In particular, we show that by applying this procedure to a single machine,
it is possible to ensure a desired average completion time for every job,
or to prove that this is not feasible. The parameters of the procedure can
be found in polynomial time by solving a simple nonlinear convex optimization
problem.
Refreshments at 4:00PM in Skiles 236 |
Perfect Implementation of Normal-Form Mechanisms
4:30pm, Skiles 255
| Privacy and trust affect our strategic thinking, yet they have not been precisely modeled in mechanism design. In settings of incomplete information, traditional implementations of a normal-form mechanism ---by disregarding the players' privacy, or assuming trust in a mediator--- may not be realistic and fail to reach the mechanism's objectives. We thus investigate implementations of a new type. We put forward the notion of a perfect implementation of a normal-form mechanism M: in essence, an extensive-form mechanism exactly preserving all strategic properties of M, without relying on a trusted party or violating the privacy of the players. We prove that any normal-form mechanism can be perfectly implemented via envelopes and an envelope-randomizing device (i.e., the same tools used for running fair lotteries or tallying secret votes). |
Towards a proof of Seymour's 1-flowing conjecture
4:30pm, Skiles 269
|
The well known max-flow min-cut theorem states that the maximum
amount of flow that can be sent from vertex s to a vertex t in a graph (with
capacities) is equal to the capacity of smallest cut which separates s and t.
While the notion of flows in graphs extends naturally to binary matroids, the
max-flow min-cut relation does not hold for binary matroids in general.
However, Seymour conjectured that the aforementioned minimax relation holds as
long as the binary matroids do not contain any one of three special
obstructions. This conjecture if true would generalize many classical results
on multi-commodity flows and matchings. Our approach is to try to give a
structural characterization of the binary matroids for which the minimax
relation holds. I will review known cases of the conjecture and give a brief
sketch of our strategy for solving the conjecture. A more technical description
of the tools we are developing will be presented on November 10 during the
Combinatorics seminar.
This is joint work with Irene Pivotto and Paul Wollan.
Refreshments at 4:00PM in Skiles 236 |
Advances in Convex Optimization: Conic Programming
4:00pm, Instructional Center Room 205
|
During the last two decades, major developments in Convex
Optimization were focusing on Conic Programming, primarily, on Linear, Conic
Quadratic and Semidefinite optimization. Conic Programming allows to reveal
rich structure which usually is possessed by a convex program and to exploit
this structure in order to process the program efficiently. In the talk, we
overview the major components of the resulting theory (conic duality and
primal-dual interior point polynomial time algorithms), outline the extremely
rich "expressive abilities" of Conic Quadratic and Semidefinite Programming
and discuss a number of instructive applications.
Reception to follow. |
The Abelian Sandpile Model
4:00pm, MSC E208, Emory University, Department of Mathematics and Computer Science
| Abstract |
Many Hamiltonian Cycles
11:05am, Skiles 255
|
We'll begin with the following theorem, which proves a conjecture of
Sarkozy, Selkow and Szemeredi, and try to use it as an excuse to talk
about other things (e.g., Bregman's Theorem, entropy, the
"incremental random method," statistics physics ...).
Theorem Any n-vertex Dirac graph (i.e., graph of minimum degree at least n/2) contains at least (2-o(1))^{-n}n! Hamiltonian cycles. Joint with Bill Cuckler. |
New Market Models and Algorithms
3:05-5:05pm, CCB Lecture Hall 16
| The notion of a "market" has undergone a paradigm shift with the Internet -- totally new and highly successful markets have been defined and launched by companies such as Google, Yahoo!, Amazon, MSN and Ebay. Another major change is the availability of massive computational power for running these markets in a centralized or distributed manner. In view of these new realities, the study of market equilibria, an important, though essentially non-algorithmic, theory within Mathematical Economics, needs to be revived and rejuvenated with new models, ideas, and an inherently algorithmic approach. The last five years has seen a surge of activity, within Algorithmic Game Theory, on obtaining algorithms for market equilibria. Interestingly enough, some of this work has already contributed handsomely to the theory of algorithms as well. In this two lecture series I will provide a historical perspective on the study of markets as well as give an in-depth feel for the exciting work going on within Algorithmic Game Theory. |
Additive Approximation for Edge-Deletion Problems
4:05, Skiles 255
| A graph property is monotone if it is closed under removal of vertices and edges. In this talk we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E_P(G). Our first result states that for any monotone graph property P, any \epsilon> 0 and n-vertex input graph G one can approximate E_P(G) up to an additive error of \epsilon n^2. Given the above, a natural question is for which monotone properties can one obtain better additive approximations of E_P(G). Our second main result essentially resolves this problem by giving a precise characterization of the monotone graph properties for which such approximations exist. We will show that for any dense monotone property, that is, a property for which there are graphs on n vertices with \Omega (n^2) edges that satisfy it, it is NP-hard to approximate E_P(G) up to an additive error of n^{2-\delta}, for any fixed positive \delta. The proof requires several new ideas and involves tools from Extremal Graph Theory together with spectral techniques. Interestingly, prior to this work it was not even known that computing E_P(G) precisely for dense monotone properties is NP-hard. We thus answer (in a strong form) a question of Yannakakis raised in 1981. (Joint work with N. Alon and A. Shapira.) |
Algorithmic Self-Assembly: Models and Problems
11:05, Skiles 255
| DNA Self-assembly has emerged as an important technique for molecular computation and nano-technology. At these scales, self- assembly is governed by simple (and local) probabilistic rules for growth, making it amenable to algorithmic techniques. We will discuss two important challenges in algorithmic self-assembly: robustness and efficiency. This talk will present recent results, and also attempt to provide a road-map of open problems. |
Voronoi Percolation
4:00pm, Skiles 269
One and two stage minimum spanning tree problems: average case analysis
4:00pm, Skiles 269
| Let the edge weights of a graph G be given independent uniform [0,1] random costs. We review some old results about the expected value of the minimum spanning tree. We then consider a 2-stage problem where independent weights are given for Monday and Tuesday. On Monday we might buy some edges knowing only the distribution of the edge weights for Tuesday and then buy the remaining edges on Tuesday. We present some results on this and on a directed version. |
Constant Round Oblivious Transfer in the Bounded Storage Model
4:30pm, Skiles 255
| The bounded storage model, introduced by Maurer, is an alternative to the standard complexity based model for cryptography. In contrast to the complexity based model, the bounded storage model assumes that the adversary is space-bounded, and provides provable information-theoretic security by employing a public random string R whose length exceeds the space bound. Security is guaranteed against a malicious adversary who remembers almost all information about R, while an honest party is only required to store a small fraction of R. Oblivious transfer is a fundamental cryptographic primitive on which many two-party and multi-party cryptographic protocols can be based. It involves two parties, Alice who has two secrets s_0 and s_1, and Bob who has a secret bit b. Roughly speaking, in a secure oblivious transfer protocol, Alice sends s_0 and s_1 to Bob in such a way that (1) Bob receives s_b but learns nothing about the other secret, and (2) Alice learns nothing about b. We construct a 5-round protocol for oblivious transfer in the bounded storage model. This improves on previous works that required polynomially many rounds. Our protocol also significantly improves upon the previous ones in terms of total bit communication complexity. The main ingredients of our construction are powerful tools from pseudo randomness, an area that is concerned with generating "random looking" objects with no or little randomness. In particular, our construction uses randomness extractors, averaging samplers, and almost t-wise independent permutations. This talk will be self-contained, and assume no previous knowledge in cryptography and pseudo randomness. This is joint work with Danny Harnik, Alon Rosen and Ronen Shaltiel. |
<
Full-Text Page >