http://magic.aladdin.cs.cmu.edu Algorithms are everywhere. Wed, 11 Jun 2008 17:17:41 +0000 http://backend.userland.com/rss092 en Wednesday June 11th, 2008 Wean 8220 1:30pm Title: Graph partitioning into isolated, high conductance clusters: Theory, computation and applications to preconditioning. Yiannis Koutis, CMU Abstract: We study the problem of decomposing a weighted graph with $n$ vertices into a collection $P$ of vertex disjoint clusters such that, for all clusters $C$ in $P$, the graph ... http://magic.aladdin.cs.cmu.edu/2008/06/11/theory-seminar-2008-06-11/ Date: 2008-05-14 12:00 Speaker: Yiannis Koutis Title: Faster algebraic algorithms for path and packing problems Place: NSH 1507 Abstract: We study the problem of deciding whether an n-variate polynomial, presented as an arithmetic circuit G, contains a degree k square-free term with an odd coefficient. We show that if G can be evaluated over the ... http://magic.aladdin.cs.cmu.edu/2008/05/13/theory-lunch-2008-05-14/ Say you are preparing a camera-ready submission and you are running a little low on space, maybe by a few lines. At this point, hopefully you are willing to put in the time and try rewording some of your sentences. A usual way to start is to identify a paragraph ... http://magic.aladdin.cs.cmu.edu/2008/05/12/using-raggedbottom-to-identify-where-to-reword/ Date: 2008-05-07 12:00 Speaker: Karl Wimmer Title: Polynomial regression under arbitrary product spaces Place: NSH 1507 Abstract: Recently, Kalai et. al gave a variant of the “Low-Degree Algorithm” for agnostic learning (learning with arbitrary classification noise) under the uniform distribution on {0,1}^n. One result of their work is an agnostic learning algorithm with respect to ... http://magic.aladdin.cs.cmu.edu/2008/05/07/theory-lunch-2008-05-07/ In an Intel Software Network article titled Parallel computing: disappearing from CS curricula???, Michael Wrinn demonstrated that parallel computing has gradually disappeared from popular CS curricula in the past 10+ years. His first example is: […] a panelist at IPDPS (in Miami, a couple of weeks ago) assert that parallel-processing topics ... http://magic.aladdin.cs.cmu.edu/2008/05/05/parallel-algorithms-dropped-from-clrs/ Title:Packing in Multipartite Graphs Speaker: Ryan Martin, Iowa State When: May 2, 11:30-12:30 Where: Hamburg Hall, Room 237 Abstract: We present some results on packing graphs in dense multipartite graphs. This is a question very similar to the Hajnal-Szemeredi theorem, which gives sufficient minimum-degree conditions for an $n$-vertex graph to have a subgraph consisting of ... http://magic.aladdin.cs.cmu.edu/2008/05/01/aco-seminar-2008-05-02/ Title: Scarf’s Lemma and the Stable Paths Problem Speaker: Penny Haxell, Waterloo When: May 1, 12:30-13:30 Where: Porter Hall 125B Abstract: We address a question in graphs called the stable paths problem, which is an abstraction of a network routing problem concerning the Border Gateway Protocol (BGP). The main tool we use is Scarf’s Lemma. ... http://magic.aladdin.cs.cmu.edu/2008/04/30/aco-seminar-2008-05-01/ Friday May 2nd, 2008 3:30 PM 7500 Wean Hall Nash Bargaining via Flexible Budget Markets Vijay V. Vazirani, Georgia Tech In his seminal 1950 paper, John Nash defined the bargaining problem; the ensuing theory of bargaining lies today at the heart of game theory. In this work, we initiate an algorithmic study of Nash bargaining ... http://magic.aladdin.cs.cmu.edu/2008/04/29/theory-seminar-2008-05-02/ Iterative Methods in Combinatorial Optimization Mohit Singh Wednesday, April 30, 2008, 3:30 pm, 384 Posner Abstract: Linear programming has been a successful tool in combinatorial optimization to achieve polynomial time algorithms for problems in P and also to achieve good approximation algorithms for problems which are NP-hard. We demonstrate that iterative methods give a ... http://magic.aladdin.cs.cmu.edu/2008/04/27/thesis-oral-2008-04-30/ A while ago I checked out Beautiful Code from our library. Jon Bentley wrote chapter 3, which is about Quicksort, and paradoxically named the chapter “The Most Beautiful Code I Never Wrote”. This video is an extension of that chapter and will explain the name. I can recommend the talk, ... http://magic.aladdin.cs.cmu.edu/2008/04/27/jon-bentley-on-three-beautiful-quicksorts/ April 30, 2008 Varun Gupta 12:00 PM, 1507 Newell-Simon Hall Title: Optimal size-based scheduling with selfish users Abstract: We consider the online single-server job scheduling problem. It is known that to minimize the average response time of jobs in this setting, at all times the job with the shortest remaining service time must be scheduled. ... http://magic.aladdin.cs.cmu.edu/2008/04/27/theory-lunch-2008-04-30/ Available here at informIT. Andrew Binstock and Donald Knuth converse on the success of open source, the problem with multicore architecture, the disappointing lack of interest in literate programming, the menace of reusable code, and that urban legend about winning a programming contest with a single compilation. Among other things, he explained ... http://magic.aladdin.cs.cmu.edu/2008/04/25/knuth-interview-2008-04-25/ Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time Pall Melsted, CMU April 25, 2008, 3:30PM, Wean 7220 Abstract: We present a linear expected time algorithm for finding maximum cardinality matchings in sparse random graphs. This is optimal and improves on previous results by a logarithmic factor. This is joint work ... http://magic.aladdin.cs.cmu.edu/2008/04/24/theory-seminar-2008-04-25/ Title: The formulation complexity of minimum cut Speaker: Ojas Parekh, Emory University When: April 24, 12:30-13:30 Where: Porter Hall 125B Abstract: Our focus in this talk will be the size of linear programming formulations of combinatorial optimization problems. We may view this parameter as akin to traditional measures of complexity, such as computational time and ... http://magic.aladdin.cs.cmu.edu/2008/04/23/aco-seminar-2008-04-23/ Date: 2008-04-23 12:00 Place: NSH 1507 Speaker: Elaine Shi Title: How to build private Google Docs Abstract: I will describe some latest results in predicate encryption. The crypto construction allows a user to store her personal files on a remote untrusted server, and make expressive search queries to retrieve certain documents. The remote untrusted ... http://magic.aladdin.cs.cmu.edu/2008/04/22/theory-lunch-2008-04-23/ Title: Approximation Algorithms for Vehicle Routing and Scheduling. Viswanath Nagarajan, Thesis Proposal for Ph.D. in Algorithms, Combinatorics and Optimization. 10:30am Wednesday 23-April Room 384, 3rd floor Posner Hall (Tepper School of Business) Broadly speaking, any scheduling problem can be characterized as serving a set of requests using a limited set of resources, subject to ... http://magic.aladdin.cs.cmu.edu/2008/04/22/thesis-proposal-2008-04-23/ Date: 2008-04-16 12:00 Speaker: Mike Dinitz Title: The Discounted Secretary Problem Place: NSH 1507 Abstract: The classical secretary problem studies how to select online an element with maximum value in a randomly ordered sequence. The problem is closely connected with online mechanism design in which agents {e} with private values v(e) for a good arrive ... http://magic.aladdin.cs.cmu.edu/2008/04/15/theory-lunch-2008-04-16/ Name: Nikolaos Sahinidis University: Carnegie Mellon University Dept. of Chemical Engineering Date: Friday, April 18, 2008 Time: 3:30 to 5:00 pm Location: Room 388 Posner Hall Title: Optimization in the New Biology Abstract: A variety of modern bioinformatics and systems biology problems can be approached systematically from an optimization point ... http://magic.aladdin.cs.cmu.edu/2008/04/14/or-seminar-2008-04-18/ Title: A Polynomial Bound on Vertex Folkman Numbers Speaker: Andrzej Dudek, Emory University When: Tuesday April 15, 12:30-13:30 Where: Wean Hall 5304 Abstract: In 1970, Folkman proved that for a given integer r and a graph G of order n there exists a graph H with the same clique number as G such that every ... http://magic.aladdin.cs.cmu.edu/2008/04/14/aco-seminar-2008-04-15/ Friday April 18th, 2008 3:30pm WEH 7220 TITLE: What makes a good Steiner point? Benoit Hudson Toyota Technological Institute at Chicago ABSTRACT: The mesh refinement problem is to take an input geometry (defined by a set of points, curves, and surfaces), and output a set of points that both “respects'’ the geometry and has good “quality.'’ ... http://magic.aladdin.cs.cmu.edu/2008/04/14/theory-seminar-2008-04-18/