CATS Seminar: Spring 2012  (Capital Area Theory Seminar (CATS))

 

 

 

Schedule

CATS usually meets on Fridays 1:00pm- 2:00 pm  CSIC3118   but some talks may be at a different place and time.

For additional information send email to Samir Khuller.

If you want to receive announcements of upcoming talks join the theory-local mailing list.

CATS Talks from previous semesters

• 2011: Spring | Fall
• 2010: Spring | Fall
• 2009: Spring 
• 2008: Spring | Fall
• 2007 : Spring| Fall
• 2006 : Fall | Spring
• 2005 : Fall | Spring
• 2004 : Fall | Spring
• 2003 : Fall | Spring
• 2002 : Fall | Spring
• 2001 : Fall
• 2000 : Fall | Spring
• 1999 : Fall | Spring
• 1998 : Fall | Spring
• 1997 : Fall | Spring
• 1996 : Summer and Fall | Spring
• 1995 : Fall

Other cats

Combinatorial Algorithms Test Sets Collaborative Agent Technology System Computing: The Australasian Theory Symposium

Abstracts

Title

Speaker

Affiliation

Abstract:
Abstract Body.

Single Processor Scheduling with Monotone Penalties

Rohit Khandekar

IBM T. J. Watson research center

Abstract:
We will consider single processor preemptive scheduling with job-dependent setup times. In this model, a job-dependent setup time is incurred when a job is started for the .rst time, and each time it is restarted after preemption. This model is a common generalization of preemptive scheduling, and actually of non- preemptive scheduling as well. The objective is to minimize the sum of any general non-negative, non- decreasing cost functions of the completion times of the jobs . this generalizes objectives of minimizing weighted .ow time, .ow-time squared, tardiness or the number of tardy jobs among many others. I will sketch a randomized polynomial time of.ine O(1)-speed O(1)-approximation algorithm for this problem. Without speedup, no polynomial time .nite multiplicative approximation is possible unless P = NP. This is a joint work with Kirsten Hildrum, Deepak Rajan and Joel Wolf.

Provable Security and Beyond

Dominique Schroeder

University of Maryland

Abstract:
One of the cornerstones of modern cryptography is that new constructions of cryptographic schemes should come with a proof of security showing that the scheme satisfies a given definition of security, under certain assumptions and in a specific model. While techniques used to prove security are quite powerful, for some schemes no security proofs are known. Interestingly, it is sometimes possible to show the impossibility of proving security (subject to certain constraints on the proof); this shows that our inability to find such proofs is not a failure, but rather due to some fundamental limitations. In the opposite direction, and somewhat surprisingly, impossibility proofs can sometimes lead to positive results by guiding cryptographers to new constructions. I illustrate the above by discussing two recent results of my own. The first result (Eurocrypt 2010) shows the impossibility of three-round blind signature schemes based on non-interactive assumptions in the standard model. This result implies, in particular, limitations on provable security of the well-known blind signature schemes of Chaum and Pointcheval-Stern. The second part of my talk discusses how to bypass this impossibility result and construct a two-round blind signature scheme based on non-interactive assumptions in the standard model (Crypto '11).

Frugal Auctions For Vertex Covers, Flows, and Cuts

David Kempe

University of Southern California

Abstract:
In this talk, we investigate auction mechanisms for combinatorial reverse auctions. The model is that selfish agents own elements, and the auctioneer wants to purchase a feasible set for some problem from the agents. The specific problems that we study are: 1. Vertex Cover: The agents own the vertices of a graph, and the auctioneer wants to purchase a vertex cover from them. 2. k-Flow: The agents own edges, and the auctioneer wants to buy k edge-disjoint paths from a source to a sink. 3. Cut: The agents own edges, and the auctioneer wants to purchase an s-t cut. In such settings, it is commonly assumed that selfish agents will act in such a way as to maximize their own profit; in particular, this may include misrepresenting their true cost for letting the auctioneer use their resources (edges or vertices). Thus, mechanisms should have severable desirable properties. 1. Truthfulness: selfish agents want to reveal their true costs. 2. Frugality: the mechanism does not pay much more than "necessary" to achieve truthfulness. 3. Computability: the mechanism can be computed in polynomial time. We begin this talk with a brief introduction to auctions, truthfulness, and the notion of frugality. After presenting a novel and optimal mechanism for Vertex Cover, we show how to use the Vertex Cover mechanism as a useful design methodology for other problems, by deriving from it competitive mechanisms for flows and cuts. We end with a number of interesting open problems. (Joint work with Mahyar Salek and Cristopher Moore, which appeared in FOCS 2010; this talk will also discuss an independent FOCS 2010 paper by Ning Chen, Edith Elkind, Nick Gravin, and Fedor Petrov, including the similarities and differences between the ideas.)

Influence, Bribery, and Manipulation in Voting Systems: Current Results and Ongoing Work

Nicholas Mattei

University of Kentucky

Abstract:
Computational Social Choice (ComSoc) is an emergent and vibrant area of research in Computer Science. ComSoc, in broad terms, is concerned with the design and analysis of systems and processes for collective decision making. Voting and election procedures are common ways that groups of agents can arrive at a collective decision. Unfortunately, foundational results in the field of Social Choice prove that it is impossible to devise a voting procedure for three or more candidates that is immune to manipulation (some agent will, in some cases, have an incentive to misrepresent his true preferences). Our research focuses on the manipulation as well as the bribery problem in voting and ranking procedures. Most existing research related to bribery and manipulation assumes an agent has access to perfect information about the preferences of all agents within the system. Our ongoing research focuses on the case where an agent only has access to probabilistic information about other agents. preferences. This talk will provide a brief introduction to ComSoc with a review of some major results related to election systems, result from our theoretical work on election systems where voters. preferences are modeled as probabilities, and a brief overview of our empirical work on testing the robustness of voting and ranking systems.

Greedy Sequential Maximal Independent Set is Parallel On Average

Jeremy Fineman

Georgetown University

Abstract:
The greedy sequential algorithm for finding maximal independent set (MIS) of an undirected graph loops over the vertices in order, adding a vertex to the resulting set if and only if no previous neighboring vertex has been added. This talk shows that for any graph, a trivial parallelization of this sequential algorithm is in fact usually highly parallel (polylogarithmic time) as long as the initial ordering on vertices is random. Specifically, in the sequential loop, each iterate (vertex) depends only on a subset of the previous iterates (i.e., knowing that any one of a vertex's neighbors is in the MIS is enough of exclude it from the MIS, and knowing that it has no earlier neighbors is enough to accept it). Iterates may therefore be processed in parallel as long as all earlier iterates on which they depend have also been processed. This leads to a dependence structure among iterates. If this structure is shallow, then running iterates in parallel while respecting dependencies can lead to an efficient implementation mimicking the sequential algorithm. The MIS found by the greedy sequential algorithm (and its parallelization) is called the lexicographically first MIS (LFMIS). Finding a LFMIS in general is P-complete, meaning that it is unlikely that any fast parallel algorithm exists. This talk shows, perhaps surprisingly, that for a random vertex ordering of an arbitrary undirected graph, the dependence length among iterates is polylogarithmic with high probability, and hence the LFMIS can be found quickly in parallel. This result extends previous results showing polylogarithmic dependence length only for random graphs. Beyond theoretical interest, the result has practical implications. Firstly, it allows for a simple and efficient parallel implementation that can trade-off work with depth, yielding a parallel implementation that outperforms the standard Luby's algorithm. Second, once the vertex ordering is fixed, the approach guarantees the same result whether run sequentially or in parallel. Such determinism can be an important property of parallel algorithms, particularly where debugging is concerned.

Quantum algorithms for testing graph expansion and bipartiteness

Yi-Kai Liu

National Institute of Standards and Technology

Abstract:
We show how quantum computers can speed up two classical algorithms, due to Goldreich and Ron, for testing bipartiteness and expansion of bounded-degree graphs. We give quantum algorithms that solve these problems in time O(N^(1/3)), beating the Omega(sqrt(N)) classical lower bound; this follows from Ambainis' quantum algorithm for element distinctness. For testing expansion, we also prove an Omega(N^(1/4)) quantum query lower bound, thus ruling out the possibility of an exponential quantum speedup; this is proved using the polynomial method and some combinatorics. I'll also give a gentle introduction to quantum walks, which are the underlying technique in these algorithms. (This is joint work with Andris Ambainis and Andrew Childs.)

How to use Lagrangian-Relaxation Algorithms to solve Packing and Covering Problems

Neal Young

UC Riverside

Abstract:
Following a brief review of (some of) the history of Lagrangian-relaxation algorithms, I will summarize recent results in the area in a concrete form, with the aim of making it easier to understand how to apply those results. Namely, given any linear program (LP) that includes some packing constraints and/or some covering constraints, the packing and/or covering constraints can be "dualized", replacing the packing constraints by a carefully chosen linear combination of the packing constraints, and likewise for the covering constraints. This replaces all m packing/covering constraints by just one (or two) constraints, and gives an LP relaxation LP. of the problem that is combinatorially simpler than the original problem. Why is this useful? iven any algorithm alg.' for the simpler problem LP', there is a simple algorithm for the original problem that calls alg' at most O(min(m, width) log(m)/epsilon^2) times, then returns an epsilon-approximate solution to the original problem. Here m is the number of constraints, and width is a technical parameter. I will illustrate the ideas using zero-sum matrix games, the Held-Karp lower bound on TSP, the "configuration LP" for bin packing, and multi-commodity flow problems.

Polyhedral Clinching Auctions and the AdWords Polytope

Gagan Goel

Google Research

Abstract:
Motivated by ad auctions, a mechanism design problem that has come to the fore is that of designing auctions in the presence of budget-constrained bidders. Recent results in this direction extend Ausubel's clinching auction to give Pareto-optimal auctions for specific allocation scenarios such as multi-unit supply (Dobzinski et al) and certain matching markets (Fiat et al). A natural question one must ask is: For what all allocation scenarios can we design a Pareto-optimal auction in the presence of budget-constrained bidders? In this work, we give a Pareto-optimal auction for any allocation scenario that can be described using a polymatroid. This not only generalizes the previous known results, but is widely applicable because of the rich structure of polymatroids. We also show that a very general model of Adwords that includes multiple slots and multiple keywords can be described using a polymatroid. Finally we give an impossibility result for more general allocation scenarios. As a byproduct, we also get an impossibility result for multi-unit auctions with decreasing marginal utilities. This is a joint work with Vahab Mirrokni and Renato Paes Leme.

Survivable Network Design with Node and Edge Costs

Debmalya Panigrahi

MIT

Abstract:
Survivable network design (SND) is a suite of algorithmic problems that focus on designing minimum cost networks satisfying desired robustness characteristics. Over the last decade, networking technology has gradually embraced wireless infrastructure, where a substantial fraction of the deployment cost comes from network nodes (e.g. cellular base stations). This motivates us to generalize the traditional edge-weighted cost model in SND problems to one that is able to handle fixed or variable costs on nodes as well. In this talk, I will present two sets of SND problems that attempt to bridge this gap. In the first part of the talk, I will give the first poly-logarithmic competitive algorithm for the online steiner tree problem with node and edge costs. This is joint work with Seffi Naor and Mohit Singh. In the second part of the talk, I will introduce a new suite of SND problems called network activation problems that generalize node costs and several other previously studied cost models. In these problems, instead of a fixed cost at a node, the algorithm designer must choose the cost that she wants to pay at a node, and the activation of a link depends on the cost paid at its two end-points. I will give approximation algorithms and(matching) hardness results for several well-studied SND problems in this framework.

Quantum Algorithms for Quantum Field Theories

Stephen P. Jordan

National Institute of Standards and Technology

Abstract:
Quantum field theory reconciles quantum mechanics and special relativity, and plays a central role in many areas of physics. I will discuss a polynomial-time quantum algorithm for simulating a quantum field theory, which I developed in collaboration with Keith Lee and John Preskill. Such simulations are believed to require exponential time on classical computers. No prior knowledge of quantum algorithms or quantum field theory will be assumed.

Finding Maximal Independent Sets in Hypergraphs in Parallel

Ioana Bercea

University of Maryland

Abstract:
In 1990, Beame and Luby developed a parallel randomized algorithm for finding maximal independent subsets in hypergraphs in which the maximum edge size is bounded by a constant. Two years later, Kelsen discovered a flaw in their analysis and developed the machinery for correcting it. Despite the intuitive nature of the algorithm, the analysis is highly elaborated and involves using an upper tail of sums of dependent random variables defined on the edges of a hypergraph, which is similar but predates the one by Kim and Vu. Moreover, the total running time of the algorithm is too large for it to be efficiently implemented. We will review the general components of the analysis and provide some insight as to the certain choices that Kelsen makes in developing the machinery.

Perfect Matchings in Regular Bipartite Graphs

Sanjeev Khanna

University of Pennsylvania

Abstract:
The problem of finding a perfect matching in a regular bipartite graph is a classical problem with applications to edge-colorings, routing, and scheduling, and is closely related to the Birkhoff-von Neumann decomposition of doubly stochastic matrices. A sequence of improvements over the years have culminated in a linear-time algorithm for this problem. This talk considers the question if a perfect matching can be computed in sub-linear time in a regular bipartite graph. We show that using randomization, one can obtain surprisingly efficient sub-linear time algorithms for this problem. In contrast, we show that no deterministic algorithm can do better than linear time. This is based on joint work with Ashish Goel and Michael Kapralov at Stanford University.

Identity Testing of Tensors, Low Rank Recovery and Compressed Sensing

Michael Forbes

MIT

Abstract:
A matrix A naturally defines a quadratic form x^tAy. If A is of rank <=r, then the rank<=r decomposition of A corresponds naturally to a size ~2nr circuit for computing the quadratic form. It is clear how to perform "white box" polynomial identity testing for such circuits, and the motivating question for this work is to explore black-box identity testing. The probabilistic method shows that there is a size ~2nr hitting set for such polynomials. In this work we match this bound (over large fields), which is optimal up to constant factors. Further, we explore how A can be reconstructed from the evaluations of the quadratic form. Similar probabilistic constructions show that there exist ~4nr evaluations which determine any such matrix A. Again, we match this bound (over large fields) with an explicit construction, and furthermore give a polynomial-time algorithm to reconstruct A from such evaluations. More generally, we show an efficient reduction from (exact) low-rank matrix reconstruction to (exact) sparse recovery. This reduction is novel in the compressed-sensing realm as it is field independent and unrelated to convex optimization. Finally, we use these results recursively to derive the first quasipolynomial-sized hitting set for set-multilinear, depth 3 algebraic circuits, as these circuits correspond to higher-dimensional matrices, known as tensors. Joint work with Amir Shpilka, to appear in STOC 2012.

Improved Approximation Algorithms for Directed Steiner Forest

Guy Kortsarz

Rutgers University-Camden

Abstract:
We consider the {\sf $k$-Directed Steiner Forest} ($k$-{\sf DSF}) problem: Given a directed graph $G=(V,E)$ with edge costs, a collection ${\cal D} \subseteq V \times V$ of ordered node pairs, and an integer $k \leq |D|$, find a minimum cost subgraph $H$ of $G$ that contains an $st$-path for (at least) $k$ pairs $(s,t) \in {\cal D}$. When $k=|{\cal D}|$, we get the {\sf Directed Steiner Forest} ({\sf DSF}) problem. The best known approximation ratios for these problems are: $\tilde{O}(k^{2/3})$ for $k$-{{\sf DSF}} by Charikar et~al. \cite{CCC}, and $O(k^{1/2 + \varepsilon})$ for {{\sf DSF}} by Chekuri et~al. \cite{CEGS}. Our main result is achieving the first sub-linear in terms of $n=|V|$ approximation ratio for {\sf DSF}. Specifically, we give an $O(n^\varepsilon \cdot \min\{n^{4/5},m^{2/3}\})$-approximation scheme for {\sf DSF}. For $k$-{\sf DSF} we give a simple greedy $O(k^{1/2 + \varepsilon})$-approximation algorithm. This improves upon the best known ratio $\tilde{O}(k^{2/3})$ by Charikar et~al. \cite{CCC}, and (almost) matches, in terms of $k$, the best ratio known for the undirected variant \cite{GHNR}. This algorithm uses a new structure called {\em start-junction tree} which may be of independent interest.

Alignment-Free Phylogenetic Reconstruction

Henry Lin

University of Maryland

Abstract:
The goal of phylogeny reconstruction is to recover the past evolutionary history of multiple species (i.e. how the species evolved from each other) only given the current DNA sequences of the present species. Since not many people may be familiar with phylogeny reconstruction, I'll formally define the problem and explain some of the basic techniques used to solve the problem. Then I'll give a high level overview of the recent paper below, which shows you can recover the evolutionary history even in the presence of insertions and deletions on the species' DNA sequences, improving on the prior work which only allowed substitutions in the genome sequence. We present an efficient phylogenetic reconstruction algorithm allowing insertions and deletions which provably achieves a sequence-length requirement (or sample complexity) growing polynomially in the number of taxa. Our algorithm is distance-based, that is, it relies on pairwise sequence comparisons. More importantly, our approach largely bypasses the difficult problem of multiple sequence alignment. Original work by: C. Daskalakis and S. Roch. Alignment-Free Phylogenetic Reconstruction. Proceedings of RECOMB 2010, 123-137.

Mesh Repair and Reconstruction of City-Scale Urban Models

Jyh-Ming Lien

George Mason University

Abstract:
Since the introduction of the concept of Digital Earth, almost every major international city has been re-constructed in the virtual world. A large volume of geometric models describing urban objects has become freely available in the public domain via software like ArcGlobe and Google Earth. Although mostly created for visualization, these urban models can benefit many applications beyond visualization including city scale evacuation planning and earth phenomenon simulations. However, these models are mostly loosely structured and implicitly defined and require tedious manual preparation that usually takes weeks if not months before they can be used. Designing algorithms that can robustly and efficiently handle unstructured urban models at the city scale becomes a main technical challenge. In this talk, I will present a framework that generates seamless 3D architectural models from 2D ground plans with elevation and height information. Due to measurement and manual errors, these ground plans usually contain small, sharp, and various (nearly) degenerate artifacts. In this paper, we show both theoretically and empirically that our framework is efficient and numerically stable.

Bio:
Jyh-Ming Lien is an Assistant Professor in the Department of Computer Science and is affiliated with the Motion and Shape Computing (MASC) group and the Autonomous Robotics Laboratory at George Mason University. His research area is computational geometry, CAD/CAGD, algorithmic robotics, and computer graphics. His recent work focuses on shape decomposition, approximation and reconstruction of complex and dynamic 3D geometries.

Streaming Balanced Graph Partitioning for Large Distributed Graphs

Isabelle Stanton

UC Berkeley

Abstract:
Extracting knowledge by performing computations on graphs is becoming increasingly challenging as graphs grow in size. A standard approach distributes the graph over a cluster of nodes, but performing computations on a distributed graph is expensive if large amount of data have to be moved. Without partitioning the graph, communication quickly becomes a limiting factor in scaling the system up. Existing graph partitioning heuristics incur high computation and communication cost on large graphs, sometimes as high as the future computation itself. Observing that the graph has to be loaded into the cluster, we ask if the partitioning can be done at the same time with a lightweight streaming algorithm. In the first part of this talk, we propose natural, simple heuristics and compare their performance to hashing and METIS, a fast, o ffline heuristic. We show on a large collection of graph datasets that our heuristics are a signifcant improvement, with the best obtaining an average gain of 76%. The heuristics are scalable in the size of the graphs and the number of partitions. Using our streaming partitioning methods, we are able to speed up PageRank computations on Spark, a distributed computation system, by 18% to 39% for large social networks. The second part of the talk focuses on theoretical aspects of the problem. I will discuss lower bounds for the general performance of any streaming balanced graph partitioning algorithm. In addition, I will discuss methods for analyzing the performance of the best heuristics on a class of random graphs.
Bio:
Isabelle Stanton is a PhD student at UC Berkeley in the Theory group, advised by Satish Rao. Her primary research interests are graph algorithms, randomized algorithms, computational social choice and learning theory.