tag:talks.cs.umd.edu,2005:/lists/6/feedCATS2018-06-18T20:59:12-04:00tag:talks.cs.umd.edu,2005:Talk/192012-02-14T12:30:39-05:002012-02-14T12:30:39-05:00https://talks.cs.umd.edu/talks/19Frugal Auctions For Vertex Covers, Flows, and Cuts<a href="http://www-bcf.usc.edu/~dkempe/">David Kempe - University of Southern California </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, February 17, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <pre>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.)</pre>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/272012-02-22T03:16:48-05:002012-02-22T03:16:48-05:00https://talks.cs.umd.edu/talks/27Influence, Bribery, and Manipulation in Voting Systems: Current Results and Ongoing Work<a href="http://www.ramble.nickmattei.net/"> Nicholas Mattei - University of Kentucky </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, February 24, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/362012-02-28T23:54:41-05:002012-02-28T23:54:41-05:00https://talks.cs.umd.edu/talks/36Greedy Sequential Maximal Independent Set is Parallel On Average<a href="http://www.cs.georgetown.edu/~jfineman/">Jeremy Fineman - Georgetown University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, March 2, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
The greedy sequential algorithm for finding maximal independent set<br>
(MIS) of an undirected graph loops over the vertices in order, adding<br>
a vertex to the resulting set if and only if no previous neighboring<br>
vertex has been added. This talk shows that for any graph, a trivial<br>
parallelization of this sequential algorithm is in fact usually highly<br>
parallel (polylogarithmic time) as long as the initial ordering on<br>
vertices is random. Specifically, in the sequential loop, each<br>
iterate (vertex) depends only on a subset of the previous iterates<br>
(i.e., knowing that any one of a vertex's neighbors is in the MIS is<br>
enough of exclude it from the MIS, and knowing that it has no earlier<br>
neighbors is enough to accept it). Iterates may therefore be processed<br>
in parallel as long as all earlier iterates on which they depend have<br>
also been processed. This leads to a dependence structure among<br>
iterates. If this structure is shallow, then running iterates in<br>
parallel while respecting dependencies can lead to an efficient<br>
implementation mimicking the sequential algorithm.<br>
<br>
The MIS found by the greedy sequential algorithm (and its<br>
parallelization) is called the lexicographically first MIS (LFMIS).<br>
Finding a LFMIS in general is P-complete, meaning that it is unlikely<br>
that any fast parallel algorithm exists. This talk shows, perhaps<br>
surprisingly, that for a random vertex ordering of an arbitrary<br>
undirected graph, the dependence length among iterates is<br>
polylogarithmic with high probability, and hence the LFMIS can be<br>
found quickly in parallel. This result extends previous results<br>
showing polylogarithmic dependence length only for random graphs.<br>
<br>
Beyond theoretical interest, the result has practical implications.<br>
Firstly, it allows for a simple and efficient parallel implementation<br>
that can trade-off work with depth, yielding a parallel implementation<br>
that outperforms the standard Luby's algorithm. Second, once the<br>
vertex ordering is fixed, the approach guarantees the same result<br>
whether run sequentially or in parallel. Such determinism can be an<br>
important property of parallel algorithms, particularly where<br>
debugging is concerned.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/412012-03-06T22:59:06-05:002012-03-06T22:59:06-05:00https://talks.cs.umd.edu/talks/41Quantum algorithms for testing graph expansion and bipartiteness <a href="https://sites.google.com/site/yikailiu00/">Yi-Kai Liu - National Institute of Standards and Technology </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, March 9, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.)<br>
</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/532012-03-13T22:02:39-04:002012-04-03T15:12:42-04:00https://talks.cs.umd.edu/talks/53Quantum Algorithms for Quantum Field Theories<a href="http://www.nist.gov/itl/math/sjordan.cfm">Stephen P. Jordan - National Institute of Standards and Technology</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, April 6, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
<br>
Quantum field theory reconciles quantum mechanics and special<br>
relativity, and plays a central role in many areas of physics. I will<br>
discuss a polynomial-time quantum algorithm for simulating a quantum<br>
field theory, which I developed in collaboration with Keith Lee and<br>
John Preskill. Such simulations are believed to require exponential<br>
time on classical computers. No prior knowledge of quantum algorithms<br>
or quantum field theory will be assumed.</p>
<br><b>Bio:</b> <p>
Stephen Jordan got his Bachelor's degree in physics in 2003 from Penn State, and his PhD in physics in 2008 from MIT. After a postdoc at Caltech, he joined NIST's Applied and Computational Mathematics division in April 2011. He works on quantum algorithms, quantum complexity, and post-quantum cryptography. He also maintains the "Quantum Algorithm Zoo" (<a href="http://math.nist.gov/quantum/zoo/">http://math.nist.gov/quantum/<wbr></wbr>zoo/</a>), a comprehensive repository of quantum algorithms.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/632012-03-27T19:31:17-04:002012-03-27T19:31:17-04:00https://talks.cs.umd.edu/talks/63Polyhedral Clinching Auctions and the AdWords Polytope<a href="http://research.google.com/pubs/GaganGoel.html">Gagan Goel - Google Research</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, March 30, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/832012-04-10T12:31:33-04:002012-04-10T12:31:33-04:00https://talks.cs.umd.edu/talks/83Survivable Network Design with Node and Edge Costs<a href="http://people.csail.mit.edu/debmalya/">Debmalya Panigrahi - MIT </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, April 13, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/902012-04-17T15:22:21-04:002012-04-17T15:22:21-04:00https://talks.cs.umd.edu/talks/90Perfect Matchings in Regular Bipartite Graphs <a href="http://www.cis.upenn.edu/~sanjeev/">Sanjeev Khanna - University of Pennsylvania</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, April 20, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1052012-04-24T21:24:18-04:002012-04-24T21:24:18-04:00https://talks.cs.umd.edu/talks/105Identity Testing of Tensors, Low Rank Recovery and Compressed Sensing<a href="http://www.mit.edu/~miforbes/">Michael Forbes - MIT </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, April 27, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1102012-05-01T17:09:46-04:002012-05-01T17:09:46-04:00https://talks.cs.umd.edu/talks/110Finding Maximal Independent Sets in Hypergraphs in Parallel<a href="http://www.cs.umd.edu/~ioana">Ioana Bercea - University of Maryland </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, May 4, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1102012-05-01T17:09:46-04:002012-05-01T17:09:46-04:00https://talks.cs.umd.edu/talks/110Finding Maximal Independent Sets in Hypergraphs in Parallel<a href="http://www.cs.umd.edu/~ioana">Ioana Bercea - University of Maryland </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, May 4, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1142012-05-08T14:40:51-04:002012-05-08T14:40:51-04:00https://talks.cs.umd.edu/talks/114Alignment-Free Phylogenetic Reconstruction<a href="http://www.cbcb.umd.edu/~henrylin/">Henry Lin - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, May 11, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1152012-05-08T20:59:19-04:002012-05-08T20:59:19-04:00https://talks.cs.umd.edu/talks/115Improved Approximation Algorithms for Directed Steiner Forest<a href="http://crab.rutgers.edu/~guyk/">Guy Kortsarz - Rutgers University-Camden </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Thursday, May 10, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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 imes 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: $ ilde{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 $ ilde{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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1182012-05-17T10:53:30-04:002012-05-17T10:53:30-04:00https://talks.cs.umd.edu/talks/118Mesh Repair and Reconstruction of City-Scale Urban Models <a href="http://www.cs.gmu.edu/~jmlien/">Jyh-Ming Lien - George Mason University </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, May 18, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br><b>Bio:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1202012-05-17T23:09:50-04:002012-05-20T15:21:31-04:00https://talks.cs.umd.edu/talks/120Streaming Balanced Graph Partitioning for Large Distributed Graphs<a href="http://www.cs.berkeley.edu/~isabelle/">Isabelle Stanton - UC Berkeley </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Wednesday, May 23, 2012, 11:00 am-12:00 pm<br><br><b>Abstract:</b> <p>
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.</p>
<br><b>Bio:</b> <p>
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.</p>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1252012-06-19T10:38:17-04:002012-06-20T14:46:24-04:00https://talks.cs.umd.edu/talks/125Revisiting submodular function maximization<a href="http://www.cs.toronto.edu/~bor/">Allan Borodin - University of Toronto </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2120 Computer Science Instructional Center (CSI)</a><br>Monday, June 25, 2012, 2:30-3:30 pm<br><br><b>Abstract:</b> <pre>Submodular function maximization has generated a substantial amount of
recent activity, both in terms of applications as well as new algorithms
obtaining improved approximation ratios. There is a nice interplay
with algorithmic ideas (i.e. theory) being applied to specific problems
and then in turn
these problems suggesting some new concepts.
One example is the problem
of ranking with diversity where the goal is (for example)
to choose a subset S of documents so as to maximize the ``quality'' of
the documents in S (say as measured by a submodular function subject to a
matroid constraint) while
insuring that these documents are diverse in some sense (e.g. maximizing
the sum of pairwise ``distances'' between documents). We utilize some ideas
about greedy and local search algorithms to extend previous results for
linear quality functions subject to a cardinality (i.e. uniform matroid)
constraint.
The analysis also
suggests a new class of
``weakly submodular functions'' (due to Yuli Ye) which include
submodular functions as well as the sum of pairwise distances.
(This is work with Yuli Ye and Hyun Chul Lee).
Another example of a new abstraction of ideas is the use of ``non-oblivious''
local search as applied by Berman to weighted k-set packing and more generally
independence in k+1 claw free graphs. This has led to a new class of
independence systems called
``k-exchangeable systems''. Within this class of independence systems,
non-oblivious local search provides improved approximation bounds.
(This is recent work by Justin Ward.)
</pre>
<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1652012-09-04T10:30:36-04:002012-09-15T09:02:49-04:00https://talks.cs.umd.edu/talks/165Beyond Swinging: Geometric Dissections that Swing or Twist<a href="http://www.cs.purdue.edu/people/faculty/gnf/">Greg N. Frederickson - Professor of Computer Science, Purdue University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Monday, September 24, 2012, 11:00 am-12:00 pm<br><br><b>Abstract:</b> <p>A geometric dissection is a cutting of a geometric figure into pieces that can be rearranged to form another figure. Some dissections can be connected with hinges so that the pieces form one figure when swung one way on the hinges, and form the other figure when swung another way. In addition to using "swing hinges", which allow rotation in the plane, we can use "twist hinges", which allow one piece to be flipped over relative to another piece via rotation by 180 degrees through a third dimension. Furthermore, we can use "fold hinges", which allow rotation along a shared edge, a motion that is akin to folding.</p>
<p>This talk will introduce a variety of twist-hinged and fold-hinged dissections of regular polygons and stars, and other figures such as polyominoes. The emphasis will be on both appreciating and understanding these fascinating mathematical recreations. I will employ algorithmic and tessellation-based techniques, as well as symmetry and other geometric properties, to design the dissections. The goal will be to minimize the number of pieces, subject to the dissection being suitably hinged. Animations and video will be used to demonstrate the hinged dissections, in addition to actual physical models.</p><br><b>Bio:</b> <p>Greg N. Frederickson received a Ph.D. in Computer Science from the University of Maryland in 1977. He is now a Professor of Computer Science at Purdue University, in West Lafayette, Indiana, with his primary area of research in the design and analysis of algorithms. He has served on the editorial boards of SIAM Journal on Computing, SIAM Journal on Discrete Mathematics, Algorithmica, and IEEE Transactions on Computers. He also pursues interests in mathematical recreations, specifically geometric dissection. On this topic he has published three books and a number of articles. He has twice won the George Polya Award from the Mathematical Association of America.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1662012-09-04T10:33:24-04:002012-09-22T17:19:03-04:00https://talks.cs.umd.edu/talks/166Profit Maximization of Seller over Social Markets <a href="http://www.umiacs.umd.edu/~hmahini/">Hamid Mahini - Postdoctoral Research, University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, September 28, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p>Despite the rapid growth, online social networks have not yet generated significant revenue. Most efforts to design a comprehensive business model for monetizing such social networks are based on contextual display advertising. An alternative way to monetize social networks is viral marketing, or advertising through word-of-mouth. This can be done by understanding the influences among buyers in a social network. The increasing popularity of these networks has allowed companies to collect and use information about inter-relationships among users of social networks. In particular, by designing certain experiments, these companies can determine how users influence each others’ activities.</p>
<p>In this talk, I will describe the optimal pricing for revenue maximization in the presence of positive network influences. In this model, the value of a digital good for a buyer is a function of the set of buyers who have already bought the item. The talk will focus on setting in which seller post a public price at each step. The price at each step is visible to all buyers, and each buyer might decide to buy the item based on her valuation for the item and the price of the item in that time step. The main questions which will be answered during this talk are: How can we use network influences in order to maximize the revenue? How re-pricing rate effects on revenue?</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1832012-09-18T09:19:06-04:002012-09-23T17:51:00-04:00https://talks.cs.umd.edu/talks/183An $O(\log k)$-competitive Algorithm for Generalized Caching <a href="http://www.dcs.warwick.ac.uk/~harry/">Harald Räcke - University of Warwick </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, October 5, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p>In the generalized caching problem, we have a set of pages and a cache of size $k$. Each page $p$ has a size $w_p\ge1$ and fetching cost $c_p$ for loading the page into the cache. At any point in time, the sum of the sizes of the pages stored in the cache cannot exceed $k$. The input consists of a sequence of page requests. If a page is not present in the cache at the time it is requested, it has to be loaded into the cache incurring a cost of $c_p$.</p>
<p>We give a randomized $O(\log k)$-competitive online algorithm for the generalized caching problem, improving the previous bound of $O(\log^2 k)$ by Bansal, Buchbinder, and Naor. This improved bound is tight and of the same order as the known bounds for the classic problem with uniform weights and sizes. We use the same LP based techniques as Bansal et al.\ but provide improved and slightly simplified methods for rounding fractional solutions online.</p>
<p>This is joint work with Anna Adamaszek, Artur Czumaj, and Matthias Englert.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1842012-09-18T09:25:38-04:002012-09-18T09:25:38-04:00https://talks.cs.umd.edu/talks/184Compact Representations: Thrtcl. Ids. n Prctc (joint with Colloquium Series)<a href="http://www.cs.princeton.edu/~moses/">Moses Charikar - Professor of Computer Science at Princeton University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2117 Computer Science Instructional Center (CSI)</a><br>Friday, September 21, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Compact representations are about taking a complicated data set and representing its elements using a very small number of bits, such that interesting things can be estimated from this highly compressed representation. Such tools are a central building block in the algorithmic toolkit for analysis of very large data sets, leading to orders of magnitude savings in storage space and running time. In this talk, we present simple methods to construct compact representations for estimating similarity. These schemes are simple and elegant enough to teach in an undergraduate class, yet powerful enough that they are actually used in practice in massive data sets, e.g. in eliminating near duplicates in search engines. The principles behind these constructions have important applications in other areas of theoretical computer science and I will sketch some of these connections.</p><br><b>Bio:</b> <p>Moses Charikar is a Professor of Computer Science at Princeton University. He received his undergraduate degree from the Indian Institute of Technology, Bombay in 1995 and his Ph.D. from Stanford University in 2000. He joined Princeton in 2001 after spending a year at Google Research. He is a winner of the best paper award at FOCS 2003, as well as a Sloan Fellow. He is broadly interested in the design and analysis of algorithms, with an emphasis on approximation algorithms for NP-hard problems, embeddings of metric spaces and algorithmic techniques for massive data sets.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1852012-09-18T09:27:24-04:002012-11-06T15:32:28-05:00https://talks.cs.umd.edu/talks/185Private Equilibrium Release, Large Games, and No-Regret Learning<a href="http://www.cis.upenn.edu/~aaroth/">Aaron Roth - Assistant Professor of Computer and Information Science, University of Pennsylvania</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, November 9, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p><span style="font-family: sans-serif; font-size: 13px; line-height: 19.03333282470703px;">We give mechanisms in which each of n players in a game is given their component of an (approximate) equilibrium in a way that guarantees differential privacy --- that is, the revelation of the equilibrium components does not reveal too much information about the utilities of other players. More precisely, we show how to compute an approximate correlated equilibrium (CE) under the constraint of differential privacy (DP), provided $n$ is large and any player's action affects any other's payoff by at most a small amount. Our results draw interesting connections between noisy generalizations of classical convergence results for no-regret learning, and the noisy mechanisms developed for differential privacy. Our results imply the ability to truthfully implement good social-welfare solutions in many games, such as games with small Price of Anarchy, even if the mechanism does not have the ability to enforce outcomes. We give two different mechanisms for DP computation of approximate CE. The first is computationally efficient, but has a suboptimal dependence on the number of actions in the game; the second is computationally inefficient, but allows for games with exponentially many actions. We also give a matching lower bound, showing that our results are tight up to logarithmic factors. Joint work with Michael Kearns, Mallesh Pai, and Jonathan Ullman.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1582012-08-26T12:20:46-04:002012-11-03T14:24:28-04:00https://talks.cs.umd.edu/talks/158Distinguished Lecture: Experiments in Social Computation<a href="http://www.cis.upenn.edu/~mkearns/">Michael Kearns - University of Pennsylvania</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2117 Computer Science Instructional Center (CSI)</a><br>Friday, November 16, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>What do the theory of computation, economics and related fields have to say about the emerging phenomena of crowdsourcing and social computing? Most successful applications of crowdsourcing to date have been on problems we might consider "embarrassingly parallelizable" from a computational perspective. But the power of the social computation approach is already evident, and the road cleared for applying it to more challenging problems.</p>
<p>In part towards this goal, for a number of years we have been conducting controlled human-subject experiments in distributed social computation in networks with only limited and local communication. These experiments cast a number of traditional computational problems --- including graph coloring, consensus, independent set, market equilibria, biased voting and network formation --- as games of strategic interaction in which subjects have financial incentives to collectively "compute" global solutions. I will overview and summarize the many behavioral findings from this line of experimentation, and draw broad comparisons to some of the predictions made by the theory of computation and microeconomics.</p><br><b>Bio:</b> <p>Michael Kearns is a professor of Computer and Information Science at the University of Pennsylvania, where he is the director of the new Penn program in Market and Social Systems Engineering (www.mkse.upenn.edu). His research interests include topics in machine learning, algorithmic game theory, social networks, computational finance and artificial intelligence. More information is available at <a href="http://www.cis.upenn.edu/~mkearns">www.cis.upenn.edu/~mkearns</a>.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/2">CS Department</a> ⋅ <a href="https://talks.cs.umd.edu/lists/17">CS Research Seminar</a><br>tag:talks.cs.umd.edu,2005:Talk/1602012-08-26T12:22:17-04:002012-11-03T14:25:15-04:00https://talks.cs.umd.edu/talks/160Distinguished Lecture: Enabling Innovation Inside the Network<a href="http://www.cs.princeton.edu/~jrex/">Jennifer Rexford - Princeton University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2117 Computer Science Instructional Center (CSI)</a><br>Friday, December 7, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Modern computer networks perform a bewildering array of tasks, from routing and traffic monitoring, to access control and server load balancing. Yet, managing these networks is unnecessarily complicated and error-prone, due to a heterogeneous mix of devices (e.g., routers, switches, firewalls, and network-address translators) with closed and proprietary configuration interfaces. The emergence of Software Defined Networking (SDN) is poised to change all this by offering a clean and open interface between networking devices and the software that controls them. In particular, many commercial switches support the OpenFlow protocol, and a number of campus, data-center, and backbone networks have deployed the new technology. Many example SDN applications (e.g., server load balancing, seamless virtual machine migration, traffic engineering, and energy-efficient networking) illustrate SDN's potential to transform future networks. Yet, while SDN makes it possible to program the network, it does not make it easy. Today's OpenFlow controllers offer very low-level APIs that mimic the underlying switch hardware. To reach SDN's full potential, we need to identify the right higher-level abstractions for creating (and composing) powerful applications. In the Frenetic project (www.frenetic-lang.org) at Princeton and Cornell, we are designing simple and intuitive abstractions for programming SDNs, including ways to query network state, compose application modules, update a set of switches, collect measurement data from servers, and virtualize the network topology. These abstractions substantially lower the barrier for innovating inside the network.</p><br><b>Bio:</b> <p>Jennifer Rexford is a Professor in the Computer Science department at Princeton University. From 1996-2004, she was a member of the Network Management and Performance department at AT&T Labs--Research. Jennifer is co-author of the book "Web Protocols and Practice" (Addison-Wesley, May 2001). She served as the chair of ACM SIGCOMM from 2003 to 2007. Jennifer received her BSE degree in electrical engineering from Princeton University in 1991, and her MSE and PhD degrees in computer science and electrical engineering from the University of Michigan in 1993 and 1996, respectively. She was the 2004 winner of ACM's Grace Murray Hopper Award for outstanding young computer professional.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/2">CS Department</a> ⋅ <a href="https://talks.cs.umd.edu/lists/17">CS Research Seminar</a><br>tag:talks.cs.umd.edu,2005:Talk/1922012-09-22T17:21:32-04:002012-10-11T10:24:31-04:00https://talks.cs.umd.edu/talks/192Bicriteria Online Matching: Maximizing Weight and Cardinality<a href="http://research.google.com/pubs/NitishKorula.html">Nitish Korula - Research Scientist at Google</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, October 12, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.03333282470703px; font-family: sans-serif; font-size: 13px;">Inspired by online ad allocation problems and applicability of various combinatorial techniques, many new results have been developed for online matching problems during the past decade. Most of the previous work deals with single objective functions, but there is a need to optimize multiple objective functions in advertising applications. In this talk, as an illustrative example motivated by display advertising problems, I will focus on simultaneously maximizing two objectives: the cardinality and the total weight of the matching.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.03333282470703px; font-family: sans-serif; font-size: 13px;">In particular, we consider a set of fixed nodes (ads) with capacity constraints, and a set of online items (pageviews) arriving one by one. Upon arrival of an online item i, a set of eligible fixed neighbors (ads) for the item is revealed, together with a weight w_ia for each eligible neighbor a. The problem is to assign each item to an eligible neighbor online, while respecting the capacity constraints; the goal is to maximize both the total weight of the matching and the cardinality (i.e. the total number of assigned items).</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.03333282470703px; font-family: sans-serif; font-size: 13px;">We obtain both approximation algorithms and hardness results for this problem: An (α,β)-approximation for this problem is a matching with weight at least α fraction of the best weight of the maximum weighted matching, and cardinality at least β fraction of the cardinality of maximum matching. I will discuss parametrized algorithms that permit smooth tradeoff curves between the objectives, and briefly touch upon inapproximability results which combine to yield a 'hardness curve' for the problem; these upper and lower bounds are always close, and coincide in tangents at 3 points.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.03333282470703px; font-family: sans-serif; font-size: 13px;">Joint work with Vahab Mirrokni and Morteza Zadimoghaddam</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2092012-10-11T10:27:47-04:002012-10-11T10:27:47-04:00https://talks.cs.umd.edu/talks/209Designing FPT Algorithms for Cut Problem using Randomized Contractions<a href="http://www.cs.umd.edu/~rchitnis/">Rajesh Chitnis - Ph.D. Student, University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, November 2, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p><span style="font-family: sans-serif; font-size: 13px; line-height: 19.03333282470703px;">We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely "randomized contractions". We apply our framework to obtain the first FPT algorithm for the Unique Label Cover problem, which is the basis of the Unique Games Conjecture. We also give new FPT algorithms with exponential speed up for the Steiner k-Cut and the Node Multiway Cut-Uncut problems. Our algorithms can handle real weights; to the best of our knowledge, the technique of important separators due to Marx does not work in the weighted case.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2102012-10-11T10:29:32-04:002012-10-11T10:29:32-04:00https://talks.cs.umd.edu/talks/210A Manipulability Dichotomy Theorem for Generalized Scoring Rules<a href="http://people.seas.harvard.edu/~lxia/index.htm">Lirong Xia - Postdoc at Center for Research on Computation and Society (CRCS), Harvard University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Monday, November 5, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p><span style="font-family: sans-serif; font-size: 13px; line-height: 19.03333282470703px;">Social choice studies ordinal preference aggregation with applications ranging from high-stakes political elections to low-stakes movie rating websites. One recurring concern is that of the robustness of a social choice (voting) rule to manipulation, bribery and other kinds of strategic behavior. A number of results have identified ways in which computational complexity can provide a new barrier to strategic behavior, but most of previous work focused on case-by-case analyses for specific social choice rules and specific types of strategic behavior. In this talk, I present a dichotomy theorem for the manipulability of a broad class of generalized scoring rules and a broad class of strategic behavior called vote operations. When the votes are i.i.d., then with high probability the number of vote operations that are needed to achieve the strategic individual's goal is 0, \Theta(\sqrt n), \Theta(n), or infinity. This theorem significantly strengthens previous results and implies that most social choice situations are more vulnerable to many types of strategic behavior than previously believed.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2112012-10-11T10:32:16-04:002012-11-13T11:05:00-05:00https://talks.cs.umd.edu/talks/211Applicant Auctions for Internet Top-Level Domains: Resolving Conflicts Efficiently<a href="http://www.cramton.umd.edu/">Peter Cramton - Professor of Economics at the University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, November 30, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p><span style="color: #000000; font-family: sans-serif; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 19.03333282470703px; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-size-adjust: auto; background-color: #ffffff; display: inline !important; float: none;">The prospect of using auctions to resolve conflicts among parties competing for the same top-level internet domains is described. In such an auction the winner’s payment is divided among the losers, whereas if the conflict is not resolved then ICANN will conduct an auction and retain the winner’s payment. For first-price and second-price sealed-bid auctions, we characterize equilibrium bidding strategies and provide examples, assuming bidders’ valuations are distributed independently and are either symmetrically or asymmetrically distributed. The qualitative properties of equilibria reveal novel features; for example, in a second-price auction a bidder might bid more than her valuation in order to drive up the winner’s payment. Even so, examples indicate that in symmetric cases a bidder’s expected profit is the same in the two auction formats. We then test in the experimental lab two auction formats that extent the setting from a single domain to the actual setting with many domains. The first format is a sequential first-price sealed-bid auction; the second format is a simultaneous ascending clock auction. The framing and subjects were chosen to closely match the actual setting. Subjects were PhD students at the University of Maryland in Economics, Computer Science, and Computer Engineering, with training in game theory and auction theory. Each subject played the role of an actual company (e.g., Google) and bid for domains (e.g., .book) consistent with the company’s applications. Subjects were given instructions explaining the auction and the equilibrium theory for the single-item case in relevant examples. Both formats achieved auction efficiencies of 98% in the lab. This high level of efficiency is especially remarkable in the case with asymmetric distributions—the format performed better than the simple single-item equilibrium despite the presence of budget constraints in the lab. This experiment together with previous results on the robustness of ascending auctions in general and simultaneous ascending clock auctions in particular suggest that the simultaneous ascending clock auction will perform best in this setting.</span></p><br><b>Bio:</b> <p><strong style="font-family: calibri, verdana, arial, sans-serif; font-size: 16px; line-height: 22px; text-align: justify;">Peter Cramton</strong><span style="font-family: calibri, verdana, arial, sans-serif; font-size: 16px; line-height: 22px; text-align: justify;"> is Professor of Economics at the University of Maryland. Since 1983, he has conducted research on auction theory and practice. This research appears in the leading economics journals. The main focus is the design of auctions for many related items. Applications include spectrum auctions, electricity auctions, and treasury auctions. On the practical side, he is Chairman of Market Design Inc., an economics consultancy founded in 1995, focusing on the design of auction markets. He also is Founder and Chairman of Cramton Associates LLC, which since 1993 has provided expert advice on auctions and market design. Since 2001, he has played a lead role in the design and implementation of electricity auctions in France and Belgium, gas auctions in Germany, and the world’s first auction for greenhouse gas emissions held in the UK in 2002. He has advised numerous governments on market design and has advised dozens of bidders in high-stake auction markets. Since 1997, he has advised ISO New England on electricity market design and was a lead designer of New England’s forward capacity auction. He led the design of electricity and gas markets in Colombia, including the Firm Energy Market, the Forward Energy Market, and the Long-term Gas Market. Since June 2006, he played a leading role in the design and development of Ofcom’s spectrum auctions in the UK. He has advised the UK, the US, and Australia on greenhouse gas auction design. He led the development of the FAA’s airport slot auctions for the New York City airports. He received his B.S. in Engineering from Cornell University and his Ph.D. in Business from Stanford University.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2122012-10-11T10:33:43-04:002012-12-10T14:20:38-05:00https://talks.cs.umd.edu/talks/212Approximating Large Frequency Moments with Pick-and-Drop Sampling <a href="http://www.cs.jhu.edu/~vova/">Vladimir Braverman - Assistant Professor in the Department of Computer Science in the Whiting School of Engineering at the Johns Hopkins University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, December 14, 2012, 3:30-4:30 pm<br><br><b>Abstract:</b> <p>Given data stream $D = \{p_1,p_2,...,p_m\}$ of size $m$ of numbers from $\{1,..., n\}$, the frequency of $i$ is defined as $f_i = |\{j: p_j = i\}|$. The $k$-th \emph{frequency moment} of $D$ is defined as $F_k = \sum_{i=1}^n f_i^k$. We consider the problem of approximating frequency moments in insertion-only streams for $k\ge 3$. For any constant $c$ we show an $O(n^{1-2/k}\log(n)\log^{(c)}(n))$ upper bound on the space complexity of the problem. Here $\log^{(c)}(n)$ is the iterative $\log$ function. To simplify the presentation, we make the following assumptions: $n$ and $m$ are polynomially far; approximation error $\epsilon$ and parameter $k$ are constants. We observe a natural bijection between streams and special matrices. Our main technical contribution is a non-uniform sampling method on matrices. We call our method a \emph{pick-and-drop sampling}; it samples a heavy element (i.e., element $i$ with frequency $\Omega(F_k)$) with probability $\Omega(1/n^{1-2/k})$ and gives approximation $\tilde{f_i} \ge (1-\epsilon)f_i$. In addition, the estimations never exceed the real values, that is $ \tilde{f_j} \le f_j$ for all $j$. As a result, we reduce the space complexity of finding a heavy element to $O(n^{1-2/k}\log(n))$ bits. We apply our method of recursive sketches and resolve the problem with $O(n^{1-2/k}\log(n)\log^{(c)}(n))$ bits.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/1542012-08-26T12:16:46-04:002012-10-16T12:26:00-04:00https://talks.cs.umd.edu/talks/154Distinguished Lecture: Efficient communication and storage vs accurate variant calls in high throughput sequencing: two sides of the same coin <a href="http://www.cs.sfu.ca/~cenk/">S. Cenk Sahinalp - Simon Fraser University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2117 Computer Science Instructional Center (CSI)</a><br>Friday, October 19, 2012, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Given two strings A and B from the DNA alphabet, the Levenshtein edit distance between A and B, $LED(A,B)$, is defined to be the minimum number of single character insertions, deletions and replacements to transform A to B (equivalently B to A). If in addition to the single character edits, one is permitted to perform segmental (block) edits in the form of (i) moving a block from any location to another, (ii) copying a block to any location, and (iii) uncopying (i.e. deleting one of the two occurrences of) a block, the resulting "block edit distance", $BED(A,B)$, captures much of our current understanding of the relation between individual genome sequences. If among two communicating parties, Alice (holding genome sequence A) and Bob (holding genome sequence B), wants to compute $BED(A,B)$ then, theoretically, the total number of bits Bob needs to send to Alice is $O^{\tilde}(BED(A,B)\cdot\log BED(A,B))$ [Cormode et al., SODA 2000]. Considering that between a typical donor genome B and a reference genome A, the number of single character differences are on the order of a few million and the number of structural (i.e., blockwise) differences are in the order of tens of thousands, it should be possible to communicate genomes by exchanging only a few million bytes! Yet, today, the most effective way of communicating genome sequence data involves physically exchanging hard disks.</p>
<p>In this talk we will try to explain the wide gap between theoretical expectations and the current reality in genome communication, as well as storage, and pose some theoretical and practical problems on the way to the Google-ization of genome search and analysis. We will also try to explore the extent of our theoretical predictions for genome sequences hold for the RNA-Seq data. Finally we will briefly go through some of the recent developments in transcriptome sequence analysis, especially in the context of disease studies.</p><br><b>Bio:</b> <p>S. Cenk Sahinalp is a Professor of Computing Science at Simon Fraser University, Canada. He received his Ph.D. in Computer Science from the University of Maryland at College Park in early 1997. Sahinalp is an NSF Career Awardee, a Canada Research Chair, a Michael Smith Foundation for Health Research Scholar and an NSERC Discovery Accelerator Awardee. His papers on genomics and bioinformatics have been highlighted by scientific journals and magazines (e.g. Genome Research, Nature Biotech, Genome Technology) and won several awards (e.g. ISMB'12 Best Student Paper, ISMB'11 HitSeq Best Paper). He was/is the conference general chair of RECOMB'11, PC chair of APBC'13, and has served as the sequence analysis area chair for ISMB and CSHL Genome Informatics Conferences. He has also co-founded the RECOMB-Seq conference series on Massively Parallel Sequencing. He is an area co-editor for BMC Bioinformatics and is on the editorial board of Bioinformatics and several other journals. He co-directs the SFU undergraduate program in Bioinformatics and the SFU Bioinformatics for Combating Infectious Diseases Research Program. His research interests include computational genomics, in particular algorithms for high throughput sequence data, network biology, RNA structure and interaction prediction and chemoinformatics algorithms.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/2">CS Department</a> ⋅ <a href="https://talks.cs.umd.edu/lists/17">CS Research Seminar</a><br>tag:talks.cs.umd.edu,2005:Talk/2402012-12-01T10:04:32-05:002012-12-01T10:04:32-05:00https://talks.cs.umd.edu/talks/240Revisiting The Monge Property<a href="http://www.cse.ust.hk/~golin/">Mordecai Golin - The Hong Kong University of Science and Technology</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Tuesday, December 4, 2012, 2:00-3:00 pm<br><br><b>Abstract:</b> <pre>We revisit the "Monge" speedup for dynamic programming and show that
not only time, but in many cases also space, can be reduced by an order
of magnitude. We further show that it's often possible to maintain the
speedup in an online setting (the original Monge speedup assumed static
input).
This is joint work with Amotz Bar-Noy, Yi Feng, Larry Larmore and Yan
Zhang</pre><br><b>Bio:</b> <pre>Dr. Golin is a Professor in the Department of Computer Science &
Engineering at HKUST. He is also Associate Vice-President for
Postgraduate Studies. After receiving his doctorate from Princeton
University in 1990, Dr. Golin worked as a researcher in the Projet
Algorithmes of the Institut National de Recherche en Informatique et en
Automatique (INRIA) in Rocquencourt, France. He has also been a visiting
researcher at the Max-Planck-Institut fur Informatik in Saarbrucken,
Germany, INRIA-Sophia in France, AT&T Labs-Research, and DIMACS. His
research interests include the design and application of algorithms,
computational geometry, information theory, and combinatorics.</pre><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2622013-02-01T11:41:26-05:002013-02-01T11:41:26-05:00https://talks.cs.umd.edu/talks/262Movement Repairman Problem<a href="http://www.cs.umd.edu/~khani/">Reza Khani - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Friday, February 1, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>In the Movement Repairman (MR) problem we are given a metric space (V, d) along with a set R of k repairmen r_1, r_2, ..., r_k with their start depots s_1, s_2, ..., s_k \in V and speeds v_1, v_2, ..., v_k > 0 respectively and a set C of m clients c_1, c_2, ..., c_m having start locations s'_1, s'_2, ..., s'_m \in V and speeds v'_1, v'_2, ..., v'_m > 0 respectively. If t is the earliest time a client c_j is collocated with any repairman (say, r_i) at a node u, we say that the client is served by r_i at u and that its latency is t. The objective in the Sum Movement Repairman (Sum-MR) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients' latencies. We give the first O(\log n)-approximation algorithm for the Sum-MR problem. In order to do so we give a natural LP formulation for this problem and bound its integrality gap. In order to be able to solve the LP in polynomial time, we relax the LP allowing the repairmen and clients to travel a little more. We next round the relaxed LP using randomization applied to each of the geometrically increasing segments of the time line. The MR problem is very general; we present additional results to show the connections of this problem to the other well studied problems. It turns out that Sum-MR is closely related to the Neighborhood TSP problems which are studied well in Euclidean Space. We give a constant-factor approximation algorithm for Sum-MR in Euclidean Space. An alternate objective in the MR problem is to minimize the maximum latency seen by the clients. We study the Max Movement Repairman (Max-MR) problem in which the goal is to minimize the time of serving the latest client. We also give a constant-factor approximation algorithm for the Max-MR problem in the case where all repairmen have the same speed.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2632013-02-01T11:43:16-05:002013-02-01T11:43:16-05:00https://talks.cs.umd.edu/talks/263To send or not to send: Reducing the cost of data transmission <a href="http://www.cs.umd.edu/~koyelm/">Koyel Mukherjee - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Friday, February 22, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <h2> </h2>
<p>Frequently, ISPs charge for Internet use not based on peak bandwidth usage, but according to a percentile (often the 95th percentile) cost model. In other words, the time slots with the top 5 percent (in the case of 95th percentile) of data transmission volume do not affect the cost of transmission. Instead, we are charged based on the volume of traffic sent in the 95th percentile slot. In such an environment, by allowing a short delay in transmission of some data, we may be able to reduce our cost considerably.</p>
<p>We provide an optimal solution to the offline version of this problem (in which the job arrivals are known), for any delay $D>0$. The algorithm works for any choice of percentile.</p>
<p>We also show that there is no efficient deterministic online algorithm for this problem. However, for a slightly different problem, where the maximum amount of data transmitted is used for cost accounting, we provide an online algorithm with a competitive ratio of $\frac{2D+1}{D+1}$. Furthermore, we prove that no online algorithm can achieve a competitive ratio $ $\frac{2D+1}{D + F(D)}$ where $F(D) = \sum^{D+1}_{i=1}{\frac{i}{D+i}}$ for any $D>0$ in an adversarial setting.</p>
<p>We also provide a heuristic that can be used in an online setting where the network traffic has a strong correlation over consecutive accounting $ based on the solution to the offline percentile problem. Experimental results are used to illustrate the performance of the algorithms proposed in this work.</p>
<p>oint work with: Leana Golubchik, Samir Khuller and Yuan Yao.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2642013-02-01T11:44:44-05:002013-02-26T14:29:31-05:00https://talks.cs.umd.edu/talks/264New Approximation Results for Resource Replication Problems <a href="http://www.cs.umd.edu/~kasarpa/Welcome.html">Kanthi Kiran Sarpatwar - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, March 1, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We consider several variants of a basic resource replication problem in this paper, and propose new approximation results for them. These problems are of fundamental interest in the areas of P2P net- works, sensor networks and ad hoc networks, where optimal placement of replicas is the main bottleneck on performance. We observe that the threshold graph technique, which has been applied to several k-center type problems, yields simple and efficient approximation algorithms for resource replication problems. Our results range from positive (efficient, small constant factor, approximation algorithms) to extremely negative (impossibility of existence of any algorithm with non-trivial approximation guarantee, i.e., with positive approximation ratio) for different versions of the problem.</p>
<p>This is joint work with Samir Khuller and Barna Saha.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2652013-02-01T11:47:39-05:002013-02-27T16:51:45-05:00https://talks.cs.umd.edu/talks/265The Degree of Segregation in Social Networks <a href="http://users.eecs.northwestern.edu/~nickle/">Nicole Immorlica - Microsoft Research</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, March 15, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>In 1969, economist Thomas Schelling introduced a landmark model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority. Simple simulations of Schelling's model suggest that this local behavior can cause global segregation effects. In this talk, we provide a rigorous analysis of Schelling's model on ring networks. Our results show that, in contrast to prior interpretations, the outcome is nearly integrated: the average size of an ethnically-homogenous region is independent of the size of the society and only polynomial in the size of a neighborhood.</p>
<p>Joint work with Christina Brandt, Gautam Kamath, and Robert D. Kleinberg</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2662013-02-01T11:49:17-05:002013-02-27T16:55:27-05:00https://talks.cs.umd.edu/talks/266The Combinatorics of Hidden Diversity<a href="http://www2.research.att.com/~dsj/">David Johnson - AT&T Labs - Research</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3117 Computer Science Instructional Center (CSI)</a><br>Friday, April 12, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Suppose we are given n buckets with varying integral sizes, and wish to fill some fraction alpha of them will balls, with a bucket of size k being filled as soon as it receives k balls. Our goal is to minimize the number of balls used.</p>
<p>If we know the sizes of the buckets, this is a trivial problem: Just identify the (alpha)n smallest buckets, and fill them. But what if we do not know the sizes of the buckets in advance, and after each ball placement only find out whether the bucket is now full or not?</p>
<p>This problem models a cryptographic question. Suppose an adversary wishes to prevent a multiparty protocol from succeeding. Typically with such protocols, the adversary need only corrupt half (or a third) of the parties to attain its goal. But suppose each party is protected by a sequence of some number of cryptographic walls, each of which requires a certain amount of computation to break through. If parties have differing numbers of walls, and the adversary does not know how many walls a given party has until it breaks through the last one, we get our balls-and-buckets problem.</p>
<p>This cryptographic connection is formalized in a paper I've written with Juan Garay, Aggelos Kiayis, and Moti Yung. Here I will concentrate on the combinatorial side, giving algorithms for the adversary (bucket filler) in the presence various levels of partial information about the sizes, and near-matching lower bounds on what is possible, both for deterministic and randomized algorithms. I also address the question of how a system-designer can best spend his security dollars (in wall building) in the hidden diversity setting.</p><br><b>Bio:</b> <p>David Johnson is Head of the Algorithms and Optimization Department at AT&T Labs-Research in Florham Park, NJ, and has been a researcher at the Labs (in its many incarnations) since 1973, when he received his PhD from MIT. He is perhaps best known as the co-author of COMPUTERS AND INTRACTABILITY: A GUIDE TO THE THEORY OF NP-COMPLETENESS, for which he and his co-author M. R. Garey won the INFORMS Lanchester Prize. His research interests include approximation algorithms for combinatorial problems, a subject on which he had several of the first key papers, starting with his PhD thesis on the infamous "bin packing" problem. In recent years he has become a leader in the experimental analysis of algorithms, and has been the creator and lead organizer for the series of DIMACS Implementation Challenges, covering topics from Network Flows to the Traveling Salesman Problem. He also founded the ACM-SIAM Symposium on Discrete Algorithms (SODA), and served as its Steering Committee Chair for its first 23 years. He is an ACM Fellow, a SIAM Fellow, an AT&T Fellow, and the winner of the 2010 Knuth Prize for outstanding contributions to the foundations of computer science.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2672013-02-01T11:50:29-05:002013-04-08T15:56:30-04:00https://talks.cs.umd.edu/talks/267 Porting the Computer Science Toolbox to Game Theory and Economics<a href="http://theory.stanford.edu/~tim/">Tim Roughgarden - Stanford University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, May 3, 2013, 11:00 am-12:00 pm<br><br><b>Abstract:</b> <p>Theoretical computer science has brought new ideas and<br> techniques to game and economic theory. A primary signature of the<br> computer science approach is {em approximation} --- the idea of<br> building credibility for a proposed solution by proving that its<br> performance is always within a small factor of an ideal (and typically<br> unimplementable) solution. We explain two of our recent contributions<br> in this area, one motivated by networks and one by auctions.<br> <br> We first discuss the "price of anarchy": how well does decentralized<br> (or "selfish") behavior approximates centralized optimization? This<br> concept has been analyzed in many applications, including network<br> routing, resource allocation, network formation, health care, and even<br> models of basketball. We highlight a new theory of robust price of<br> anarchy bounds, which apply even to systems that are not in<br> equilibrium.<br> <br> Second, we consider auction design: for example, what selling<br> procedure should be used to maximize the revenue of a seller? On the<br> analysis side, we highlight a new framework that explicitly connects<br> average-case (i.e., Bayesian) analysis, the dominant paradigm in<br> economics, with the worst-case analysis approach common in computer<br> science. On the design side, we provide a distribution-independent<br> auction that performs, for a wide class of input distributions, almost<br> as well as the distribution-specific optimal auction.</p><br><b>Bio:</b> <p>Tim Roughgarden received his Ph.D. from Cornell University in<br> 2002 and joined the Stanford CS department in 2004, where he is<br> currently an associate professor. His research interests are in<br> theoretical computer science, especially its interfaces with game<br> theory and networks. He wrote the book "Selfish Routing and the Price<br> of Anarchy" (MIT Press, 2005) and co-edited the book "Algorithmic Game<br> Theory", with Nisan, Tardos, and Vazirani (Cambridge, 2007). His<br> significant awards include the 2002 ACM Doctoral Dissertation Award<br> (Honorable Mention), the 2003 Tucker Prize, a 2007 PECASE Award, the<br> 2008 Shapley Lectureship of the Game Theory Society, the 2009 ACM<br> Grace Murray Hopper Award, and the 2012 EATCS-ACM-SIGACT Godel Prize.</p>
<div class="yj6qo ajU">
<div id=":24t" class="ajR"><img class="ajT" src="https://mail.google.com/mail/u/0/images/cleardot.gif" alt=""></div>
</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2832013-02-13T13:19:02-05:002013-02-13T13:19:02-05:00https://talks.cs.umd.edu/talks/283Approximations in Bayesian optimal multi-dimensional mechanism design <a href="http://pages.cs.wisc.edu/~dmalec/">David Malec - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, February 15, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We will consider the classical problem of Bayesian (revenue-)optimal mechanism design. Here, a seller with a set of items wants to design a protocol to sell them to a set of potential buyers, who have various preferences among the items. The seller wants to maximize expected revenue given distributional information on how the buyers value each item. If the seller had only one item, a seminal result of Myerson (1981) exactly characterizes the optimal mechanism for this setting. Unfortunately, this optimal mechanism can be complicated and impractical; furthermore, the characterization fails to generalize to settings where there are multiple items, and buyers have distinct values for different items. We instead consider a class of mechanisms called sequential posted-pricings for selling items. As we shall see, these mechanisms are approximately optimal, and are simple, practical, and extremely robust to collusion among buyers. Furthermore, their nice properties allow us to extend our approximations to unit-demand multi-item settings, where buyers have different values for different items but want to receive at most one item. One aspect of multi-item mechanism design we give special attention to is the benefit of randomness. While Myerson's characterization shows that deterministic mechanisms can achieve optimal revenue in single-item settings, this is not true in multi-item ones. In fact, when buyers' values for different items may exhibit arbitrary correlation, Briest et al. (2010) demonstrated an unbounded gap between optimal randomized and optimal deterministic mechanisms, even with just four items and a single buyer. We shall see, however, that with independent values the benefit of randomness is bounded by a constant.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2842013-02-13T13:25:11-05:002013-05-06T21:26:18-04:00https://talks.cs.umd.edu/talks/284Reconstructing Latent Similarities in a Multiplex Social Network <a href="research.microsoft.com/en-us/people/slivkins/">ALex Slivkins - Microsoft Research Silicon Valley Mountain View</a><br><br>Friday, May 10, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>It is commonly assumed that individuals tend to be more similar to their friends than to strangers. Thus, we can view an observed social network as a noisy signal about the latent underlying "social space": the way in which individuals are (dis)similar. This naturally raises the inverse question: given a social network, how accurately can we reconstruct the social space?</p>
<p>We begin to address this problem formally. We assume that each category (e.g., geography, profession, hobbies) is characterized by a latent metric capturing (dis)similarities in this category, and gives rise to a separate social network: a random graph parameterized by this metric. The algorithm only observes the unlabeled union of these graphs, and reconstructs each metric with provably low distortion.</p>
<p>Joint work with Ittai Abraham (MSR-SV), Shiri Chechik (MSR-SV) and David Kempe (USC). Appeared in SODA 2013.</p><br><b>Bio:</b> <p>Alex Slivkins is a researcher at Microsoft Research Silicon Valley since 2007. He joined MSR-SV after a one-year postdoc at Brown University, where he was working with Eli Upfal. He received his Ph.D. in Computer Science from Cornell University, advised by Jon Kleinberg, after completing undergraduate studies at Caltech. His research interests lie in the design and analysis of algorithms, for domains such as machine learning, algorithmic economics, and social and technological networks. He has authored over 25 papers in top computer science conferences in several areas: theory&algorithms (FOCS,STOC,SODA,PODC), machine learning (COLT,ICML,NIPS), algorithmic economics (ACM-EC), and networking (SIGCOMM, INFOCOM). His work was recognized by ACM EC 2010 best paper award, and ACM PODC 2005 best student paper award.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2932013-02-22T12:10:32-05:002013-04-23T18:05:14-04:00https://talks.cs.umd.edu/talks/293The breakthrough on k-median by Li and SvenssonThomas Pensyl and Khoa Trinh - University of Maryland<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, April 26, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <pre>We will survey the recent breakthrough approximation algorithm
for k-median due to Shi Li and Ola Svensson
(<a href="http://arxiv.org/pdf/1211.0243v1.pdf">http://arxiv.org/pdf/1211.0243v1.pdf</a>). This is a sophisticated paper with
many technicalities, and we will only be able to survey the main ideas.
</pre><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2972013-02-27T17:23:31-05:002013-02-27T17:23:31-05:00https://talks.cs.umd.edu/talks/297New Connections between Fixed-Parameter Algorithms and Approximation Algorithms <a href="http://www.cs.umd.edu/~rchitnis/">Rajesh Chitnis - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Friday, March 8, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Traditionally fixed-parameter algorithms (FPT) and approximation algorithms have been considered as different approaches for dealing with NP-hard problem. The area of fixed-parameter approximation algorithms tries to tackle problems which are intractable to both these techniques. In this talk we will start with the formal definitions of fixed-parameter approximation algorithms and give a brief survey of known positive and negative results. Then (under standard conjectures in computational complexity) we show the first fixed-parameter inapproximability results for Clique and Set Cover, which are two of the most famous fixed-parameter intractable problems. On the positive side we obtain polynomial time f(OPT)-approximation algorithms for a number of W[1]-hard problems such as Minimum Edge Cover, Directed Steiner Forest, Directed Steiner Network, etc. Finally we give a natural problem which is W[1]-hard, does not have a constant factor approximation in polynomial time but admits a constant factor FPT-approximation.</p>
<p>This is joint work with MohammadTaghi Hajiaghayi and Guy Kortsarz.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/2982013-02-27T17:24:40-05:002013-03-21T23:56:01-04:00https://talks.cs.umd.edu/talks/298Improvements on Offline and Online Node-Weighted Steiner Connectivity Problems<a href="http://www.cs.umd.edu/~vliaghat/">Vahid Liaghat - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Friday, March 29, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Consider a graph G=(V,E) with a weight value w(v) associated with each vertex v. A demand is a pair of vertices (s,t). A subgraph H satisfies the demand if s and t are connected in H. In the (offline) node-weighted Steiner forest problem, given a set of demands the goal is to find the minimum-weight subgraph H which satisfies all demands. In the online variant, the demands arrive one by one and we need to satisfy each demand immediately; without knowing the future demands.<br> <br>In the offline variant, we give the first non-trivial approximation algorithm for the prize-collecting variant of the problem. In the prize-collecting variant, a penalty is associated with each demand. If the subgraph does not satisfy a demand, we need to pay the penalty of the demand. Our algorithm has a logarithmic approximation ratio which is tight up to a constant factor. Indeed our algorithm simplifies and generalizes the previous results for the prize-collecting node-weighted Steiner tree problem.<br> <br>In the online variant of the Steiner forest problem, we give a randomized O(log^3(n))-competitive algorithm. The competitive ratio is tight to a logarithmic factor. This result generalizes the recent result of Naor et al. which is an O(log^3(n))-competitive algorithm for the Steiner tree problem, thus answering one of their open problems.<br> When restricted to planar graphs (and more generally graphs excluding a fixed minor) we give a deterministic primal-dual algorithm with a logarithmic competitive ratio which is tight to a constant factor.<br><br>Joint works with MohammadTaghi Hajiaghayi, Debmalya Panigrahi, and MohammadHossein Bateni</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/3282013-04-15T15:08:45-04:002013-04-15T15:08:45-04:00https://talks.cs.umd.edu/talks/328Risk in Routing Games<a href="http://faculty.cse.tamu.edu/nikolova/">Evdokia Nikolova - Department of Computer Science and Engineering, Texas A&M University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, April 19, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span>Network routing games are instrumental in understanding</span><br><span>traffic patterns and improving congestion in networks. They have a</span><br><span>direct application in transportation and telecommunication networks</span><br><span>and extend to many other applications such as task planning, etc.</span><br><span>Theoretically, network games were one of the central examples in the</span><br><span>development of algorithmic game theory.</span><br><br><span>In these games, multiple users need to route between di fferent</span><br><span>source-destination pairs and links are congestible, namely, each link</span><br><span>delay is a non-decreasing function of the flow on the link. Many of</span><br><span>the fundamental game theoretic questions are now well understood for</span><br><span>these games, for example, does equilibrium exist, is it unique, can it</span><br><span>be computed e fficiently, does</span><br><span>it have a compact representation; the same questions can be asked of</span><br><span>the socially optimal solution that minimizes the total user delay.</span><br><br><span>So far, most research has focused on the classical models in which the</span><br><span>link delays are deterministic. In contrast, real world applications</span><br><span>contain a lot of uncertainty, which may stem from exogenous factors</span><br><span>such as weather, time of day, weekday versus weekend, etc. or</span><br><span>endogenous factors such as the network tra ffic. Furthermore, many</span><br><span>users are risk-averse in the presence of uncertainty, so that they do</span><br><span>not simply want to minimize expected delays and instead may need to</span><br><span>add a bu ffer to ensure a guaranteed arrival time to a destination.</span><br><br><span>I present my recent work on a new stochastic network game model with</span><br><span>risk-averse users. Risk-aversion poses a computational challenge and</span><br><span>it often fundamentally alters the mathematical structure of the game</span><br><span>compared to its deterministic counterpart, requiring new tools for</span><br><span>analysis. The talk will discuss best response and equilibrium</span><br><span>analysis, as well as equilibrium efficiency (price of anarchy) and a</span><br><span>new concept, the price of risk.</span><br><br><span>One relevant paper is here:</span><br><span><a href="http://faculty.cse.tamu.edu/nikolova/papers/Stochastic-selfish-routing-full.pdf">http://faculty.cse.tamu.edu/<span class="il">nikolova</span>/papers/Stochastic-selfish-routing-full.pdf</a></span><br><span>A short summary of the paper is here:</span><br><span><a href="http://www.sigecom.org/exchanges/volume_11/1/NIKOLOVA.pdf">http://www.sigecom.org/exchanges/volume_11/1/<span class="il">NIKOLOVA</span>.pdf</a></span></p><br><b>Bio:</b> <p>Evdokia Nikolova is an Assistant Professor at the Computer Science & Engineering Department at Texas A&M University. Previously she was a postdoctoral associate in the Computer Science and Artificial Intelligence Laboratory at MIT. She graduated with a BA in Applied Mathematics with Economics from Harvard University, MS in Mathematics from Cambridge University (U.K.) and Ph.D. in Computer Science from MIT. She is interested in risk analysis from an algorithmic perspective arising in stochastic optimization, networks, economics and complex systems. She has worked on applications to transportation and is also interested in energy and other domains where her work may apply.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/3412013-04-25T16:29:45-04:002013-05-13T00:20:11-04:00https://talks.cs.umd.edu/talks/341Network Diffusion & Node-Weighted Steiner Trees<a href="http://www.math.uwaterloo.ca/~jochen/">Jochen Koenemann - Associate Professor, University of Waterloo </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Monday, May 13, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>The first part of this talk focuses on a network diffusion model that was recently introduced by Goldberg & Liu (SODA'13). Goldberg & Liu's model adapts the earlier linear threshold model of Kempe, Kleinberg & Tardos (KDD'03) in an effort to capture aspects of technology adaptation processes in networks. We present new, improved, yet simple algorithms for the so called Influence Maximization problem in this setting.</p>
<p>A key component of our algorithm is a Langrangean multiplier preserving (LMP) algorithm for the Prize-collecting Node-weighted Steiner Tree problem (PC-NWST). This problem had been studied in prior work by Moss and Rabani (STOC'01 & SICOMP'07) who presented a primal-dual O(log |V|) approximate and LMP algorithm, and showed that this is best possible unless NP=P.</p>
<p>We demonstrate that Moss & Rabani's algorithm for PC-NWST is seriously flawed. We then present a new, fundamentally different primal-dual method achieving the same performance guarantee. Our algorithm introduces several novel features to the primal-dual method that may be of independent interest.</p>
<p>Joint work with Laura Sanita and Sina Sadeghian</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/3762013-07-18T10:57:42-04:002013-07-18T10:57:42-04:00https://talks.cs.umd.edu/talks/376Revisiting the Ranking Algorithm for Greedy Randomized Matching on Arbitrary Graphs<a href="http://i.cs.hku.hk/~hubert/">Hubert Chan - Department of Computer,The University of Hong Kong</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, August 2, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <pre>Motivated by online advertisement and exchange settings, greedy
randomized algorithms for the maximum matching problem have been
studied, in which the algorithm makes (random) decisions that are
essentially oblivious to the input graph. Any greedy algorithm can
achieve performance ratio 0.5, which is the expected number of matched
nodes to the number of nodes in a maximum matching.
Since Aronson, Dyer, Frieze and Suen proved that the Modified
Randomized Greedy (MRG) algorithm achieves performance ratio 0.5000025
on arbitrary graphs in the mid-nineties, no further attempts in the
literature have been made to improve this theoretical ratio for
arbitrary graphs until two papers were published in FOCS 2012.
In this talk, we revisit the Ranking algorithm using the LP framework.
Special care is given to analyze the structural properties of the
Ranking algorithm in order to derive the LP constraints, of which one
known as the boundary constraint requires totally new analysis and is
crucial to the success of our LP. We use continuous LP relaxation to
analyze the limiting behavior as the finite LP grows. Of particular
interest are new duality and complementary slackness characterizations
that can handle the monotone and the boundary constraints in
continuous LP. We believe our work achieves the currently best
theoretical performance ratio of 0.523 on arbitrary graphs.</pre><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/3842013-08-19T19:36:07-04:002013-08-19T19:36:07-04:00https://talks.cs.umd.edu/talks/384The Power of Localization for Active and Passive Learning of Linear Separators <a href="http://www.cc.gatech.edu/~ninamf/">Maria Florina Balcan - School of Computer Science at Georgia Institute of Technology</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Tuesday, September 17, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We analyze active learning algorithms, which only receive the classifications of examples when they ask for them, and traditional passive (PAC) learning algorithms, which receive classifications for all training examples, under log-concave and nearly log-concave distributions. By using an aggressive localization argument, we prove that active learning provides an exponential improvement over passive learning when learning homogeneous linear separators in these settings. Building on this, we then provide a computationally efficient algorithm with optimal sample complexity for passive learning in such settings. This provides the first bound for a polynomial-time algorithm that is tight for an interesting infinite class of hypothesis functions under a general class of data-distributions, and also characterizes the distribution-specific sample complexity for each distribution in the class. We also illustrate the power of localization for efficiently learning linear separators in two challenging noise models (malicious noise and agnostic setting) where we provide efficient algorithms with significantly better noise tolerance than previously known.</p><br><b>Bio:</b> <p>Maria Florina Balcan is an assistant professor in the School of Computer Science at Georgia Institute of Technology. Her main research interests are machine learning, computational aspects in economics and game theory, and algorithms. She is a recipient of the Carnegie Mellon University SCS Distinguished Dissertation Award , an NSF CAREER Award, a Microsoft Faculty Research Fellowship, and several paper awards at COLT. She is currently a board member of the International Machine Learning Society and a Program Committee co-chair for COLT 2014.</p>
<p> </p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/3882013-08-24T22:26:32-04:002013-08-24T22:27:07-04:00https://talks.cs.umd.edu/talks/388Clustering under Perturbation Resilience<a href="http://www.cc.gatech.edu/~yliang39/">Yingyu Liang - School of Computer Science at Georgia Institute of Technology</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, September 20, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Recently, Bilu and Linial formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor O(\sqrt{n})) perturbations, and subsequently Awasthi et al. considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations.</p>
<p>In this talk, for center-based objectives, we present an algorithm that can optimally cluster instances resilient to (1+\sqrt{2})-factor perturbations, solving an open problem of Awasthi et al. For k-median, a center-based objective of special interest, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small fraction of the points after perturbation. We give the first bounds known for k-median under this more realistic and more general assumption. We also provide positive results for min-sum clustering which is a generally much harder objective than center-based objectives. Our algorithms are based on new linkage criteria that may be of independent interest.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/3892013-08-24T22:32:08-04:002013-08-24T22:32:08-04:00https://talks.cs.umd.edu/talks/389List H-Coloring a Graph by Removing Few Vertices <a href="http://www.cs.umd.edu/~rchitnis/">Rajesh Chitnis - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, September 27, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) that is a subset of V(H) for each vertex v of G, and an integer k. The task is to decide whether there exists a subset W of V(G) of size at most k such that there is a homomorphism from G W to H respecting the lists. We show that DL-Hom(H), parameterized by k and |H|, is fixed-parameter tractable for any (P6, C6)-free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom(H) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder, Hell and Huang (1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT.</p>
<p>This is joint work with Laszlo Egri and Daniel Marx.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/4322013-09-24T23:17:23-04:002013-09-24T23:17:23-04:00https://talks.cs.umd.edu/talks/432Algorithmic Game Theory of eBay's Buyer-Selling matching<a href="http://labs.ebay.com/people/kamal-jain/">Kamal Jain - Director of Research, eBay</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, October 4, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>At the broadest level, eBay is an intermediary, who is in the business of matching a buyer and a seller so that they can complete a mutually beneficial transaction. There are two important strategic choices eBay makes. First, how and whom does eBay charge a fee for its services. Two, how does eBay rank the possible product choices for a buyer.</p>
<p><br> In this presentation, we see eBay as a part of the intermediation industry, e.g., Google is in the same business of intermediation where they match buyer-seller (i.e., searcher-advertiser as known in their world). We compare some of the popular intermediation business-models in the industry. We then ask if the intermediary could choose any business model, which would be a profit maximizing business model. We also try to propose some algorithms to implement these business models.</p>
<p><br> Credit: This is a joint work with Chris Wilkens of Berkeley. The data analysis work is jointly done with Di Wang of Berkeley.</p><br><b>Bio:</b> <p>Dr. Kamal Jain is a scientist interested in the interface of technology and business innovation. He earned his doctorate from Georgia Tech in 2000 in areas consisting of computer science, mathematics, and operation research. He is well known in both academic community and technology industry. He has published 75+ research papers in top notch conferences and journals. One of his papers inspired a book on iterative methods in algorithms. He has also published 100+ patents, a third of which have already been granted. He enjoys mentoring. He has mentored dozens of PhD students, most of whom are now at top universities and companies.</p>
<p>Kamal, together with his wife and daughter, is a Seattle area resident since 2000. He spent 11+ years with Microsoft before he moved to eBay in 2011. At Microsoft he was involved in strategic research, such as search loyalty program and music business models. His timely research helped Microsoft to develop an alternate strategy than buying Yahoo entirely, thereby saving a fortune. His research work also inspired Microsoft's research center in Boston area. At eBay he tries to develop new insights on commerce from foundational perspective.</p>
<p>Kamal is also an Affiliated Professor of Computer Science at the University of Washington and a Charter Member of TIE at its Seattle chapter.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/4552013-10-07T10:38:27-04:002013-10-07T10:38:27-04:00https://talks.cs.umd.edu/talks/455Economics of Sponsored Content in Mobile Data Networks under Uncertain Demand <a href="http://ect.bell-labs.com/who/dmandrews/">Matthew Andrews - Bell Labs</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, October 11, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>The explosion of demand for mobile data services in recent years has meant that many service providers are looking for novel pricing strategies that will allow them to recover the investment required to meet that demand. This development has generated a number of research challenges including:</p>
<p>· Which pricing mechanisms will lead to more efficient use of networks?</p>
<p>· How should contractual relationships between service providers/content providers/end users be defined?</p>
<p>· How can network measurements be used to optimize pricing plans?</p>
<p>· How can we implement nontraditional pricing plans at scale?</p>
<p>In this presentation we shall begin with a survey of recent work in this area including a description of the types of mechanism that service providers are considering. We shall then focus on the specific case of “sponsored content” where the service provider puts in place a system that allows content providers to cover the cost of end-user bandwidth. We shall develop a model for the resulting interactions when the underlying user demand is uncertain and then show that contracts can be designed that are win-win-win for the service provider, the content provider and the end user.</p>
<p>This is joint work with Ulas Ozen, Marty Reiman and Qiong Wang.</p><br><b>Bio:</b> <p>Matthew Andrews is Head of the Industrial Mathematics and Operations Research Department in the Enabling Computing Technologies domain at Bell Labs, the research arm of Alcatel-Lucent. His research interests include wireless resource allocation, packet scheduling and approximation algorithms. Some of his recent work includes algorithms for joint scheduling and congestion control in ad-hoc networks and complexity theoretic results on the hardness of network design.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/4782013-10-21T14:05:32-04:002013-10-21T14:08:45-04:00https://talks.cs.umd.edu/talks/478Scheduling a Cascade with Opposing Influences Anshul Sawant - University of Maryland<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, October 25, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Adoption or rejection of ideas, products, and technologies in a society is often governed by simultaneous propagation of positive and negative influences. Consider a planner trying to introduce an idea in different parts of a society at different times. How should the planner design a schedule considering this fact that positive reaction to the idea in early areas has a positive impact on probability of success in later areas, whereas a flopped reaction has exactly the opposite impact? We generalize a well-known economic model to study this situation, where the reaction of each area is determined by its initial preference and the reaction of early areas. We model the society by a graph where each node represents an a group of people with same preferences. We consider a full propagation setting where news and influences propagate between every two areas. We generalize previous works by studying the problem when people in different areas have differing behaviors.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/4882013-10-28T10:58:09-04:002013-10-28T10:58:09-04:00https://talks.cs.umd.edu/talks/488Statistically-secure ORAM with $\tilde{O}(\log^2 n)$ Overhead<a href="http://www.cs.princeton.edu/~zhenming/">Zhenming Liu - Post-doctoral research associate, Princeton University </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, November 1, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We demonstrate a simple, statistically secure, ORAM with computational overhead $\tilde{O}(\log^2 n)$; previous ORAM protocols achieve only computational security (under computational assumptions) or require $\tilde{\Omega}(\log^3 n)$ overheard. An additional benefit of our ORAM is its conceptual simplicity, which makes it easy to implement in both software and (commercially available) hardware.</p>
<p><br> Our construction is based on recent ORAM constructions due to Shi, Chan, Stefanov, and Li (Asiacrypt 2011) and Stefanov and Shi (ArXiv 2012), but with some crucial modifications in the algorithm that simplifies the ORAM and enable our analysis. A central component in our analysis is reducing the analysis of our algorithm to a ``supermarket<em> problem; of independent interest (and of importance to our analysis,)</em> we provide an upper bound on the rate of ``upset<em> customers in the</em> ``supermarket<em> problem.</em></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/4952013-11-03T17:05:38-05:002013-11-03T17:05:38-05:00https://talks.cs.umd.edu/talks/495Partial Resampling in the Moser-Tardos Framework David Harris - University of Maryland<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, November 8, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>The resampling algorithm of Moser & Tardos is a powerful approach to develop constructive versions of the Lovasz Local Lemma. We develop a partial resampling approach motivated by this methodology: when a bad event holds, we resample an appropriately-random subset of the variables that define this event, rather than the entire set as in Moser & Tardos. This is particularly useful when the bad-events are sums of random variables; in that case, we can (in effect) drastically lower the inter-dependency of the bad-events. This leads to several improved algorithmic applications in scheduling, graph transversals, packet routing etc. As a motivating example, we discuss a packet-routing algorithm of Leighton, Maggs, Rao; we show that this approach leads to much better approximation guarantees for scheduling.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5002013-11-12T21:28:32-05:002013-11-12T21:28:32-05:00https://talks.cs.umd.edu/talks/500Concise Bid Optimization Strategies with Multiple Budget Constraints <a href="http://mhbateni.com/academic/">Mohammad Hossein Bateni - Google Research at New York</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, November 15, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>A major challenge faced by the marketers attempting to optimize their advertising campaigns is to deal with budget constraints. The problem is even harder in the face of multidimensional budget constraints, particularly in the presence of many decision variables involved, and an interplay among the variables and decisions. Concise bidding strategies help advertisers deal with this challenge by introducing fewer variables to act on.</p>
<p>In this paper, we study the problem of finding optimal concise bidding strategies for advertising campaigns with multiple budget constraints. Given bid landscapes---i.e., predicted value (e.g., number of clicks) and cost per click for any bid---that are typically provided by ad-serving systems, we optimize the value given budget constraints. In particular, we consider bidding strategies that consists of no more than $k$ different bids for all keywords. For constant $k$, we provide a PTAS to optimize the profit, whereas for arbitrary $k$ we show how constant-factor approximation can be obtained via a combination of solution enumeration and dependent LP-rounding techniques.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5072013-11-19T15:39:20-05:002013-11-19T15:39:20-05:00https://talks.cs.umd.edu/talks/507Pretty good, though still Exponential, algorithms for 3-SAT and Min Ind Set<a href="http://www.cs.umd.edu/~gasarch/">William Gasarch - University of Maryladn</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, November 22, 2013, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>SAT can clearly be solved in roughly 2^n steps. We would like to solve it in poly time, though this is unlikely. Even so, can we improve upon 2^n? YES! In this talk we show a sequence of algorithms that do BETTER than 2^n time for 3-SAT. (example: (1.5)^n).</p>
<p>We will (time permitting) also look at Maximum Ind Set. Here too we will get better, though still exponential time for this problem. Of interest- in some cases it is not the ALGORITHM we change but the ANALYSIS.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5322014-01-13T13:22:27-05:002014-01-13T13:22:27-05:00https://talks.cs.umd.edu/talks/532Defining sets in combinatorics with emphasis in graph theory(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5402014-01-21T16:56:39-05:002014-01-21T16:56:39-05:00https://talks.cs.umd.edu/talks/540Selling Tomorrow's Bargains Today<a href="https://www.cs.umd.edu/people/mabolhas">Melika Abolhassani - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, January 31, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Consider a family who decides, on Monday, that they would like to go on vacation the following weekend. Reserving a hotel involves an interesting dilemma: should they book a room now, or wait until late in the week? Booking now assures them a place to stay that is affordable. On the other hand, many hotels offer last minute deals, which could save the potential vacationers money if they decide to wait. Taking full advantage of last minute offers generally requires too much risk and too much effort on the part of an individual buyer, but such offers quickly become appealing if these costs can be split across many customers. Thus a company can make a profit in this way. In this work we consider what the reasonable deals for a company is and in what ways it can make a profit.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5442014-01-27T18:21:34-05:002014-01-27T18:21:34-05:00https://talks.cs.umd.edu/talks/544On Correcting Inputs - Inverse Optimization with a Margin <a href="http://www.cs.umd.edu/~manishp/">Manish Purohit - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, February 28, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Algorithm designers typically assume that the input data is correct, and then proceed to find ``optimal<em> or ``sub-optimal</em> solutions using this input data. However this assumption of correct data does not always hold in practice, especially in the context of online learning systems where the objective is to learn appropriate weights given some training samples. Such scenarios necessitate the study of inverse optimization problems where one is given an input instance as well as a desired output and the task is adjust the input data so that the given output is indeed optimal. In this talk, we consider inverse optimization with a margin, i.e., the given output should be better than all other feasible outputs by a desired margin. We consider such inverse optimization problems for maximum weight matroid basis, matroid intersection, perfect matchings, minimum cost maximum flows, and shortest paths.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5482014-01-30T11:07:08-05:002014-01-30T11:07:08-05:00https://talks.cs.umd.edu/talks/548Revenue Monotone Mechanisms for Online Advertising <a href="http://www.cs.umd.edu/~khani/">Reza Khani - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, February 21, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Online advertising is an essential part of the Internet and the main source of revenue for many web-centric firms such as search engines, social networks, and online publishers. A key component of online advertising is the auction mechanism which selects and prices the set of winning ads.</p>
<p>This work is inspired by one of the biggest practical drawbacks of the widely popular Vickrey-Clarke-Groves (VCG) mechanism, which is the unique incentive-compatible mechanism that maximizes social welfare. It is known that VCG lacks a desired property of revenue monotonicity - a natural notion which states that the revenue of a mechanism shouldn't go down as the number of bidders increase or if the bidders increase their bids. Most firms which depend on online advertising revenue have a large sales team to attract more bidders on their inventory as the general belief is that more bidders will increase competition, and hence revenue. However, the lack of revenue monotonicity of VCG conflicts with this general belief and can be strategically confusing for the firm's business.</p>
<p>In this work, we seek incentive-compatible mechanisms that are revenue-monotone. This natural property comes at the expense of social welfare - one can show that it is not possible to get incentive-compatibility, revenue-monotonicity, and optimal social welfare simultaneously. In light of this, we introduce the notion of Price of Revenue Monotonicity (\porm) to capture the loss in social welfare of a revenue-monotone mechanism.</p>
<p>We further study revenue-monotonicity for two important online advertising scenarios. First one is the text vs image ad auction where in an ad slot, one can either show a single image ad or a few text ads. Second one is the video-pod auction where we have a video advertising slot of $k$ seconds which can be filled with multiple video ads. For the image-text auction, we give a mechanism that satisfy both RM and IC and achieve \porm{} of $\sum_{i=1}^k \frac{1}{i} \approx \ln k$. We also show that the \porm{} of our mechanism is the best possible by proving a matching lower bound of $\sum_{i=1}^k \frac{1}{i}$ on the \porm{} of any deterministic mechanism under some mild assumptions. For the video-pod auction, we give a mechanism that achieves a \porm{} of $(\lfloor \log k \rfloor + 1) \cdot (2 + \ln k)$.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5702014-02-04T13:47:18-05:002014-02-04T13:47:18-05:00https://talks.cs.umd.edu/talks/570Beating 2^n: Faster Exact Algorithms for Some Graph Problems <a href="http://www.cs.umd.edu/~rchitnis/">Rajesh Chitnis - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, February 7, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Most NP-complete graph problems can be solved by brute force in 2^{n} time, where n is the size of the input graph. In this talk, we will describe faster exact algorithms, of the form (2-\epsilon)^n for some constant \epsilon>0, for various problems such as (Directed) Multiway Cut and (Directed) Subset Feedback Vertex Set. </p>
<div> </div>
<div>Joint work with Fedor Fomin, Daniel Lokshtanov, Pranabendu Misra, M.S. Ramanujan and Saket Saurabh. Appeared in IPEC '13.</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/5802014-02-12T23:13:16-05:002014-02-12T23:13:16-05:00https://talks.cs.umd.edu/talks/580Online Stochastic Reordering Buffer Scheduling <a href="http://www.cs.umd.edu/~hossein/Research.html">Hossein Esfandiari - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, February 14, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>In this work we consider online buffer scheduling problem in which an online stream of n items (jobs) with different colors (types) has to be processed by a machine with a buffer of size k. This problem has been considerd in two models, block-operation model and standard model. In the block-operation model, the machine chooses an active color and can--in each step--process all items of that color in the buffer. In the standard model, the machine process items whose color matches the active color until no items in the buffer have this color anymore (note that the buffer is refilled in each step).</p>
<p>Motivated by practical applications in real-world, we assume we have prior stochastic information about the input. In particular we know the colors of items are drawn i.i.d. from a possibly unknown distribution or more generally the items are coming in the random order setting in which an adversary determines the color of each item in advance, but then the items arrive in a random order in the input stream. To the best of our knowledge, this is the first work which considers the reordering buffer problem in stochastic settings. Our main result is demonstrating constant competitive online algorithms for both the standard model and the block operation model in the unknown distribution setting and more generally in the random order setting. This provides a major improvement of the competitiveness of algorithms in stochastic settings; the best competitive ratio in the adversarial setting is \Theta(log (log (k)) for both the standard and the block-operation models by Avigdor-elgrabli and Rabani and Adamaszek et al.</p>
<p>Along the way, we also show that in the random order setting designing competitive algorithms with the same competitive ratios (up to constant factors) in both the block operation model and the standard model are equivalent.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6012014-02-25T13:33:00-05:002014-02-25T13:33:00-05:00https://talks.cs.umd.edu/talks/601Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems <a href="anthi%20Kiran%20Sarpatwa">Kanthi Kiran Sarpatwar - University of Maryland </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, March 7, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>In the well studied "Connected Dominating Set" (CDS) problem, we are given an unweighted graph and the goal is to find a minimum size dominating set, with an additional restriction that it induces a connected subgraph in the given graph. Guha and Khuller (Algorithmica, 1998) obtained the first O(log n) approximation algorithm for this problem. In this talk, we will discuss new approximation algorithms for a partial and budgeted version of the CDS problem. In the partial connected dominating set problem (PCDS), the goal is to find a min size subset that induces a connected subgraph, while dominating at least a given fraction of vertices. The budgeted CDS problem (BCDS) is a dual problem, where the size of the subset is fixed and we seek to maximize the number of vertices that can be dominated. We will discuss, an O(log n) and a constant approximation algorithm for the PCDS and BCDS problems respectively. Further, we will extend our results to a more generalized framework that has the capacitated version of these problems as a special case.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6042014-02-25T21:27:16-05:002014-02-25T21:28:25-05:00https://talks.cs.umd.edu/talks/604How to Influence People with Partial Incentives<a href="http://www.cs.umd.edu/~hmahini/">Hamid Mahini - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, March 28, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We study the power of fractional allocations of resources to maximize influence in a network. This work extends in a natural way the well-studied model by Kempe, Kleinberg, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no way to apply intermediate levels of influence. This model captures some settings precisely, e.g. exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away one free product.</p>
<p>While fractional versions of problems tend to be easier to solve than integral versions, for influence maximization, we show that the two versions have essentially the same computational complexity. On the other hand, the two versions can have vastly different solutions: the added flexibility of fractional allocation can lead to significantly improved influence. Our main theoretical contribution is to show how to adapt the major positive results from the integral case to the fractional case. Specifically, Mossel and Roch (2006) used the submodularity of influence to obtain their integral results; we introduce a new notion of continuous submodularity, and use this to obtain matching fractional results. We conclude that we can achieve the same greedy (1−1/e−ε)-approximation for the fractional case as the integral case. In practice, we find that the fractional model performs substantially better than the integral model, according to simulations on real-world social network data.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6252014-03-05T10:55:17-05:002014-03-05T10:55:54-05:00https://talks.cs.umd.edu/talks/625Parallel Algorithms for Geometric Graph Problems <a href="http://onak.pl/">Krzysztof Onak - IBM TJ Watson Research Center</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, March 14, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Over the past decade a number of parallel systems such as MapReduce, Hadoop, and Dryad have become widely successful in practice. In this talk, I will present a new algorithmic framework for geometric graph problems for these kinds of systems. Our algorithms produce approximate solutions for problems such as Minimum Spanning Tree (MST) and Earth-Mover Distance (EMD). Provided the underlying set of points lies in a space of constant dimension, only a constant number of rounds is necessary, while the total amount of space and communication remains linear in the size of the data. In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem, despite drawing significant attention in recent years.</p>
<p>Our algorithmic framework has implications beyond the modern parallel systems. For example, it yields a new algorithm for approximating EMD in the plane in near-linear time. We note that while recently Sharathkumar and Agarwal (STOC 2012) have developed a near-linear time algorithm for (1+epsilon)-approximating EMD, our approach is fundamentally different and also solves the transportation cost problem, which was raised as an open question in their work.</p>
<p>Joint work with Alexandr Andoni (Microsoft), Aleksandar Nikolov (Rutgers University), and Grigory Yaroslavtsev (Brown University).</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6282014-03-06T04:09:33-05:002014-03-06T04:09:33-05:00https://talks.cs.umd.edu/talks/628Impossibility Theorems and the Universal Algebraic Toolkit <a href="http://www.cs.rutgers.edu/~szegedy/">Mario Szegedy - Rutgers University </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Wednesday, April 2, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We elucidate a close connection between the Theory of Judgment Aggregation and a relatively young but rapidly growing field of universal algebra, that was primarily developed to investigate constraint satisfaction problems. We show that theorems in the above field translate (often directly) to impossibility,classification and robustness theorems in social choice theory. We refine the classification of E. Dokow, R. Holzman of binary evaluations, give a classification theorem for the majoritarian aggregator and show how Sen's well known theorem follows from it, add new classification results to non binary evaluations, define new aggregator classes and also prove theorems about them.</p>
<p>Joint work with Yixin Xu</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6372014-03-12T11:12:28-04:002014-04-03T10:13:51-04:00https://talks.cs.umd.edu/talks/637Greedy-like algorithms and a myopic model for the non-monotone submodular maximization problem <a href="http://www.cs.toronto.edu/~bor/">Allan Borodin - University of Toronto</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1115 Computer Science Instructional Center (CSI)</a><br>Friday, April 11, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We are generally interested in the following not-well defined problem: What is a conceptually simple algorithm and what is the power and limitations of such algorithms? In particular, what is a greedy algorithm or more generally a myopic algorithm for a combinatorial optimization problem? And to be even more specific, motivated by the Buchbinder et al ``online greedy algorithm<em> for the</em> unconstrained non-monotone submodular maximization problem, what are (if any) the limitations of algorithms "of this genre" for the general unconstrained problem and for specific instances of the problem, such as Max-Di-Cut?</p>
<p>Joint work with Norman Huang</p><br><b>Bio:</b> <p>Allan Borodin received his BSC from Rutgers University in 1963, and obtained an MSC degree in 1966 from Stevens Institute of Technology while working as a Member of the Technical Staff at Bell Laboratories. He returned full time to graduate school at Cornell in 1966 and received his PhD in 1969. He came to Canada and the University of Toronto in 1969 for a year or two but forgot to leave. He has been on the faculty of the Department of Computer Science at Toronto since 1969 and served as department chair from 1980-1985. He has held visiting positions at Cornell, ETH Zurich, Universite' de Nice, Hebrew University, Weizmann University, Technion, Tel Aviv University, University of Washington and the Institute for Advanced Study. Professor Borodin is a fellow of the Royal Society of Canada and a recipient of the 2008 CRM-Fields-PIMS Prize. He was appointed a University Professor in 2011.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6562014-04-01T12:45:47-04:002014-04-01T12:45:47-04:00https://talks.cs.umd.edu/talks/656Weighted and Fractional Versions of the Target Set Selection Problem on Trees<a href="http://terpconnect.umd.edu/~raghavan/">S. Raghu Raghavan - Professor of Management Science and Operations Management , University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, April 4, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>The Target Set Selection (TSS) problem is a fundamental problem about the diffusion of influence in social networks that has been widely studied in the literature. The TSS problem has applications in many areas in economics, business, sociology and medicine including viral marketing and epidemiology. In this talk I will discuss 1) A weighted version of the TSS problem (WTSS problem). The weights in the WTSS problem model the fact the cost or effort to activate different nodes can vary. 2) A fractional version of the TSS problem. The fractional activation of a node has a natural interpretation as the payment of partial incentives to adopt a product in the viral marketing context. We call this fractional version of the TSS problem, the Least Cost Influence Problem (LCIP).</p>
<p>Both problems are NP-hard on general graphs. Motivated by the desire to develop mathematical programming approaches to solve these two problems, we focus on developing strong formulations for these problems on trees. In particular, we are interested in formulations whose linear programming relaxations are integral. Based on the observation that the influence propagation network is a directed acyclic graph, these integral formulations can be embedded into a larger exponential sized integer programming formulation for these two problems on general graphs. In the talk I will focus on simple dynamic programming algorithms for both problems, and developing integral formulations for both problems on trees. Time permitting I will describe results with a branch-and-cut approach to solve these problems on general graphs. (Joint work with Dilek Gunnec and Rui Zhang)</p><br><b>Bio:</b> <p>Dr. Raghavan is passionate about using quantitative methods (in particular optimization models) for better decision making. His research interests and activities cover a broad domain including--- auction design, data mining, economics, information systems, computational marketing, networks, optimization, and telecommunications. He has published on a wide variety of topics (including telecommunications, electronic markets, and data mining) and numerous academic outlets such as Management Science, Operations Research, Decision Support Systems, and the INFORMS Journal on Computing. He holds two patents, and has won numerous awards for his work. These include (i) the Dantzig award for the best doctoral dissertation, (ii) the INFORMS Computing Society Prize (twice); once for innovative contributions to the field of data mining, and a second time for his contributions to public sector auction design, (iii) the Glover-Klingman Prize for the best paper in the journal Networks, (v) the Management Science Strategic Innovation Prize by the European Operations Research Society, (v) 2nd Prize in the INFORMS Junior Faculty Paper Competition, (vi) Finalist for the European Operations Research Society Excellence in Practice Award, and (vii) Finalist for the Wagner Prize for Excellence in Operations Research Practice. He has edited six books titled Telecommunications Network Design and Management (Kluwer Academic Press 2003), Telecommunications Planning: Innovations in Pricing, Network Design, and Management (Springer 2006), The Next Wave in Computing, Optimization, and Decision Technologies (Springer 2005), Telecommunications Modeling, Policy, and Technology (Springer 2008), The Vehicle Routing Problem: Latest Advances and New Challenges (Springer 2008), and Tutorials in Operations Research (INFORMS 2008). He enjoys teaching decision modeling oriented courses, and is a recipient of the Legg-Mason Teaching Innovation award at the Smith School. Prior to joining the Smith School he led the Optimization Group at U S WEST Advanced Technologies.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6712014-04-14T10:54:02-04:002014-04-14T10:54:02-04:00https://talks.cs.umd.edu/talks/671Label Cover Instances with Large Girth and the Hardness of Approximating Spanners<a href="http://www.cs.jhu.edu/~mdinitz/">Michael Dinitz - Johns Hopkins University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, April 18, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We study the well-known Label Cover problem under the additional requirement that problem instances have large girth. We show that if the girth is at least k, the problem is roughly 2^{\log^{1-\epsilon} n/k} hard to approximate for all constant \epsilon > 0, which is the first non-trivial lower bound. Our main technique is subsampling the edges of 2-query PCPs, which allows us to reduce the degree of a PCP to be essentially equal to the soundness desired. This turns out to be enough to basically guarantee large girth, as well as giving an almost tight tradeoff between the degree and the soundness.</p>
<p>We use the new proof to show inapproximability for the basic k-spanner problem, which is both the simplest problem in graph spanners and one of the few for which super-logarithmic hardness was not known. Assuming NP \not\subseteq BPTIME(2^{polylog(n)}), we show (roughly) that for every k \geq 3 and every constant \epsilon > 0 it is hard to approximate the basic k-spanner problem within a factor better than 2^{(\log^{1-\epsilon} n) / k}. Time permitting, we will also show an additional hardness result for the Lowest Degree k-Spanner problem.</p>
<p>Join work with Guy Kortsarz and Ran Raz.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/6722014-04-14T11:08:54-04:002014-04-14T11:29:48-04:00https://talks.cs.umd.edu/talks/672One-Sided Matching with Limited Complementarities <a href="https://sites.google.com/site/quaerereverum9/">Rakesh Vohra - Department of Economics & Department of Electrical and Systems Engineering, University of Pennsylvania</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1115 Computer Science Instructional Center (CSI)</a><br>Friday, May 2, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, the assignment of computing resources like CPU time, memory and disk space to computing tasks and the assignment of truck loads of food to food banks. In these settings the complementarities in preferences are small compared with the size of the market. We exploit this to design mechanisms satisfying efficiency, envyfreeness and asymptotic strategy-proofness.</p>
<p>Informally, we assume that agents do not want bundles that are too large. There will be a parameter k such that the marginal utility of any item relative to a bundle of size k or larger is zero. We call such preferences k-demand preferences. Given this parameter we show how to represent probability shares over bundles as lotteries over approximately deterministic feasible integer allocations. The degree of infeasibility in these integer allocations will be controlled by the parameter k. In particular, ex-post, no good is over allocated by at most k-1 units.</p>
<p>Based on joint work with Thanh Nguyen and Ahmad Peivandi.</p><br><b>Bio:</b> <p>Professor Vohra is a leading global expert in mechanism design, an innovative area of game theory that brings together economics, engineering and computer science. His economics research in mechanism design focuses on the best ways to allocate scarce resources when the information required to make the allocation is dispersed and privately held, an increasingly common condition in present-day environments. His work has been critical to the development of game, auction and pricing theory — for example, the keyword auctions central to online search engines — and spans such areas as operations research, market systems and optimal pricing mechanisms.</p>
<p>He formerly taught at Northwestern University, where he was the John L. and Helen Kellogg Professor of Managerial Economics and Decision Sciences in the Kellogg School of Management, with additional appointments in the Department of Economics and the Department of Electrical Engineering and Computer Science. He taught from 1985 to 1998 in the Fisher College of Business at Ohio State University. He earned a Ph.D. in mathematics in 1985 from the University of Maryland, an M.Sc. in operational research in 1981 from the London School of Economics and a B.Sc. (Hon.) in mathematics in 1980 from University College London.</p>
<p>He joined Penn as part as of the Penn Integrates Knowledge program that President Amy Guttmann established in 2005 as a University-wide initiative to recruit exceptional faculty members whose research and teaching exemplify the integration of knowledge across disciplines. His appointment is shared with the Department of Electrical and Systems Engineering in the School of Engineering and Applied Science.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/7052014-05-13T14:30:16-04:002014-05-16T08:31:58-04:00https://talks.cs.umd.edu/talks/705Multiplicative Bidding <a href="http://mhbateni.com/academic/">Mohmmad Hossein Bateni - Google Research</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">2120 A.V. Williams Building (AVW)</a><br>Friday, May 16, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>In this paper, we initiate the study of the multiplicative bidding language adopted by major Internet search companies. In multiplicative bidding, the effective bid on a particular search term is the product of a base bid and bid adjustments that are dependent on features of the search term (for example, the geographic location of the user, or the platform on which the search is conducted). We consider the task faced by the advertiser when setting these bid adjustments, and establish a foundational optimization problem that captures the core difficulty of bidding under this language. We give matching algorithmic and approximation hardness results for this problem. Inspired by empirical studies of search engine price data, we then study certain restrictions of the problem, giving further algorithmic and hardness results. Our main technical contribution is an O(logn)-approximation for the case of multiplicative prices and monotone values. We then test our algorithms on real data against natural benchmarks.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/7062014-05-15T17:48:44-04:002014-05-15T17:48:44-04:00https://talks.cs.umd.edu/talks/706Analyzing Big Graphs via Sketching and Streami <a href="http://people.cs.umass.edu/~mcgregor/">Andrew McGregor - Department of Computer Science at the University of Massachusetts, Amherst </a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Friday, May 23, 2014, 11:00 am-12:00 pm<br><br><b>Abstract:</b> <p><span style="color: #222222; font-family: arial, sans-serif; font-size: 13.333333969116211px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; background-color: #ffffff; display: inline !important; float: none;">Early work on data stream algorithms focused on estimating numerical statistics such as quantiles, frequency moments, and heavy hitters given limited memory and a single pass over the input. However, there's now a growing body of work on analyzing more structured data such as graphs. In this talk, we survey research in this area with a focus on recent results on dimensionality reduction via random projections and processing dynamic graphs.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8012014-10-02T13:23:57-04:002014-10-02T13:23:57-04:00https://talks.cs.umd.edu/talks/801Elementary Properties of Geometric Objects in High Dimensions<a href="www.cs.umd.edu/~manishp">Manish Purohit - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, October 3, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will discuss some interesting properties of simple geometric objects (such as unit spheres and unit cubes) in high dimensions. Our intuition about space is formed in two and three dimensions and this can often be misleading in higher dimensions. I will derive some surprising facts about unit spheres such as - the volume decreases with increasing dimensions and tends to zero.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will primarily be covering material from Chapter 2 of the following book - <a class="external free" style="text-decoration: none; color: #3366bb; padding-right: 12px; " href="https://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/hopcroft-kannan-feb2012.pdf" rel="nofollow">https://www.cs.cmu.edu/~venkatg/teaching/CStheory-infoage/hopcroft-kannan-feb2012.pdf</a></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8122014-10-16T11:04:07-04:002014-10-16T11:04:07-04:00https://talks.cs.umd.edu/talks/812Random Graphs<a href="www.cs.umd.edu/~amitc">Amit Chavan - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, October 17, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will talk about some of the statistical properties of the G(n,p) graph model, due to Erdos and Renyi.<br>This model has two parameters: the number of vertices (n), and the edge probability (p). For each pair of vertices, u and v, p is the probability that the edge (u,v) is present, independent of all other edges.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">We will show that such a random graph has many interesting global properties. Namely:</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">(1) When p=d/n for some constant d, the number of triangles in G(n,p) is independent of n.<br>(2) The property that G(n,p) has diameter two has a sharp threshold at p = \sqrt(\dfrac{2\ln n}{n}).<br>(3) The disappearance of isolated vertices in G(n,p) has a sharp threshold at p = \dfrac{\ln n}{n}. <br>(4) When p=d/n, d > 1, there is a giant component consisting of a constant fraction of the vertices.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will be covering material from the following book: <a class="external free" style="text-decoration: none; color: #3366bb; padding-right: 12px; " href="http://www.cs.cornell.edu/jeh/book11April2014.pdf" rel="nofollow">http://www.cs.cornell.edu/jeh/book11April2014.pdf</a></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8202014-10-23T12:07:46-04:002014-10-23T12:07:46-04:00https://talks.cs.umd.edu/talks/820An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization<a href="http://www.cs.umd.edu/people/tpensyl">Thomas Pensyl</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, October 24, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables. The recent breakthrough of Li & Svensson for the classical k-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for k-median from 2.732+? to 2.611+? by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter ? from Li-Svensson's N^O(1/?^2) to N^O((1/?)log(1/?)).</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8212014-10-23T12:12:23-04:002014-10-23T12:12:23-04:00https://talks.cs.umd.edu/talks/821Parallel Algorithms for Geometric Graph Problems<a href="http://grigory.us/">Grigory Yaroslavtsev - University of Pennsylvania</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Thursday, October 30, 2014, 2:00-3:00 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will describe algorithms for geometric graph problems in the modern parallel models inspired by MapReduce. The talk will be self-contained, including a formal introduction of the modern theoretical computational models used to capture computations in massively parallel “MapReduce”-like systems. It will also include a sample of major open problems in the area.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes an approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms).</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will also show how the main ideas from the MST algorithm can be captured within a general “Solve-and-Sketch” algorithmic framework that we develop. Besides MST it also applies to the approximate Earth-Mover Distance (EMD) and the transportation cost problem. Algorithms designed in the “Solve-and-Sketch” framework have implications which go beyond parallel models. In particular, our work implies new near-linear time algorithms for EMD cost and transportation cost in the plane. Other implications include algorithms in the streaming with sorting model.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">Joint work with Alexandr Andoni, Krzysztof Onak and Aleksandar Nikolov.</p><br><b>Bio:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">Grigory Yaroslavtsev is a postdoctoral fellow at the Warren Center for Network and Data Sciences. He was previously a Postdoctoral Fellow in Mathematics at Brown University, ICERM. He received his Ph.D. in Theoretical Computer Science in 2013 from Pennsylvania State University and an M.Sc. in Applied Mathematics and Physics from the Academic University of the Russian Academy of Sciences in 2010.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">Grigory works on efficient algorithms for sparsification, summarization and testing properties of large data, including approximation, parallel and online algorithms, learning theory and property testing, communication and information complexity and private data release.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8302014-11-05T10:34:12-05:002014-11-05T10:34:12-05:00https://talks.cs.umd.edu/talks/830Non-Bayesian Learning in Sparse and Expansive Networks<a href="http://research.microsoft.com/en-us/um/people/brlucier/">Brendan Lucier - Microsost Research, New England</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, November 7, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">When information (about products, ideas, etc.) spreads through a population by word of mouth, one might hope that the population would eventually aggregate the opinions of its individual members. However, it is also possible for a majority opinion to be lost or suppressed; for example, if a very influential individual holds a minority view. In this talk we will study the outcomes of information aggregation in social networks. We will show that networks with certain realistic structural properties avoid information cascades and enable a population to effectively learn information from individual noisy signals.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">In our model, each individual in a network holds a private, independent opinion about a product or idea. Individuals declare their opinions asynchronously, can observe the declarations of their neighbors, and are free to update their declarations over time. Supposing that individuals conform with the majority report of their neighbors, we ask whether the population will eventually arrive at consensus on the majority opinion. We show that the answer depends on the network structure: there exist networks for which consensus is unlikely, or for which declarations converge on the minority opinion with positive probability. On the other hand, we show that individual opinions will be aggregated successfully with high probability in expansive bounded-degree networks.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8372014-11-12T10:41:22-05:002014-11-12T10:41:22-05:00https://talks.cs.umd.edu/talks/837The Interesting Behavior of the Source Location Problem<a href="http://crab.rutgers.edu/~guyk/">Guy Kortsarz - Rutgers University - Camden</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, November 14, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">In the Source Location problem we are given a graph G(V,E) with costs on the vertices and capacities on the edges and demand d_v for every v \in V. It is required to select a set S so that for any v \notin S the minimum cut between S and v is at least d_v. For example for capacities 1, it is required that there will be at least d_v edge disjoint paths from S to v for every v \notin v.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I will discuss the interesting behavior of this problem on undirected graphs. If all costs are equal then the problem is polynomial. If all demands are equal the problem is polynomial while if the demands are general and the costs are general the problem is Omega(log n) hard to approximate.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">I shall discuss the standard submodular cover algorithm that gives O(log n) ratio for all variants of this problem and countless others.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">In the main new version suggested by Fukunaga, there is a "free" flow p(v) for every v \in S. If d_v>p_v, then S-v has to provide additional d_v-p_v flow to v. Fukunaga gives an O(k\log k) ratio for this problem where k is the largest demand. I will describe very recent improvements and generalizations of this result (by a very recent paper of Nutov and myself).</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">We show that the problem is related to Steiner Network with vertex disjoint paths. I shall present a beautiful algorithm by Chuzhoy and Khanna for Steiner Network with disjoint paths.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8442014-11-19T16:40:04-05:002014-11-19T16:40:04-05:00https://talks.cs.umd.edu/talks/844Frequency Moments of Data StreamsBrian Brubach - University of Maryland, College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, November 21, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">Given a massive data set and limited space, what can we learn from a single pass through the data? This talk will serve as an introduction to streaming algorithms for frequency moments in big data. I will present algorithms for problems such as counting the number of distinct elements in a data stream and finding high frequency elements.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 13px;">The topics discussed in this talk are from Chapter 7.1 of the Hopcroft-Kannan book: <a class="external free" style="text-decoration: none; color: #3366bb; padding-right: 12px; " href="http://www.cs.cornell.edu/jeh/book11April2014.pdf" rel="nofollow">http://www.cs.cornell.edu/jeh/book11April2014.pdf</a></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8482014-12-02T14:55:00-05:002014-12-02T14:55:00-05:00https://talks.cs.umd.edu/talks/848Large-Scale Parallel Graph Algorithms<a href="http://www.cs.cmu.edu/~jshun/">Julian Shun - Carnegie Mellon University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, December 5, 2014, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="font-family: arial, sans-serif; font-size: 13px;">In the first part of the talk, we will discuss our recent work on developing a practical linear-work parallel algorithm for graph connectivity. Sequentially, connectivity can be done in linear work easily using breadth-first search or depth-first search. There have been many parallel algorithms for connectivity, however the simpler parallel algorithms require super-linear work, and the linear-work polylogarithmic-depth parallel algorithms are very complicated and not amenable to implementation. We address this gap by describing a simple and practical expected linear-work, polylogarithmic-depth parallel algorithm for graph connectivity. Our algorithm is based on a recent parallel algorithm for generating low-diameter graph decompositions by Miller et al., which uses parallel breadth-first searches. We experimentally compare our implementation of the algorithm against the fastest existing parallel connectivity implementations (which are not theoretically linear-work and polylogarithmic-depth) and show that our implementation is competitive for various inputs, and achieves good speedup relative to sequential algorithms. Our algorithm is the first parallel connectivity algorithm that is both theoretically and practically efficient.</span><br style="font-family: arial, sans-serif; font-size: 13px;"><br style="font-family: arial, sans-serif; font-size: 13px;"><span style="font-family: arial, sans-serif; font-size: 13px;">In the second part of the talk, we will discuss Ligra, a shared-memory graph processing system that we recently developed. The framework has two very simple routines, one for mapping over edges and one for mapping over vertices. The routines can be applied to any subset of the vertices, which makes the framework useful for many graph traversal algorithms that operate on subsets of the vertices. Based on recent ideas used in a very fast algorithm for breadth-first search (BFS), the routines automatically adapt to the density of vertex sets. We implement several algorithms in this framework, including BFS, betweenness centrality, graph radii estimation, graph connectivity, PageRank and single-source shortest paths. Our algorithms expressed using this framework are very simple and concise, and perform almost as well as highly-optimized code. Furthermore, they get good speedups on multicore machines and are sometimes significantly more efficient than previously reported results using graph frameworks on machines with many more cores.</span></p><br><b>Bio:</b> <p><span style="font-family: arial, sans-serif; font-size: 13px;">Julian Shun is currently a Ph.D. student in Computer Science at Carnegie Mellon University, and is advised by Guy Blelloch. He is interested in developing large-scale parallel algorithms for graph and text processing. He is also interested in designing techniques and tools for writing efficient parallel programs. Julian obtained his undergraduate degree in Computer Science from UC Berkeley.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8682015-01-15T11:24:54-05:002015-01-21T11:38:15-05:00https://talks.cs.umd.edu/talks/868Variable Selection is HardHoward Karloff - Yahoo Labs - New York<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Thursday, January 22, 2015, 11:00 am-12:00 pm<br><br><b>Abstract:</b> <div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">Consider the task of a machine-learning system faced with voluminous</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">data on m individuals. While there may be p=10^6 features describing</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">each individual, how can the algorithm find a small set of features</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">that "best" describes the individuals? People usually seek small</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">feature sets both because models with small feature sets are</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">understandable and because simple models usually generalize better.</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;"> </div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">We study the simple case of linear regression, in which a user has</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">an m x p matrix B and a vector y, and seeks a p-vector x *with as</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">few nonzeroes as possible* such that Bx is approximately equal to</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">y, and we call it SPARSE REGRESSION. There are numerous algorithms</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">in the statistical literature for SPARSE REGRESSION, such as Forward</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">Selection, Backward Elimination, LASSO, and Ridge Regression.</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;"> </div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">We give a general hardness proof that (subject to a complexity</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">assumption) no polynomial-time algorithm can give good performance</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">(in the worst case) for SPARSE REGRESSION, even if it is allowed</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">to include more variables than necessary, and even if it need only</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">find an x such that Bx is relatively far from y.</div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;"> </div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;" dir="ltr"> </div>
<div style="font-family: HelveticaNeue, 'Helvetica Neue', Helvetica, Arial, 'Lucida Grande', sans-serif; font-size: 16px; line-height: 24px;">This is joint work with Dean Foster and Justin Thaler of Yahoo Labs.</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/8972015-02-04T16:38:35-05:002015-02-04T16:38:35-05:00https://talks.cs.umd.edu/talks/897Foundations of Clustering<a href="http://www.cs.umd.edu/people/ngupta12">Neal Gupta - University of Maryland, College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, February 6, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">This talk will provide an introduction to the unsupervised learning problem of clustering. I will introduce k-means clustering and discuss the well-known computational limitations of optimal clustering. I will also present an impossibility result that provides some intuition into desirable properties of clustering that are feasible, for example through balanced k-means clustering. </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">The topics discussed in this talk are primarily from Chapter 8 of the Hopcroft-Kannan book: <a style="color: #3f51b5; z-index: 0; position: relative;" href="http://www.cs.cornell.edu/jeh/book11April2014.pdf">http://www.cs.cornell.edu/jeh/book11April2014.pdf</a></div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/9072015-02-12T10:01:14-05:002015-02-12T10:01:14-05:00https://talks.cs.umd.edu/talks/907Vertex Connectivity under Sampling<a href="www.cs.umd.edu/~manishp">Manish Purohit - University of Maryland, College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, February 13, 2015, 2:30-3:30 pm<br><br><b>Abstract:</b> <p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 12.6999998092651px;">Consider the following random process - Given a graph G, each edge or vertex of G is sampled with probability p. We are now interested in the following natural question - How large should p be to guarantee that sampled graph is connected? Intuitively it is clear that if the base graph G has higher (edge or vertex) connectivity, then a smaller sampling probability should suffice.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 12.6999998092651px;">In this setting, a fundamental result by Karger (STOC 94) states that for any k-edge connected graph with n nodes, independently sampling each edge with probability p = \Omega(log n / k) is sufficient to guarantee that the sampled graph has edge connectivity \Omega(kp). However, analogous results for vertex connectivity were only obtained very recently in a sequence of two papers by Censor-Hillel et al (SODA 2014, SODA 2015).</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 12.6999998092651px;">Censor-Hillel et al introduced a novel technique of analyzing the sampling process in phases (also known as layers). The key idea is to show that connected components induced by the sampled vertices grow in each layer until finally we have only one component as desired. In this talk, we describe this layering technique and prove the following theorem - For any k-vertex connected graph with n node, independently sampling each vertex with probability p = Omega(log n / \sqrt(k)) is sufficient to guarantee that the sampled graph is connected.</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 12.6999998092651px;">This talk is based on the following two papers -</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 12.6999998092651px;">1. K. Censor-Hillel, M. Ghaffari, F. Kuhn. A New Perspective on Vertex Connectivity. SODA 2014</p>
<p style="margin: 0.4em 0px 0.5em; line-height: 19.0499992370605px; font-family: sans-serif; font-size: 12.6999998092651px;">2. K. Censor-Hillel, M. Gharrafi, G. Giakkoupis, B. Haeupler, F. Kuhn. Tight Bounds on Vertex Connectivity Under Vertex Sampling. SODA 2015</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/9312015-02-25T10:38:33-05:002015-02-25T10:38:33-05:00https://talks.cs.umd.edu/talks/931Spectral Sparsification<a href="http://www.cs.umd.edu/~kabinav/">Karthik Abhinav Sankararaman</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, February 27, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">Continuing on the theme of sparsification, in this talk I will present a neat algorithm due to Spielman and Srivatsava on spectral sparsification. The aim of the talk is to introduce some notions from spectral graph theory, look at how a different perspective of graph as a physical object such as electrical network helps in realising many properties and also some interesting mathematical tools. This algorithm is from the following paper</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">"Graph Sparsification by Effective Resistances", Daniel A Spielman, Nikhil Srivatsava [STOC '08] (<a style="color: #3f51b5; z-index: 0; position: relative;" href="http://arxiv.org/pdf/0803.0929.pdf">http://arxiv.org/pdf/0803.0929.pdf</a>)</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<p> </p>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">This talk might be useful for a broader range of audience, outside theory as well. So, all are invited to attend.</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/9392015-03-02T14:40:49-05:002015-03-02T14:40:49-05:00https://talks.cs.umd.edu/talks/939Cournot CompetitionAnshul Sawant<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, March 6, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="font-family: sans-serif; font-size: 12.6999998092651px; line-height: 19.0499992370605px;">Cournot competition is a fundamental economic model that represents firms competing in a single market of a homogeneous good. Each firm tries to maximize its utility---a function of the production cost as well as market price of the product---by deciding on the amount of production. In today's dynamic and diverse economy, many firms often compete in more than one market simultaneously, i.e., each market might be shared among a subset of these firms. In this situation, a bipartite graph models the access restriction where firms are on one side, markets are on the other side, and edges demonstrate whether a firm has access to a market or not. We call this game Network Cournot Competition (NCC). In this paper, we propose algorithms for finding pure Nash equilibria of NCC games in different situations. First, we carefully design a potential function for NCC, when the price functions for markets are linear functions of the production in that market. However, for nonlinear price functions, this approach is not feasible. We model the problem as a nonlinear complementarity problem in this case, and design a polynomial-time algorithm that finds an equilibrium of the game for strongly convex cost functions and strongly monotone revenue functions. We also explore the class of price functions that ensures strong monotonicity of the revenue function, and show it consists of a broad class of functions. Moreover, we discuss the uniqueness of equilibria in both of these cases which means our algorithms find the unique equilibria of the games. Last but not least, when the cost of production in one market is independent from the cost of production in other markets for all firms, the problem can be separated into several independent classical Cournot Oligopoly problems. We give the first combinatorial algorithm for this widely studied problem.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/9832015-03-31T14:04:10-04:002015-03-31T14:04:10-04:00https://talks.cs.umd.edu/talks/983Space-efficient Local Computation AlgorithmsBrian Brubach<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, April 3, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">his talk is based on the paper "Space-efficient Local Computation Algorithms" by Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. No prior knowledge of Local Computation Algorithms is required.</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">Rubinfeld et al. proposed a new model of sublinear algorithms called local computation algorithms. In this model, a computation problem F may have more than one legal solution and each of them consists of many bits. The local computation algorithm for F should answer in an online fashion, for any index i, the ith bit of some legal solution of F . Further, all the answers given by the algorithm should be consistent with at least one solution of F.</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">In this talk, we'll see a technique which under certain conditions can be applied to construct local computation algorithms that run not only in polylogarithmic time, but also in polylogarithmic space. Moreover, these local computation algorithms are easily parallelizable and can answer all parallel queries consistently. The main technical tools are pseudorandom numbers with bounded independence and the theory of branching processes.</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/9952015-04-08T14:47:38-04:002015-04-08T14:47:38-04:00https://talks.cs.umd.edu/talks/995Models to Motifs: A Graph Structure Success Story <a href="http://www.csc.ncsu.edu/faculty/bdsullivan/">Blair Sullivan - North Carolina State University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, April 10, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="font-family: sans-serif; font-size: 12.6999998092651px; line-height: 19.0499992370605px;">We discuss recent work that begins bridging the gap between real-world network analysis and structural graph algorithms. In particular, we demonstrate that a form of structural sparsity known as bounded expansion is a deep structural property of networks that is simultaneously algorithmically useful, predicted by many mathematical models of complex networks, and observed in practice in real-world network data. We highlight results proving a dichotomy in generative network models with respect to this structure and give empirical evidence of bounded expansion in real network data. Finally, we will present the algorithmic pipeline giving efficient algorithms in bounded-expansion classes and an implementation for motif counting. This is joint work with E. Demaine, F. Reidl, P. Rossmanith, F. Sanchez Villaamil, and S. Sikdar.</span></p><br><b>Bio:</b> <p><span style="font-family: sans-serif; font-size: 12.6999998092651px; line-height: 19.0499992370605px;">Blair D. Sullivan is an Assistant Professor in the Department of Computer Science at North Carolina State University, and holds a Joint Faculty Appointment at Oak Ridge National Laboratory. Her current research focuses on enabling the application of structural graph algorithms to real-world challenges in the analysis of complex networks, including new methods for identifying and leveraging structural sparsity. Before joining NC State, Dr. Sullivan was a computational mathematician at ORNL, and a visiting researcher at the Renyi Institute in Budapest, Hungary. She received her Ph.D. in Mathematics at Princeton University as a Department of Homeland Security Graduate Fellow, and bachelor's degrees in Applied Mathematics and Computer Science at Georgia Tech. Dr. Sullivan is a Moore Investigator in Data-Driven Discovery and a 2014 National Consortium for Data Science Faculty Fellow.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/10102015-04-20T13:01:45-04:002015-04-20T13:08:32-04:00https://talks.cs.umd.edu/talks/1010Convexity, Colors, LP and PPADAhmed Abdelkader - University of Maryland, College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3120 Computer Science Instructional Center (CSI)</a><br>Friday, April 24, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">We start with an overview of fundamental convexity results in discrete geometry. This includes the theorems of Radon, Carathéodory, Helly and Tverberg. We follow by describing their duals and the colorful generalizations pioneered by Bárány [1]. Then, we present some recent works on the computational aspects of the colorful Carathéodory's theorem [2] and its application to Colorful Linear Programming (CLP) [1, 3]. In particular, the authors in [3] describe a reduction from BIMATRIX, which is PPAD-complete, to CLP, which they show is NP-complete by reusing a result in [1]. This would imply that any NP-complete problem is at least as hard as any PPAD-complete problem.</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">[1] Bárány, Imre, and Shmuel Onn. "Colourful linear programming and its relatives." <em style="font-size: 13px; font-family: Arial, sans-serif; line-height: 16px;">Mathematics of Operations Research</em> 22.3 (1997): 550-567.</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">[2] Mulzer, Wolfgang, and Yannik Stein. "Computational Aspects of the Colorful Carathéodory Theorem." <em style="font-size: 13px; font-family: Arial, sans-serif; line-height: 16px;">arXiv preprint arXiv:1412.3347</em> (2014). (accepted in SoCG 2015)</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">[3] Meunier, Frédéric, and Pauline Sarrabezolles. "Colorful linear programming, Nash equilibrium, and pivots." <em style="font-size: 13px; font-family: Arial, sans-serif; line-height: 16px;">arXiv preprint arXiv:1409.3436</em> (2014).</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/10172015-04-21T11:52:39-04:002015-05-04T16:34:17-04:00https://talks.cs.umd.edu/talks/1017Computing on Strategic Inputs<a href="http://people.csail.mit.edu/costis/">Constantinos Daskalakis - MIT</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3117 Computer Science Instructional Center (CSI)</a><br>Friday, May 8, 2015, 3:00-4:00 pm<br><br><b>Abstract:</b> <p><span style="font-family: sans-serif; font-size: 12.6999998092651px; line-height: 19.0499992370605px;">Algorithmic mechanism design centers around the following question: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? We present computationally efficient, approximation-preserving reductions from mechanism design (i.e.optimizing over rational inputs) to algorithm design (i.e. optimizing over known inputs) in general Bayesian settings. We also explore whether structural properties about optimal mechanisms can be inferred from these reductions. As an application, we present extensions of Myerson's celebrated single-item auction to multi-item settings.</span></p><br><b>Bio:</b> <p><span style="font-family: sans-serif; font-size: 12.6999998092651px; line-height: 19.0499992370605px;">Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and its interface with economics and probability. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, and the 2012 Microsoft Research Faculty Fellowship. He is also a recipient of Best Paper awards at the ACM Conference on Economics and Computation in 2006 and in 2013.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/2">CS Department</a><br>tag:talks.cs.umd.edu,2005:Talk/10202015-04-21T20:16:05-04:002015-04-21T20:16:05-04:00https://talks.cs.umd.edu/talks/1020Sketching as a Tool for Numerical Linear Algebra <a href="http://researcher.watson.ibm.com/researcher/view.php?person=us-dpwoodru">David Woodruff - IBM, Almaden</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Thursday, April 30, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: medium; line-height: 24px;">I'll highlight recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given an n x d matrix A, one first compresses A to an m x d matrix S*A, where S is a certain m x n random matrix with m much less than n. Much of the expensive computation is then performed on S*A, thereby accelerating the solution for the original problem involving A. I'll discuss recent advances in least squares as well as robust regression, including least absolute deviation and M-estimators. I'll also discuss low rank approximation, and a number of variants of these problems. </span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/11342015-09-24T08:59:43-04:002015-09-24T08:59:43-04:00https://talks.cs.umd.edu/talks/1134Cryptography in the Age of Quantum ComputersMark Zhandry<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3460 A.V. Williams Building (AVW)</a><br>Wednesday, September 30, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>It is well established that full-fledged quantum computers, when realized, will completely break many of today`s cryptosystems. This looming threat has led to the proposal of so-called "post-quantum" systems, namely those that appear resistant to quantum attacks. We argue, however, that the attacks considered in prior works model only the near future, where the attacker may be equipped with a quantum computer, but the end-users implementing the protocols are still running classical devices.<br> <br> Eventually, quantum computers will reach maturity and everyone — even the end-users — will be running quantum computers. In this event, attackers can interact with the end-users over quantum channels, opening up a new set of attacks that have not been considered before. In this talk, I will put forward new security models and new security analyses showing how to ensure security against such quantum channel attacks. In particular, these analyses allow for re-building many core cryptographic functionalities, including pseudorandom functions, encryption, digital signatures, and more, resulting in the first protocols that are safe to use in a ubiquitous quantum computing world. Along the way, we resolve several open problems in quantum query complexity, such as the Collision Problem for random functions, the Set Equality Problem, and the Oracle Interrogation Problem.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/20">Crypto Reading Group</a> ⋅ <a href="https://talks.cs.umd.edu/lists/3">MC2 Seminar</a> ⋅ <a href="https://talks.cs.umd.edu/lists/19">Security Reading Group</a><br>tag:talks.cs.umd.edu,2005:Talk/11422015-09-30T10:48:19-04:002015-09-30T10:49:46-04:00https://talks.cs.umd.edu/talks/1142Lassere HierarchyPan Xu - University of Maryland, College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, October 2, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #151515; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; line-height: 24px; background-color: #f7f7f7;">Lassere Hierarchy is an important tool for systematically reducing the size of a feasible polytope in many optimization problems. This tool has been used extensively in the last decade in a variety of approximation algorithms. In this talk, we will go over a beautiful survey written by Thomas Rothvoss on this subject(</span><a class="external free" style="box-sizing: border-box; color: #236b9b; text-decoration: none; transition: color 250ms ease-out, background-color 250ms ease-out, border-color 250ms ease-out; cursor: pointer; padding-right: 2px; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; line-height: 24px; background: #f7f7f7;" href="http://www.math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf" rel="nofollow">http://www.math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf</a><span style="color: #151515; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; line-height: 24px; background-color: #f7f7f7;">). This is a continuation of the two-part talk. In this second part, we will have a look at some of the applications(e.g. Matching and Max Cut) and the power of this tool. This talk is a good mix of convex optimization and algorithmic techniques with very little pre-requisites needed. </span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/11542015-10-07T10:36:04-04:002015-10-07T10:36:04-04:00https://talks.cs.umd.edu/talks/1154Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models<a href="www.cs.umd.edu/~hossein/">Hossein Esfandiari - University of Maryland, College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, October 9, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Motivated by Internet advertising applications, online allocation problems have been studied extensively in various adversarial and stochastic models. While the adversarial arrival models are too pessimistic, many of the stochastic (such as i.i.d or random-order) arrival models do not realistically capture uncertainty in predictions. A significant cause for such uncertainty is the presence of unpredictable traffic spikes, often due to breaking news or similar events. To address this issue, a simultaneous approximation framework has been proposed to develop algorithms that work well both in the adversarial and stochastic models; however, this framework does not enable algorithms that make good use of partially accurate forecasts when making online decisions. In this paper, we propose a robust online stochastic model that captures the nature of traffic spikes in online advertising.</div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"> </div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In our model, in addition to the stochastic input for which we have good forecasting, an unknown number of impressions arrive that are adversarially chosen. We design algorithms that combine an stochastic algorithm with an online algorithm that adaptively reacts to inaccurate predictions. We provide provable bounds for our new algorithms in this framework. We accompany our positive results with a set of hardness results showing that that our algorithms are not far from optimal in this framework. As a byproduct of our results, we also present improved online algorithms for a slight variant of the simultaneous approximation framework.</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/11892015-10-29T09:39:02-04:002015-10-29T09:39:02-04:00https://talks.cs.umd.edu/talks/1189Two Faces of Algorithm Design: Optimization and Learning<a href="www.cs.umd.edu/~manishp">Manish Purohit - University of Maryland, College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, October 30, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Traditionally, algorithm designers have been interested in optimization problems where one assumes that the provided data is sacrosanct and correct. Given a specified problem, the goal is to design an algorithm that yields a good solution to any instance of the problem. On the other hand, the rise of machine learning presents an algorithm designer with new challenges. Abstractly, a prediction problem can be described as follows - One is given a problem instance and a large number of experts (i.e. features) who present their opinions as corresponding solutions. The learning goal is to determine the "faithful" experts who consistently give good solutions. In other words, at the training step, one is required to update their belief (weight) in the experts by looking a problem instance as well as the desired solution.</div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"> </div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In this talk, I'll present some of my work on both of these aspects of algorithm design. The first part of the talk focuses on a natural optimization problem that arises in the context of job scheduling with soft precedence constraints. We formalize this scheduling problem as the Max-k-Ordering problem that naturally generalizes two of the most well studied problems on directed graphs - Max Directed Cut and Max Acyclic Subgraph. We develop a tight 2-approximation algorithm for the problem for all k by rounding the natural LP-relaxation.</div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"> </div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">The second part of the talk focuses on the structured prediction problem referred to above. We extend the online large-margin training algorithm (MIRA) developed by Crammer et al (2006) in the context of multiclass prediction to learning structured prediction models. We show that for a large class of structured prediction problems, one can formulate the online learning problem as an inverse optimization problem with a margin. Further, these inverse optimization problems can be solved efficiently using polynomial sized convex programs. </div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/12012015-11-09T18:18:37-05:002015-11-09T18:18:37-05:00https://talks.cs.umd.edu/talks/1201Online Degree-Bounded Steiner Network DesignSoheil Ehsani - University of Maryland, College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, November 13, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In this talk I am going to present our paper which is accepted in</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">SODA'16. We initiate the study of degree-bounded network design</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">problems in the online setting. The degree-bounded Steiner tree</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">problem, which asks for a subgraph with minimum degree that connects a</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">given set of vertices, is perhaps one of the most representative</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">problems in this class. The paper deals with its well-studied</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">generalization called the degree-bounded Steiner forest problem where</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">the connectivity demands are represented by vertex pairs that need to</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">be individually connected. In the classical online model, the input</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">graph is given online but the demand pairs arrive sequentially in</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">online steps. The selected subgraph starts as the empty subgraph, but</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">has to be augmented to satisfy the new connectivity constraint in each</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">online step. The goal is to be competitive against an adversary that</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">knows the input in advance. The standard techniques for solving</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">degree-bounded problems often fall in the category of iterative and</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">dependent rounding techniques. Unfortunately, these rounding methods</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">are inherently difficult to adapt to an online settings since the</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">underlying fractional solution may change dramatically in between the</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">rounding steps. Indeed, this might be the very reason that despite</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">many advances in the online network design paradigm in the past two</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">decades, the</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">natural family of degree-bounded problems has remained widely open.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In our paper, we design an intuitive greedy-like algorithm that</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">achieves a competitive ratio of O(log n) where n is the number of</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">vertices. We show that no (randomized) algorithm can achieve a</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">(multiplicative) competitive ratio o(log n); thus our result is</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">asymptotically tight. We further show strong hardness results for the</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">group Steiner tree and the edge-weighted variants of degree-bounded</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">connectivity problems. Furer and Raghavachari resolved the online</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">variant of degree-bounded Steiner forest in their paper in SODA'92.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Since then, the family of degree-bounded network design problems has</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">been extensively studied in the literature resulting in the</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">development of many interesting tools and numerous papers on the</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">topic. We hope that our approach and its dual analysis, paves the way</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">for solving the online variants of the classical problems in this</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">family of problems.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/12242015-11-30T10:59:11-05:002015-11-30T10:59:11-05:00https://talks.cs.umd.edu/talks/1224A Crash Course on Fast Interactive ProofsJustin Thaler - Yahoo! Labs<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3460 A.V. Williams Building (AVW)</a><br>Thursday, December 3, 2015, 10:00-11:00 am<br><br><b>Abstract:</b> <p>Protocols for verifiable computation enable a computationally weak verifier to offload computations to a powerful but untrusted prover, while providing the verifier with a guarantee that the prover performed the computations correctly. Asymptotically efficient protocols for verifiable computation have been known for several decades in the form of interactive proofs, PCPs, and their brethren. However, it is only very recently that these protocols have grown efficient enough for plausible use in the real world. In this talk, I will give a crash course on interactive proofs and the algorithmic techniques underlying their efficient implementation.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/20">Crypto Reading Group</a> ⋅ <a href="https://talks.cs.umd.edu/lists/3">MC2 Seminar</a><br>tag:talks.cs.umd.edu,2005:Talk/12382015-12-07T17:15:40-05:002015-12-07T17:15:40-05:00https://talks.cs.umd.edu/talks/1238Scalable Large Near-Clique Detection in Large-Scale Networks<a href="http://people.seas.harvard.edu/~babis/">Charalampos Tsourakakis - Harvard University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, December 11, 2015, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Finding large near-(bi)cliques in massive networks is a notoriously hard problem of great importance to many applications, including anomaly</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">detection and security, and community detection in social networks, and the Web graph.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">But can we exploit idiosyncrasies of real-world networks to attack</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">this NP-hard problem successfully?</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In this talk I will answer this question in the affirmative. Specifically,</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">I will present a significant advance in routines</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">with rigorous theoretical guarantees for scalable extraction</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">of large near-cliques from large-scale networks, the k-clique densest subgraph problem.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">I will present exact, approximation, and MapReduce algorithms that allow us</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">to scale our computations to large-scale networks. At the heart of our scalable</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">algorithm lies a densest subgraph sparsifier theorem.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Our approach allows us to extract large near-(bi)cliques from a diverse collection of networks with millions of edges within few seconds. Finally, I will present interesting graph mining findings such as anomaly detection in real-world networks. I will conclude my talk with some interesting open problems.</span></p><br><b>Bio:</b> <p><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Dr. Charalampos Tsourakakis is currently a CRCS Postdoctoral Fellow in the School of Engineering and Applied Sciences (SEAS) at Harvard University. He received his Ph.D. from the Algorithms, Combinatorics and Optimization (ACO) program at Carnegie Mellon University (CMU). He also holds a Master of Science from the Machine Learning Department at CMU. He did his undergraduate studies in the School of Electrical and Computer Engineering (ECE) at the National Technical University of Athens (NTUA). He is the recipient of a best paper award in IEEE Data Mining and has designed two graph mining libraries for tera-scale graphs. The former has been officially included in Windows Azure, and the latter was a research highlight of Microsoft Research. His main research interest lies in designing scalable algorithms for massive networks that recover hidden structure and solve complex data-driven problems.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13542016-03-09T21:17:48-05:002016-03-09T21:17:48-05:00https://talks.cs.umd.edu/talks/1354On Computing Maximal Independent Sets of Hypergraphs in ParallelIoana Bercea - University of Maryland College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, March 11, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p> </p>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; background-color: #ffffff;">
<div style="font-size: 12.8px;">Whether or not the problem of finding maximal independent sets (MIS) in hypergraphs is in (R)NC is one of the fundamental problems in the theory of parallel computing. Essentially, the challenge is to design (randomized) algorithms in which the number of processors used is polynomial and the (expected) runtime is polylogarithmic in the size of the input. Unlike the well-understood case of MIS in graphs, for the hypergraph problem, our knowledge is quite limited despite considerable work. It is known that the problem is in RNC when the edges of the hypergraph have constant size. For general hypergraphs with $n$ vertices and $m$ edges, the fastest previously known algorithm works in time $O(\sqrt{n})$ with $\text{poly}(m,n)$ processors. In this paper we give an EREW PRAM randomized algorithm that works in time $n^{o(1)}$ with $O(n + m \log n)$ processors on general hypergraphs satisfying $m \leq n^{o(1) \frac{\log \log n}{\log \log \log n}}$. We also give an EREW PRAM deterministic algorithm that runs in time $n^{\epsilon}$ on a graph with $m \leq n^{1/\delta}$ edges, for any constants $\delta, \epsilon$; the number of processors is polynomial in $m,n$ for a fixed choice of $\delta, \epsilon$. Our algorithms are based on a sampling idea that reduces the dimension of the hypergraph and employs the algorithm for constant dimension hypergraphs as a subroutine. This paper was presented at SPAA 2014.</div>
</div><br><b>Bio:</b> <p>Ioana Bercea is a PhD student working with Prof. Samir Khuller.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13162016-02-04T17:30:00-05:002016-02-04T17:30:00-05:00https://talks.cs.umd.edu/talks/1316Correlated Knapsack problem(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13182016-02-09T17:33:33-05:002016-02-09T17:33:33-05:00https://talks.cs.umd.edu/talks/1318On Polynomial Time algorithms for restricted Subset Sum ProblemsPaul<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, February 12, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">The Subset Sum Problem is NP-complete. Each subset sum problem specifies a finite set of integers </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">and an integer </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">t</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, and its solutions are the sets </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">T</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> contained in </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> such that the sum of the elements of </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">T</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> is </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">t</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">. Here, I describe an approach to the Subset Sum Problem that involves constructing sequences of expressions for increasingly restricted supersets of the set of solutions. Let </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">N</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> = |</span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">|, let </span><strong style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">a</strong><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> be an </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">N</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">-dimensional vector whose entries are the elements of </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, let </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">Xk</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> = {(</span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">x</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">1, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">x</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">2,…, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">xN</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">) s.t. each </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">xi</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> is in {0, 1}, the dot product of </span><strong style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">a</strong><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> and (</span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">x</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">1, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">x</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">2,…, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">xN</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">) is congruent to </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">t</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> mod 2^</span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">k</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">}, and let </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">m</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> be the least integer such that 2^</span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">m</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> is greater than the sum of the absolute values of the elements of </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">. Each of these sequences of expressions is </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">e</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">1, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">e</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">2,…, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">em</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> such that (i) for each natural number</span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">k</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> less than or equal to </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">m</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, an element of </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">Xk</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> can be returned in polynomial time given </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">ek</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> if </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">Xk</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> is nonempty, (ii) </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">e</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">1 can be constructed in polynomial time given </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> and </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">t</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, (iii) for each natural number </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">k</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> < </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">m</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">ek</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">+1 can be constructed in polynomial time given </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">ek</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">S</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, and </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">t</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, and (iv) for each natural number </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">k</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> less than or equal to </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">m</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">, </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">ek</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> is no larger than </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">e</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">1. I present forms of expressions that can be included such sequences, characteristics of </span><em style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;">Xk</em><span style="color: #222222; font-family: 'Times New Roman'; font-size: 12px;"> that can be exploited by methods for producing expressions of these forms, restrictions on the Subset Sum Problem that imply the existence of such a sequence, and Polynomial Time algorithms for Subset Sum Problems with these restrictions.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13272016-02-16T20:33:26-05:002016-02-16T20:33:26-05:00https://talks.cs.umd.edu/talks/1327Succinct Data Structures and Text Indexing<a href="http://www.csc.lsu.edu/~rahul/">Rahul Shah - Louisiana State University (LSU)</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, February 19, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In the era of big data, data sizes are ever increasing, however the </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">information content in the data is often low. Many such data sets can be </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">compressed to much under their original size. The field of succinct data </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">structure attempts to achieve two goals at one shot (1) keeping the space </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">usage of the data structure as low as the information theoretic optimum </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">space required for the underlying data storage and (2) achieving fast query </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">time (polylog in data size) as if the data structure was space unaware.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Classic example where succinct data structures have had a huge impact is the </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Suffix Trees which are used for full-text indexing. Suffix trees on text data would typically take 15 to 50 times the size of the text. Moreover, many text datasets can be compressed even further. In terms of the complexity, </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">suffix trees take O(n log n) bits of space while the raw text takes O(n log </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">s) bits, where s is the size of the alphabet. Compressed indexes based on </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">Burrows-Wheeler Transform(BWT) have made it possible to have text searching </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">data structures in less than the original text's space.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In this talk, I will cover some of our recent developments in this area, </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">where the BWT based index can be made as powerful as suffix tree for pattern </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">matching variants where suffix trees need augmenting information as well as </span><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">those variants which need different notions of suffix trees.</span></p><br><b>Bio:</b> <p> </p>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; background-color: #ffffff;"><span style="font-size: 12.8px;">Dr. Rahul Shah is a Roy Paul Daniel Distinguished Associate professor at Louisiana State </span><span style="font-size: 12.8px;">University (LSU). He did is undergraduate degree from Indian Institute of Technology, Bombay </span><span style="font-size: 12.8px;">and his Doctoral degree in computer science from Rutgers University. His main areas of interest </span><span style="font-size: 12.8px;">are data structures and algorithms. He particularly specializes in string matching and external </span><span style="font-size: 12.8px;">memory algorithms. Prior to joining LSU, he was an assistant research professor at Purdue </span><span style="font-size: 12.8px;">University. He also spent a year working as a research staff member at IBM India Research Lab. </span><span style="font-size: 12.8px;">He is currently serving as a program director in algorithmic foundations at NSF.</span><span class="HOEnZb"><span style="color: #888888;"><br></span></span></div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13372016-02-24T11:12:50-05:002016-02-24T11:14:34-05:00https://talks.cs.umd.edu/talks/1337New Streaming Methods for Heavy Hitters and Norms<a href="http://www.cs.jhu.edu/~vova/">Vladimir Braverman - Johns Hopkins University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, February 26, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">In this talk we will discuss two recent results.</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;"> </p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">(1) Given a stream $p_1, \ldots, p_m$ of items from a universe</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">$\mathcal{U}$, which, without loss of generality we identify with</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">the set of integers $\{1, 2, \ldots, n\}$, we consider the problem of returning all</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">$\ell_2$-heavy hitters, i.e., those items $j$ for which</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">$f_j \geq \eps \sqrt{F_2}$, where $f_j$ is the number of occurrences</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">of item $j$ in the stream, and $F_2 = \sum_{i \in [n]} f_i^2$.</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">data structure, which finds all such $j$ using $\Theta(\log^2 n)$ bits of space</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">(for constant $\eps > 0$). The only known lower bound is $\Omega(\log n)$ bits of space, which comes from</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">the need to specify the identities of the items found.</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">We show it is possible to achieve $O(\log n \log \log n)$ bits of space for this problem.</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">This is a joint work with Stephen R. Chestnut, Nikita Ivkin, and David P. Woodruff.</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;"> </p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">(2) If time permits, we will discuss the recent <span style="font-size: 11pt; color: #1f497d;">characterization of the streaming space complexity of every symmetric norm l (a norm on R^n invariant under sign-flips and coordinate-permutations. Specifically, we provide upper and lower bounds on the space complexity of approximating the norm of the stream, where both bounds depend on the median of l(x) when x is drawn uniformly from the l_2 unit sphere. The same quantity governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem. The family of symmetric norms contains several well-studied norms, such as all l_p norms, and indeed we provide a new explanation for the disparity in space complexity between p <=2 and p>2. In addition, we apply our general results to easily derive bounds for several norms were not studied before in the streaming model, including for example the top-k norm and the k-support norm, which was recently shown to be effective for machine learning tasks.</span></p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">This is a joint work with Stephen R. Chestnut, Robert Krauthgamer, and Lin F. Yang.</p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;"> </p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;"> </p>
<p class="MsoNormal" style="margin: 0in 0in 0.0001pt; color: #222222; font-size: 11pt; font-family: Calibri, sans-serif;">All CATS talks are found in the wiki page at: https://wiki.cs.umd.edu/theory/index.php?title=CATS</p><br><b>Bio:</b> <p><span style="font-family: Times; font-size: medium;">Vladimir Braverman is an Assistant Professor in the </span><a style="font-family: Times; font-size: medium;" href="http://www.cs.jhu.edu/">Department of Computer Science</a><span style="font-family: Times; font-size: medium;"> in the Whiting School of Engineering at the Johns Hopkins University.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13452016-03-02T09:04:07-05:002016-03-02T09:04:07-05:00https://talks.cs.umd.edu/talks/1345Survey of Local Computation Algorithms<a href="www.cs.umd.edu/~bbrubach">Brian Brubach - University of Maryland College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, March 4, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In 2011, a new model was proposed to address a key challenge in solving problems on large datasets (BIG DATA!). Instead of outputting a potentially enormous solution, what if we only need to query a small portion of the solution? Do we need to compute and store the whole solution ahead of time if we want our queries to be fast and consistent? The study of local computation algorithms (LCAs) answers questions like these. The past five years have seen many interesting developments in this area and there’s still much more to explore.</div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"> </div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">This talk will be a high level survey of local computation algorithms. Topics will include an introduction to the field, recent developments, and applications to other areas such as machine learning and mechanism design. We will conclude with some open problems and future directions.</div><br><b>Bio:</b> <p>Brian is a second year PhD student advised by Dr. Aravind Srinivasan</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13622016-03-24T10:42:11-04:002016-03-24T10:42:11-04:00https://talks.cs.umd.edu/talks/1362DATA SUMMARIZATION AT SCALE<a href="http://seas.yale.edu/faculty-research/faculty-directory/amin-karbasi">Amin Karbasi - Yale University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, March 25, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">For the last several years, we have witnessed the emergence of datasets of an unprecedented scale across different scientific disciplines. The large volume of such datasets presents new computational challenges as the diverse, feature-rich, and usually high-resolution data does not allow for effective data-intensive inference. In this regard, data summarization is a compelling (and sometimes the only) approach that aims at both exploiting the richness of large-scale data and being computationally tractable; Instead of operating on complex and large data directly, carefully constructed summaries not only enable the execution of various data analytics tasks but also improve their efficiency and scalability.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">A systematic way for data summarization is to turn the problem into selecting a subset of data elements optimizing a utility function that quantifies “representativeness” of the selected set. Often-times, these objective functions satisfy sub-modularity, an intuitive notion of diminishing returns stating that selecting any given element earlier helps more than selecting it later. Thus, many problems in data summarization require maximizing submodular set functions subject to cardinality and massive data means we have to solve these problems at scale.</span><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><br style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">In this talk, I will present our recent efforts in developing practical schemes for data summarization. In particular, I will first discuss Stochastic- Greedy, currently the fastest centralized algorithm for data summarization whose query complexity is only linear in data size. However, to truly summarize data at scale we need to opt for streaming or distributed solutions. To this end, I will then present Sieve-Streaming, the first streaming algorithm for data summarization with a constant-factor approximation guarantee. Finally, I will talk about GreeDi, the first distributed approach towards data summarization. In our extensive experiments, we demonstrate the effectiveness of our approach on several applications, including sparse Gaussian process inference and exemplar-based clustering, on tens of millions of data points using Hadoop.</span></p><br><b>Bio:</b> <p style="margin-top: 0em; margin-bottom: 0.8em; padding: 0px; line-height: 1.3; font-family: Georgia, serif; font-size: medium;">Amin Karbasi is an assistant professor in the School of Engineering and Applied Science (SEAS) at Yale University, where he leads the Inference, Information, and Decision (I.I.D.) Systems Group. Prior to that he was a post-doctoral scholar at ETH Zurich, Switzerland (2013-2014). He obtained his Ph.D. (2012) and M.Sc. (2007) in computer and communication sciences from EPFL, Switzerland and his B.Sc. (2004) in electrical engineering from the same university.</p>
<p> </p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13762016-03-29T09:33:34-04:002016-03-29T09:33:34-04:00https://talks.cs.umd.edu/talks/1376Rigorous Foundations for Privacy in Statistical DatabasesAdam Smith - Penn State University<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Monday, April 18, 2016, 3:00-4:00 pm<br><br><b>Abstract:</b> <div class="abstract-body">
<p>Consider an agency holding a large database of sensitive personal information -- medical records, census survey answers, web search records, or genetic data, for example. The agency would like to discover and publicly release global characteristics of the data (say, to inform policy or business decisions) while protecting the privacy of individuals' records. This problem is known variously as "statistical disclosure control", "privacy-preserving data mining" or "private data analysis".</p>
<p>I will begin by discussing what makes this problem difficult, and exhibit some of the nontrivial problems that plague simple attempts at anonymization and aggregation. Motivated by this, I will present differential privacy, a rigorous definition of privacy in statistical databases that has received significant attention. I'll explain some recent results on the design of differentially private algorithms, as well as the application of these ideas in contexts with no (previously) apparent connection to privacy.</p>
</div><br><b>Bio:</b> <p>Adam Smith is an associate professor in the Department of Computer Science and Engineering at Penn State. His research interests lie in data privacy and cryptography and their connections to information theory, statistical learning and quantum computing. He received his Ph.D. from MIT in 2004 and was subsequently a visiting scholar at the Weizmann Institute of Science and UCLA and a visiting professor at Boston University and Harvard. He received a 2009 Presidential Early Career Award for Scientists and Engineers (PECASE) and the 2016 Theory of Cryptography Test of Time Award (with Dwork, McSherry and Nissim).</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/20">Crypto Reading Group</a><br>tag:talks.cs.umd.edu,2005:Talk/13882016-04-08T11:20:04-04:002016-04-08T11:22:50-04:00https://talks.cs.umd.edu/talks/1388An Algorithm for Identifying Optimal Spreaders in a Random Walk Model of Network CommunicationFern Hunt - NIST<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, April 8, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><span style="font-size: 12.8px; font-stretch: normal;">In a model <span>of</span> network communication based on a random walk in an undirected graph, what subset <span>of</span> nodes (<span>of</span> some fixed size), enable the fastest spread <span>of</span> information? The dynamics <span>of</span> spread is described by a process dual to the movement from informed to uninformed nodes. In this setting, an optimal set A minimizes the sum <span>of</span> the expected first hitting times F(A), <span>of</span> random walks that start at nodes outside the set. </span></div>
<div style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;"><br style="font-size: 12.8px; font-stretch: normal;"><span style="font-size: 12.8px; font-stretch: normal;">In this talk, the problem is reformulated so that the search for solutions to the optimization problem is restricted to a class <span>of</span> optimal and "near" optimal subsets <span>of</span> the graph. We introduce a submodular, nondecreasing rank function rho, that permits some comparison between the solution obtained by the classical greedy algorithm and one obtained by our methods. The supermodularity and non-increasing properties <span>of</span> F are used to show that the ratio <span>of</span> the rank <span>of</span> our solution is at least (1-(1/e)) times the rank <span>of</span> the optimal set and in the case our approximation has a higher rank than the greedy solution this constant can be improved.</span></div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/13982016-04-14T16:03:25-04:002016-04-14T16:03:25-04:00https://talks.cs.umd.edu/talks/1398Dynamic (1+\epsilon)-Approximate Matchings: A Density Sensitive Approach(Reading this paper)Saba Ahmadi - University of Maryland College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, April 15, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <div><span style="font-size: 12.8px;">Approximate matchings in fully dynamic graphs have been intensively studied in recent years. In this paper authors present a simple deterministic algorithm whose performance depends on the density of the graph. They maintain fully dynamic (1+\epsilon)-approximate MCM with worst case update time O(\alpha.\epsilon^(-2) ) for graphs with arboricity bounded by \alpha. </span><span style="font-size: 12.8px;">For the family of bounded arboricity graphs (which includes forests, planar graphs and graphs excluding a fixed minor), in the regime \epsilon = O(1) update time reduces to a constant. </span><span style="font-size: 12.8px; font-family: arial, helvetica, sans-serif;">This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve an O(log n) worst case bound, where n stands for the number of vertices in the graph.</span></div>
<p> </p>
<div style="color: #888888; font-family: arial, sans-serif; font-size: 12.8px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; background-color: #ffffff;"> </div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/14072016-04-19T21:22:20-04:002016-04-19T21:22:20-04:00https://talks.cs.umd.edu/talks/1407Approximating the ATSP on topologically restricted graphsAhmed Abdelkader - University of Maryland College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, April 22, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <div><span style="font-size: 12.8px;">We review recent work on ATSP starting with the O(log n / log log n)-approximation by Asadpour et al. [1], which was the first asymptotic improvement in almost 30 years. The key ingredient is the notion of thin trees, which they obtain by post-processing a solution to the Held-Karp relaxation. We proceed to describe how this notion was further applied to get better approximations for graphs of bounded genus by Oveis Gharan and Saberi [2] and Erickson and Sidiropoulos [3]. Finally, we discuss a recent preprint by Marx, Salmasi and Sidiropoulos [4], which combines thin trees with a dynamic program to handle the larger class of nearly-embeddable graphs.</span></div>
<div><span style="font-size: 12.8px;"> </span></div>
<div>
<div style="font-size: 12.8px;">[1] <span style="font-size: 13px; font-family: Arial, sans-serif;">Asadpour, Arash, Michel X. Goemans, Aleksander M</span>?<span style="font-size: 13px; font-family: Arial, sans-serif;">dry, Shayan Oveis Gharan, and Amin Saberi. "An O (log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem." In </span><em style="font-size: 13px; font-family: Arial, sans-serif;">SODA</em><span style="font-size: 13px; font-family: Arial, sans-serif;">, vol. 10, pp. 379-389. 2010.</span></div>
<div style="font-size: 12.8px;"> </div>
<div style="font-size: 12.8px;">[2] <span style="font-size: 13px; font-family: Arial, sans-serif;">Gharan, Shayan Oveis, and Amin Saberi. "The asymmetric traveling salesman problem on graphs with bounded genus." In </span><em style="font-size: 13px; font-family: Arial, sans-serif;">Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms</em><span style="font-size: 13px; font-family: Arial, sans-serif;">, pp. 967-975. SIAM, 2011.</span></div>
<div style="font-size: 12.8px;"> </div>
<div style="font-size: 12.8px;">[3] <span style="font-size: 13px; font-family: Arial, sans-serif;">Erickson, Jeff, and Anastasios Sidiropoulos. "A near-optimal approximation algorithm for Asymmetric TSP on embedded graphs." In </span><em style="font-size: 13px; font-family: Arial, sans-serif;">Proceedings of the thirtieth annual symposium on Computational geometry</em><span style="font-size: 13px; font-family: Arial, sans-serif;">, p. 130. ACM, 2014.</span></div>
<div style="font-size: 12.8px;"> </div>
<div style="font-size: 12.8px;">[4] Marx, Dániel and Ario Salmasi, <span style="font-family: Arial, sans-serif; font-size: 13px;">Anastasios Sidiropoulos. "</span>Constant-factor approximations for asymmetric TSP on nearly-embeddable graphs." CoRR, abs/1601.01372, 2016.</div>
</div>
<p> </p>
<div style="color: #888888; font-family: arial, sans-serif; font-size: 12.8px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 1; word-spacing: 0px; background-color: #ffffff;"> </div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/14172016-04-27T09:56:51-04:002016-04-27T09:56:51-04:00https://talks.cs.umd.edu/talks/1417Paper Presentation: An Improved Distributed Algorithm for Maximal Independent SetSheng Yang - University of Maryland College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CHM">2107 Chemistry Building (CHM)</a><br>Friday, April 29, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><br class="Apple-interchange-newline"><span style="color: #222222; font-family: arial, sans-serif; font-size: 12.8px;">We present the resent work on Distributed Algorithm for Maximal Independent Set. Based on classical Luby's algorithm for MIS which runs in rounds, they gave bounds on number of rounds for each node, and in turn improved global complexity.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/14182016-04-27T10:05:03-04:002016-05-04T13:02:09-04:00https://talks.cs.umd.edu/talks/1418Survey: Randomized Dependent Rounding of Linear Programs<a href="http://www.cs.umd.edu/~kabinav">Karthik A Sankararaman - University of Maryland College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4424 A.V. Williams Building (AVW)</a><br>Friday, May 6, 2016, 2:00-3:00 pm<br><br><b>Abstract:</b> <p><span style="font-size: small;">In this talk, we survey some of the techniques for doing dependent randomized rounding of LPs. The goal of such dependent randomized rounding is to get </span>concentration<span style="font-size: small;"> of some linear function of the variables around its </span>mean,<span style="font-size: small;"> while maintaining the marginals as much as possible.</span></p>
<p><span style="font-size: small;"><span style="color: #222222; font-family: arial, sans-serif; line-height: 19.2px;">We first start with the GKPS algorithm[1] for Bipartite graphs. We then briefly describe the Maximum-Entropy Sampling technique used in the context of Spanning Trees(This was explained in full detail by Ahmed couple of talks ago)[2]. We finally describe the generalization of the above two techniques, given by Chekrui et al.[3]</span> </span></p>
<p><span style="font-size: small;">[1] http://www.cs.umd.edu/~srin/PS/2006/depround-jou.ps</span></p>
<p><span style="font-size: small;">[2] http://homes.cs.washington.edu/~shayan/atsp.pdf</span></p>
<p><span style="font-size: small;">[3] Dependent Randomized Rounding for Matroid Polytopes (http://arxiv.org/abs/0909.4348)</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15552016-09-21T10:52:30-04:002016-09-21T10:52:30-04:00https://talks.cs.umd.edu/talks/1555TBA(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15972016-11-03T11:03:14-04:002016-11-03T11:03:14-04:00https://talks.cs.umd.edu/talks/1597TBA(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15532016-09-21T10:51:07-04:002016-11-06T17:15:41-05:00https://talks.cs.umd.edu/talks/1553Leximin Allocations in the Real World (Paper Presentation)Hadi Yami - University of Maryland<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, November 11, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p> </p>
<div class="uyb8Gf" style="color: #212121; font-family: sans-serif; font-size: 13px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; background-color: #ffffff;">
<div>
<div class="F3hlO">
<div class="gmail_msg" dir="ltr" style="unicode-bidi: isolate;">
<div class="gmail_default gmail_msg" style="font-family: tahoma, sans-serif;"><span class="gmail_msg" style="font-family: arial, sans-serif;">Authors: </span><span class="gmail_msg" style="font-family: arial, sans-serif;">David Kurokawa, Ariel D. Procaccia, Nisarg Shah</span></div>
<div class="gmail_default gmail_msg" style="font-family: tahoma, sans-serif;"><span class="gmail_msg" style="font-family: arial, sans-serif;"> </span></div>
<div class="gmail_default gmail_msg" style="font-family: tahoma, sans-serif;"><span class="gmail_msg" style="font-family: arial, sans-serif;">Abstract: </span><span class="gmail_msg" style="font-family: arial, sans-serif;">As part of a collaboration with a major California school district, we study the problem of fairly allocating unused classrooms in public schools to charter schools. Our approach revolves around the randomized leximin mechanism. We extend previous work to the classroom allocation setting, showing that the leximin mechanism is proportional, envy-free, efficient, and group strategyproof. We also prove that the leximin mechanism provides a (worst-case) 4-approximation to the maximum number of classrooms that can possibly be allocated. Our experiments, which are based on real data, show that a nontrivial implementation of the leximin mechanism scales gracefully in terms of running time (even though the problem is intractable in theory), and performs extremely well with respect to a number of efficiency objectives. We take great pains to establish the practicability of our approach, and discuss issues related to its deployment.</span></div>
</div>
</div>
</div>
</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15522016-09-21T10:50:34-04:002016-10-21T10:06:41-04:00https://talks.cs.umd.edu/talks/1552Bandits and agents: How to incentivize exploration?<a href="https://www.microsoft.com/en-us/research/people/slivkins/">Alex Slivkins - Microsoft Research</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, October 28, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;"> Individual decision-makers consume information revealed by the previous decision-makers, and produce information that may help in future decisions. This phenomenon is common in a wide range of scenarios in the Internet economy, as well as elsewhere, such as medical decisions. Each decision-maker would individually prefer to "exploit": select an action with the highest expected reward given her current information. At the same time, each decision-maker would prefer previous decision makes to "explore", producing information about the rewards of various actions. A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance the exploration and exploitation so as to maximize social welfare.<u class="gmail_msg"></u><u class="gmail_msg"></u></span></p>
<p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;"><u class="gmail_msg"></u> <u class="gmail_msg"></u></span></p>
<p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;">We formulate this problem as a multi-arm bandit problem under incentive-compatibility constraints induced by agents' Bayesian priors. We design a Bayesian incentive-compatible bandit algorithm for the social planner with asymptotically optimal regret. Moreover, we provide a black-box reduction from an arbitrary multi-arm bandit algorithm to an incentive-compatible one, with only a constant multiplicative increase in regret. This reduction works for a very general bandit setting that incorporate contexts and arbitrary partial feedback. Another extension allows for multiple interdependent decision-makers in each round of the bandit problem.<u class="gmail_msg"></u><u class="gmail_msg"></u></span></p>
<p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;"><u class="gmail_msg"></u> <u class="gmail_msg"></u></span></p>
<p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;">Joint work with Yishay Mansour (Tel Aviv University and MSR Israel), Vasilis Syrgkanis (MSR-NE) and Steven Wu (Penn).<u class="gmail_msg"></u><u class="gmail_msg"></u></span></p>
<p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;"><u class="gmail_msg"></u> <u class="gmail_msg"></u></span></p>
<p class="MsoNormal gmail_msg" style="margin: 0px 0in; font-size: 12pt; font-family: 'Times New Roman', serif; color: #212121;"><span class="gmail_msg" style="font-size: 11pt; font-family: Calibri, sans-serif;"><u class="gmail_msg"></u> </span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15512016-09-21T10:49:46-04:002016-09-21T10:49:46-04:00https://talks.cs.umd.edu/talks/1551Approximate Degree, Sign-Rank, and the Method of Dual Polynomials<a href="http://people.seas.harvard.edu/~jthaler/">Justin Thaler - Georgetown University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, October 21, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p style="box-sizing: border-box; margin: 0px 0px 10px; line-height: 1.5; color: #151515; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; background-color: #f7f7f7;">The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. Approximate degree has wide-ranging applications in theoretical computer science, from computational learning theory to communication complexity, circuit complexity, and oracle separations. Despite its importance, our understanding of approximate degree remains limited, with few general results known.</p>
<p style="box-sizing: border-box; margin: 0px 0px 10px; line-height: 1.5; color: #151515; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; background-color: #f7f7f7;">The focus of this talk will be on a relatively new method for proving lower bounds on approximate degree: specifying emph{dual polynomials}, which are dual solutions to a certain linear program capturing the approximate degree of any function. I will describe how the method of dual polynomials has recently enabled progress on a variety of open problems, especially in communication complexity and oracle separations.</p>
<p style="box-sizing: border-box; margin: 0px 0px 10px; line-height: 1.5; color: #151515; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; background-color: #f7f7f7;">Joint work with Mark Bun, Adam Bouland, Lijie Chen, Dhiraj Holden, and Prashant Nalini Vasudevan</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15462016-09-21T10:41:13-04:002016-09-21T10:41:13-04:00https://talks.cs.umd.edu/talks/1546Streaming Symmetric Norms via Measure Concentration<a href="http://pha.jhu.edu/~lyang/">Lin F. Yang - Johns Hopkins University</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, September 23, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>We characterize the streaming space complexity of every symmetric norm l (a norm on R^n invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of l. Specifically, we provide matching upper and lower bounds (up to polylog factors) on the space complexity of approximating the norm of the stream, where both bounds depend on the median and maximum of l(x) when x is drawn uniformly from the l_2 unit sphere. The same quantity governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem. The family of symmetric norms contains several well-studied norms, such as all lp norms, and indeed we provide a new explanation for the disparity in space complexity between p <= 2 and p>2. In addition, we apply our general results to easily derive bounds for several norms were not studied before in the streaming model, including for example the top-k norm and the k-support norm, which was recently shown to be effective for machine learning tasks.</p>
<p>Joint work with: Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15472016-09-21T10:44:18-04:002016-09-27T16:37:48-04:00https://talks.cs.umd.edu/talks/1547Low Complexity Convex Approximation<a href="https://www.cs.umd.edu/users/mount/">Dave Mount - University of Maryland</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, September 30, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">The problem we will discuss is how to approximate a convex body in d-dimensional space as a polytope having a small combinatorial complexity (that is, having a small number of vertices, edges, and faces). It has been known for decades that in dimension d it is possible to eps-approximate any convex body of unit diameter using O(1/eps^{d/2}) vertices. Here, it is assumed that d is a constant. Unfortunately, the number of facets could be much larger, roughly the square of this. It has been a longstanding open problem whether there exists an approximating polytope such that the number of faces of all dimensions matches the bound on the number of vertices. </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">In this talk, I will demonstrate a construction where the number of faces of all dimensions is O(1/eps^{d/2}) (up to polylog factors). Along the way, I'll introduce a a few cool geometric concepts, in particular, Macbeath regions and the witness-collector method.</div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">
<div style=" overflow: auto; max-width: calc(1154px);">This is joint work with Sunil Arya and Guilherme da Fonseca (two UMD alums), and is based on a paper I presented recently at SoCG 2016. </div>
<p> </p>
</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15482016-09-21T10:45:25-04:002016-09-21T10:48:50-04:00https://talks.cs.umd.edu/talks/1548Computing the Stationary DistributionMichael Cohen - Massachusetts Institute of Technology<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">4172 A.V. Williams Building (AVW)</a><br>Thursday, October 6, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>Given an explicit description of a Markov chain, we present a new algorithm to (approximately) compute its stationary distribution. The traditional approaches to this problem involve either solving general systems of linear equations--taking n^{omega} time--or in some way simulating the Markov chain itself--giving a linear dependence on the mixing time of the Markov chain. In contrast, our new approach is an iterative method with a polylogarithmic dependence on mixing time, and is inspired by spectral graph theory methods from undirected graphs. Our methods can also be used for other random walk problems, such as Personalized Page Rank and commute times.</p>
<p>Joint work with Jonathan Kelner, John Peebles, Richard Peng, Anup Rao, Aaron Sidford, and Adrian Vladu.</p>
<p>Work presented at FOCS 2016</p><br><b>Bio:</b> <p> </p>
<section id="content" class="mw-body container-fluid 0" style="box-sizing: border-box; display: block; margin-right: auto; margin-left: auto; padding-left: 15px; padding-right: 15px; width: 1559.62px; color: #151515; font-family: Lato, Helvetica, Arial, sans-serif; font-size: 16px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 300; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; ">
<div id="bodyContent" style="box-sizing: border-box;">
<div id="innerbodycontent">
<div>
<div id="mw-content-text" dir="ltr" lang="en">
<p>Michael Cohen is a graduate student in algorithms, advised by Jonathan Kelner and Alexander Madry. He is particularly interested in the use of techniques from linear algebra, convex optimization, and spectral graph theory in theoretical computer science.</p>
</div>
</div>
</div>
<div class="visualClear" style="box-sizing: border-box; clear: both;"> </div>
</div>
</section><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/15502016-09-21T10:47:50-04:002016-10-11T11:26:30-04:00https://talks.cs.umd.edu/talks/1550Language Edit Distance, (min,+)-Matrix Multiplication & Beyond<a href="https://barnasaha.net/">Barna Saha - University of Massachusetts Amherst</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Thursday, October 13, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>The language edit distance is a significant generalization of two basic problems in computer science: parsing and string edit distance computation. Given any context free grammar, it computes the minimum number of insertions, deletions and substitutions required to convert a given input string into a valid member of the language. In 1972, Aho and Peterson gave a dynamic programming algorithm that solves this problem in time cubic in the string length. Despite its vast number of applications, in forty years there has been no improvement over this running time.</p>
<p>Computing (min,+)-product of two n by n matrices in truly subcubic time is an outstanding open question, as it is equivalent to the famous All-Pairs-Shortest-Paths problem. Even when matrices have entries bounded in [1,n], obtaining a truly subcubic (min,+)-product algorithm will be a major breakthrough in computer science.</p>
<p>In this presentation, I will explore the connection between these two problems which led us to develop the first truly subcubic algorithms for the following problems: (1) language edit distance, (2) RNA-folding-a basic computational biology problem and a special case of language edit distance computation, (3) stochastic grammar parsing—fundamental to natural language processing, and (4) (min,+)-product of integer matrices with entries bounded in n(3-ω-c) where c >0 is any constant and, ω is the exponent of the fast matrix multiplication, widely believed to be 2.</p>
<p>Time permitting, we will also discuss developing highly efficient linear time approximation algorithms for language edit distance for important subclasses of context free grammars.</p><br><b>Bio:</b> <p style="box-sizing: border-box; margin: 0px 0px 10px; line-height: 1.5;">Barna Saha received her Ph.D. from the University of Maryland College Park, and then spent a couple of years at the AT&T Shannon Labs as a senior researcher before joining UMass Amherst in 2014. Her research interests are in theoretical computer science specifically in algorithm design and analysis, and large scale data analytics. She is the recipient of Google Faculty Award (2016), Yahoo ACE Award (2015), Simons-Berkeley Research Fellowship (2015), NSF CRII Award (2015), Dean's Fellowship from UMD (2011), and the best paper award and finalists for best papers at VLDB 2009 and ICDE 2012 respectively.</p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/2">CS Department</a><br>tag:talks.cs.umd.edu,2005:Talk/14712016-08-04T13:50:50-04:002016-09-26T15:20:58-04:00https://talks.cs.umd.edu/talks/1471The emergent structure of simple behaviors in complex networks<a href="http://www.immorlica.com">Nicole Immorlica - Microsoft Research</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2117 Computer Science Instructional Center (CSI)</a><br>Friday, October 7, 2016, 11:00 am-12:00 pm<br><br><b>Abstract:</b> <p></p>
<p></p>
<p class="MsoNormal"><span>Many games of social significance are played in a networked context. In these settings, agents often exhibit simple behaviors, shaped by local preferences and social norms. The interplay of these behaviors and the underlying network give rise to emergent structures with global impact. In this talk, we explore the impact of networked behavior on social capital, segregation, and learning.<br> <br> First we study the emergence of social capital in dynamic, anonymous social networks such as online communities. We find that despite the lack of punitive strategies, (partial) cooperation is sustainable at an intuitive and simple equilibrium as cooperation allows an individual to interact with an increasing number of other cooperators, resulting in the formation of valuable social capital.<br> <br> Next we examine the emergent structure of segregation in geographical networks. In 1969, Schelling introduced a model of racial segregation in which individuals move out of neighborhoods where their ethnicity constitutes a minority and suggested that this local behavior can cause global segregation effects. Our rigorous analysis shows that, in contrast to prior interpretations, the outcome exhibits local but not global segregation.<br> <br> Finally, we study learning outcomes in social networks. Individuals with independent opinions asynchronously update their declared opinion to match the majority report of their neighbors. We show that the population will converge to the majority opinion with high probability if the underlying network is large, sparse, and expansive, properties reflected by real social networks.<br> <br> Based on joint works with Christina Brandt, Michal Feldman, Gautam Kamath, Robert Kleinberg, Brendan Lucier, Brian Rogers, and Matt Weinberg.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a> ⋅ <a href="https://talks.cs.umd.edu/lists/2">CS Department</a><br>tag:talks.cs.umd.edu,2005:Talk/15792016-10-12T14:02:24-04:002016-10-12T14:02:24-04:00https://talks.cs.umd.edu/talks/1579The Muffin Problem<a href="https://www.cs.umd.edu/~gasarch/">William (Bill) Gasarch - University of Maryland College Park</a><br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">2107 Computer Science Instructional Center (CSI)</a><br>Friday, November 4, 2016, 1:00-2:00 pm<br><br><b>Abstract:</b> <div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">Consider the following problem:</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">You have 5 muffins and 3 students.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">You want to divide the muffins evenly so that everyone gets 5/3 of a muffin.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">You can clearly divide each muffin in 3 pieces and give each person 5/3.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">NOTE- the smallest piece is of size 1/3.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">Is there a procedure where the smallest piece is BIGGER than 1/3?</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">More genearlly what is the best you can do with m muffins and s students.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">We have proven many results about this that involve rather complex arguments.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">We state some of them:</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">1) For s+1 muffins and s students, if s==0 mod 3</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">then</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">(a) there is a procedure where the smallest piece is 1/3, and</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">(b) no procedure can do better.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">(We have results for s==1 and s==2 mod 3 but they are harder to state.)</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">2) For s=3,4,5,6 and any m we know the answer.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">3) For s=7,...,15 and all but a finite number of m we know the answer.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">4) Concrete examples:</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">11 muffins, 5 people then</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">There is a procedure with smallest piece 13/30.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">There is no better procedure.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">5) Concrete example:</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">16 muffins, 13 people</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">There is a procedure with smallest piece 14/39</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">There is no better procedure.</div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;"> </div>
<div class="gmail_msg" style="color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13px;">By Guangqi Cui, Naveen Durvasula, William Gasarch, Naveen Raman, Sung Hyun Yoo</div><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/16162016-11-29T08:55:14-05:002016-11-29T08:55:14-05:00https://talks.cs.umd.edu/talks/1616Correlation inequalities and the Group Steiner Tree problem(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/16812017-02-02T21:25:39-05:002017-02-02T21:25:39-05:00https://talks.cs.umd.edu/talks/1681Sum-of-Squares, Formal Introduction(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/16902017-02-09T21:27:44-05:002017-02-09T21:27:44-05:00https://talks.cs.umd.edu/talks/1690Sum-of-Squares, Formal Introduction(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/16942017-02-13T09:53:04-05:002017-02-13T09:53:04-05:00https://talks.cs.umd.edu/talks/1694Approximate Constraint Satisfaction Requires Sub-exponential Size Linear ProgramsPravesh Kothari - Princeton University<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, February 17, 2017, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span class="m_8388555535316963533inbox-inbox-m_-9036268435720859752inbox-inbox-lG gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px; background-color: rgba(251, 246, 167, 0.498039); outline: transparent dashed 1px;">Title</span><span class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">: Approximate Constraint Satisfaction Requires Sub-exponential Size Linear Programs</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span class="m_8388555535316963533inbox-inbox-m_-9036268435720859752inbox-inbox-lG gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px; background-color: rgba(251, 246, 167, 0.498039); outline: transparent dashed 1px;">Abstract</span><span class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">: This talk is about investigating the power of linear programming relaxations for solving constraint satisfaction problems. The main result is that for constraint satisfaction problems (CSPs), sub-exponential size linear programming relaxations are as powerful as n^{\Omega(1)}-rounds of the Sherali-Adams linear programming hierarchy. As a corollary, this yields sub-exponential size lower bounds for linear programming relaxations that beat random guessing for many CSPs such as MAX-CUT and MAX-3SAT. This is a nearly-exponential improvement over previous results; previously, it was only known that linear programs of size ~n^{</span><span class="m_8388555535316963533inbox-inbox-m_-9036268435720859752inbox-inbox-m_1082555628128130464inbox-inbox-s1 gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">(log n)} </span><span class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">cannot beat random guessing for any CSP [</span><span class="m_8388555535316963533inbox-inbox-m_-9036268435720859752inbox-inbox-m_1082555628128130464inbox-inbox-s2 gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">Chan-Lee-Raghavendra-Steurer 2013</span><span class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">].</span></p>
<p class="m_8388555535316963533inbox-inbox-m_-9036268435720859752inbox-inbox-m_1082555628128130464inbox-inbox-p1 gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">The lower bounds are obtained by exploiting and extending the recent progress in communication complexity for "lifting" query lower bounds to communication problems. The main ingredient is in a new structural result on “high-entropy rectangles” that may be of independent interest in communication complexity.</p>
<div class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;">Based on joint work with Raghu Meka and Prasad Raghavendra.</div><br><b>Bio:</b> <p><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Pravesh Kothari is a Research Instructor in the Department of Computer Science at Princeton University and a member of the School of Mathematics at the Institute for Advanced Study. He is also a part of the Simons Algorithms and Geometry Collaboration . Previously, he received my PhD from UT Austin advised by Adam Klivans and Bachelor's degree from IIT Kanpur advised by Surender Baswana.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/17202017-02-28T21:58:18-05:002017-02-28T21:58:18-05:00https://talks.cs.umd.edu/talks/1720Max-Cut algorithm using SoS(No abstract yet)<br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/17362017-03-16T10:52:18-04:002017-03-16T10:52:18-04:00https://talks.cs.umd.edu/talks/1736Approximation Algorithms for Facility Location and Clustering ProblemsKhoa Trinh - University of Maryland, College Park<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, March 31, 2017, 12:00-1:00 pm<br><br><b>Abstract:</b> <p><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Facility Location (FL) problems are among the most fundamental problems in</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">combinatorial optimization. FL problems are also closely related to</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Clustering problems. Generally, we are given a set of facilities, a set of</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">clients, and a symmetric distance metric on these facilities and clients.</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">The goal is to "open" the "best" subset of facilities, subject to certain</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">budget constraints, and connect all clients to the opened facilities so that</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">some objective function of the connection costs is minimized. In this</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">dissertation, we consider generalizations of classic FL problems. Since</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">these problems are NP-hard, we aim to find good approximate solutions in</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">polynomial time.</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">We study the classic $k$-median problem which asks to find a subset of at</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">most $k$ facilities such that the sum of connection costs of all clients to</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">the closest facility is as small as possible. Our main result is a</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">$2.675$-approximation algorithm for this problem. We also consider the</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Knapsack Median (KM) problem which is a generalization of the $k$-median</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">problem. In the KM problem, each facility is assigned an opening cost. A</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">feasible set of opened facilities should have the total opening cost at most</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">a given budget. The main technical challenge here is that the natural LP</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">relaxation has unbounded integrality gap. We propose a $17.46$-approximation</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">algorithm for the KM problem. We also show that, after a preprocessing step,</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">the integrality gap of the residual instance is bounded by a constant.</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">The next problem is a generalization of the $k$-center problem, which is</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">called the Knapsack Center (KC) problem and has a similar budget constraint</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">as in the KM problem. Here we want to minimize the maximum distance from any</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">client to its closest opened facility. The KC problem is well-known to be</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">$3$-approximable. However, the current approximation algorithms for KC are</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">deterministic and it is not hard to construct instances in which almost all</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">clients have the worst-possible connection cost. Unfairness also arises in</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">this context: certain clients may consistently get connected to distant</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">centers. We design a randomized algorithm which guarantees that the expected</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">connection cost of "most" clients will be at most $(1+2/e) \approx 1.74$</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">times the optimal radius and the worst-case distance remains the same. We</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">also obtain a similar result for the $k$-center problem: all clients have</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">expected approximation ratio about $1.592$ with a deterministic upper-bound</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">of $3$ in the worst case.</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">It is well-known that a few outliers (very distant clients) may result in a</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">very large optimal radius in the center-type problems. One way to deal with</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">this issue is to cover only some $t$ out of $n$ clients in the so-called</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">robust model. In this thesis, we give tight approximation algorithms for</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">both robust $k$-center and robust matroid center problems. We also introduce</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">a lottery model in which each client $j$ wants to be covered with</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">probability at least $p_j \in [0,1]$. We then provide randomized</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">approximation algorithms for center-type problems in this model which</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">guarantee the worst-case bounds of the robust model and slightly violate the</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">coverage and fairness constraints.</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Several of our results for FL problems in this thesis rely on novel</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">dependent rounding schemes. We develop these rounding techniques in the</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">general setting and show that they guarantee new correlation properties.</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Given the wide applicability of the standard dependent rounding, we believe</span><br class="gmail_msg" style="color: #212121; font-family: sans-serif; font-size: 13px;"><span style="color: #212121; font-family: sans-serif; font-size: 13px;">that our new techniques are of independent interests.</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/17372017-03-16T10:53:21-04:002017-03-16T10:53:21-04:00https://talks.cs.umd.edu/talks/1737Special CATS talk for visit dayStudents and faculty in theory<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">3118 Computer Science Instructional Center (CSI)</a><br>Friday, March 17, 2017, 1:00-2:00 pm<br><br><b>Abstract:</b> <p>A brief overview of the various problems students and faculty in theory group are working on. </p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/18412017-08-09T11:46:46-04:002017-08-09T11:46:46-04:00https://talks.cs.umd.edu/talks/1841A Fast Approximate Algorithm for Mapping Long Reads to Large Reference DatabasesChirag Jain - Georgia Tech<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=AVW">3258 A.V. Williams Building (AVW)</a><br>Friday, August 11, 2017, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Emerging single-molecule sequencing technologies from Pacific Biosciences and Oxford Nanopore have revived interest in long read mapping algorithms. Alignment-based seed-and-extend methods demonstrate good accuracy, but face limited scalability, while faster alignment-free methods typically trade decreased precision for efficiency. In this work, we combine a fast approximate read mapping algorithm based on minimizers with a novel MinHash identity estimation technique to achieve both scalability and precision. In contrast to prior methods, we develop a mathematical framework that defines the types of mapping targets we uncover, establish probabilistic estimates of p-value and sensitivity, and demonstrate tolerance for alignment error rates up to 20%. With this framework, our algorithm automatically adapts to different minimum length and identity requirements and provides both positional and identity estimates for each mapping reported. For mapping human PacBio reads to the hg38 reference, our method called Mashmap is 290x faster than BWA-MEM with a lower memory footprint and recall rate of 96%. We further demonstrate Mashmap’s scalability by mapping noisy PacBio reads to the complete NCBI RefSeq database containing 838 Gbp of sequence and > 60,000 genomes. I will also discuss our ongoing work on extending Mashmap framework to split-read mapping as well as genome to genome mapping. </span></p><br><b>Bio:</b> <p><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Chirag Jain is a third year PhD student in Srinivas Aluru's lab at Georgia Institute of Technology. He earned his bachelor’s degree in CS at Indian Institute of Technology at New Delhi. His research focusses on designing scalable algorithms for combinatorial problems in genomics</span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>tag:talks.cs.umd.edu,2005:Talk/18472017-08-29T15:26:26-04:002017-08-30T11:34:33-04:00https://talks.cs.umd.edu/talks/1847Assembly of big genomic data Paul Medvedev - Pennsylvania State University<br><a href="http://www.umd.edu/CampusMaps/bld_detail.cfm?bld_code=CSI">1122 Computer Science Instructional Center (CSI)</a><br>Friday, September 29, 2017, 1:00-2:00 pm<br><br><b>Abstract:</b> <p><span style="color: #212121; font-family: sans-serif; font-size: 13px;">As genome sequencing technologies continue to facilitate the generation of large datasets, developing scalable algorithms has come to the forefront as a crucial step in analyzing these datasets. In this talk, I will discuss several recent advances, with a focus on the problem of reconstructing a genome from a set of reads (genome assembly). I will describe low-memory and scalable algorithms for automatic parameter selection and de Bruijn graph compaction, recently implemented in two tools KmerGenie and bcalm. I will also present recent advances in the theoretical foundations of genome assemblers.</span></p><br><b>Bio:</b> <p><span style="color: #212121; font-family: sans-serif; font-size: 13px;">Paul Medvedev is an Assistant Professor at the Pennsylvania State University in the departments of "Computer Science and Engineering" and "Biochemistry and Molecular Biology." He heads the Center for Computational Biology and Bioinformatics at Penn State. Prior to joining Penn State, he was a postdoc with<span class="Apple-converted-space"> </span></span><a style="color: #7e57c2; z-index: 0; position: relative; font-family: sans-serif; font-size: 13px;" href="http://cseweb.ucsd.edu/~ppevzner/">Pavel Pevzner</a><span style="color: #212121; font-family: sans-serif; font-size: 13px;"><span class="Apple-converted-space"> </span>in<span class="Apple-converted-space"> </span></span><a style="color: #7e57c2; z-index: 0; position: relative; font-family: sans-serif; font-size: 13px;" href="http://www.cse.ucsd.edu/">UC San Diego</a><span style="color: #212121; font-family: sans-serif; font-size: 13px;"><span class="Apple-converted-space"> </span>and received his Ph.D. at the<span class="Apple-converted-space"> </span></span><a style="color: #7e57c2; z-index: 0; position: relative; font-family: sans-serif; font-size: 13px;" href="http://www.cs.toronto.edu/">University of Toronto</a><span style="color: #212121; font-family: sans-serif; font-size: 13px;"><span class="Apple-converted-space"> </span>in Computer Science under the supervision of<span class="Apple-converted-space"> </span></span><a style="color: #7e57c2; z-index: 0; position: relative; font-family: sans-serif; font-size: 13px;" href="http://www.cs.toronto.edu/~brudno">Michael Brudno</a><span style="color: #212121; font-family: sans-serif; font-size: 13px;"><span class="Apple-converted-space"> </span>and<span class="Apple-converted-space"> </span></span><a style="color: #7e57c2; z-index: 0; position: relative; font-family: sans-serif; font-size: 13px;" href="http://www.cs.toronto.edu/~bor">Allan Borodin</a><span style="color: #212121; font-family: sans-serif; font-size: 13px;">.<span class="Apple-converted-space"> </span></span></p><br>This talk is part of the following lists: <a href="https://talks.cs.umd.edu/lists/6">CATS</a><br>