Graduate Algorithms Seminar (CpSc 9500, Section 2)

The Friday Algorithms Seminar meets every Friday from 3:30-4:30 in McAdams Hall room 114. To join the mailing list in order to receive talk announcements, please email the seminar organizer, Dr. Brian Dean ( Students may register every semester for 1 unit of credit, for which attendance every week is expected (please contact Brian Dean if you are interested in registering for more than 1 unit of credit).

Next talk

Title: Using the PCP Theorem to Prove Inapproximability Results
Speaker: Brian Dean
Location: McAdams 114
Date/Time: Friday, November 20, 3:30pm-4:30pm

Abstract: The PCP theorem (short for Probabilistically Checkable Proofs) is one of the most groundbreaking (and complicated) results to come out of the field of complexity theory in the past few decades. It gives an alternative characterization of problems in NP (including all of our favorite NP-complete problems) where "yes" solutions of these problems can be verified by a randomized algorithm that has a long "proof" provided to it for guidance, but where the algorithm only needs to look at a few randomly-chosen locations in the proof (in fact, only a constant number of locations!) to convince itself of its answer. The PCP theorem has been instrumental in helping to prove inapproximability results -- for example, that it is NP-hard even to approximate certain problems to within, say, a given constant factor. Today, I'll give an example of how the PCP theorem can be used in this fashion.

For more information on the algorithms seminar and a list of past topics, please see:

Previous Talks

FALL 2015
Date Speaker Topic
11/13/2015 Brian Dean Locality Sensitive Hashing to the Rescue
11/6/2015 Christian Staudt Algorithms and Software for the Analysis of Large Complex Networks
10/30/2015 Brian Dean Shortest Path Network Interdiction
10/16/2015 Brian Dean Convex Hull Tricks
10/9/2015 Brian Dean Advantages of Randomization: Game Tree Evaluation and Property Testing
10/2/2015 Brian Dean Matching Nuts and Bolts
9/25/2015 Brian Dean Minimax Relationships and Applications
9/18/2015 Hayato Ushijima-Mwesigwa Streaming Algorithms for Massive Graphs
9/11/2015 Brian Dean The Burrows-Wheeler Transform
9/4/2015 Brian Dean The Revenge of the Inverse Ackermann Function
8/28/2015 Brian Dean Inverse Ackermann Running Times Demystified
FALL 2014
Date Speaker Topic
12/5/2014 Brian Dean Selection from Monotone Grids and Heaps
11/21/2014 Brian Dean Functional Double-Ended Queues and Recursive Slowdown
11/14/2014 Brian Dean Max Flows and Electrical Networks
11/7/2014 Brian Dean Multiplicative Weights and Multicommodity Flows
10/31/2014 Brian Dean Multiplicative Weights and Learning from Experts
10/24/2014 Talayeh Razzaghi Relaxed Support Vector Machine Extensions
10/10/2014 Brian Dean Compressed Sensing and its Relatives
10/3/2014 Michael Burr Data Depth: An Introduction
9/26/2014 Brian Dean Approximating the Graph TSP Problem
9/19/2014 Brian Dean Implicit Analytics on Correlation Networks
9/12/2014 Hayato Ushijima-Mwesigwa Approximating the Number of Perfect Matchings in a Bipartite Graph
9/5/2014 Brian Dean Metric Space Embeddings 101
8/29/2014 Rommel Jalasutram Approximating the Stable Matching Problem with Ties and Incomplete Lists
8/22/2014 Brian Dean New Results for Unsplittable Stable Allocation Problems
Date Speaker Topic
4/25/2014 Christopher Corsi Filesystem Data Structures and their Challenges
4/18/2014 Ben Cousins A Cubic Algorithm for Computing Gaussian Volume
4/11/2014 Brian Dean Perfectly-Balanced Trees
4/4/2014 Paul Kilgo A Secialized Algorithm for Path Generation for the Numerical Computation of Path Integrals
3/28/2014 Yihua Ding A Polynomial-Time Self Stabilizing Algorithm for Minimal Total Dominating Set in an Arbitrary Graph
3/14/2014 Brian Dean Approximate Selection
3/7/2014 Rommel Jalasutram Improving Randomized Resource Allocation
2/28/2014 Brian Dean Succinct Data Structures for Representing Trees
2/21/2014 Brian Dean Thinking Outside the Box -- Algorithms for Klee's Measure Problem
2/14/2014 Brian Dean Algorithms and Finding True Love
2/7/2014 Rommel Jalasutram Coloring 3-Colorable Graphs
1/31/2014 Brian Dean Special Properties of Random Inputs
1/24/2014 Doug Shier A Simple Network Approach to Ranking Athletic Teams
1/17/2014 Brian Dean Offense-Defense Ranking Algorithms
FALL 2013
Date Speaker Topic
12/6/2013 Brian Dean History-Independent Data Structures
11/22/2013 Rommel Jalasutram Randomized Routing
11/15/2013 Hayato Ushijima-Mwesigwa Counting Spanning Trees
11/1/2013 Brian Dean Approximating the Prize-Collecting Traveling Salesman Problem
10/25/2013 Brian Dean Sorting Without Transitivity
10/18/2013 Brian Dean Integer Range Searching
10/11/2013 Brian Dean Fast Minimum Spanning Tree Verification
10/4/2013 Brian Dean Linkages and Graph Rigidity
9/27/2013 Michael Burr Amortization: Classical, Algebraic, and Continuous
9/20/2013 Brian Dean Recent Bounds for Hashing with Linear Probing
9/13/2013 Brian Dean Parametric Shortest Paths and Min Cuts in Planar Graphs
9/6/2013 Brian Dean Sketchy Data Structures
8/30/2013 Ágnes Cseh Stability in Networks
8/23/2013 Brian Dean Wheels within Wheels and Ear Decompositions
Date Speaker Topic
4/26/2013 Sam Casacio Sparse Voxel Octrees
4/19/2013 Brian Dean Scaling Algorithms and Shortest Paths
4/12/2013 Brian Dean Spanning Trees and Approximation
4/5/2013 Brian Dean Maximum Adjacency Orderings in Flows and Cut Algorithms
3/29/2013 Brian Dean Geometric Minimum Spanning Tree Problems
3/8/2013 Rommel Jalasutram Approximating k-Median via Pseudo-Approximation
2/15/2013 Brian Dean Finding the k Minimum Spanning Trees
2/8/2013 Raghuveer Mohan Finding the k Shortest Paths
2/1/2013 Brian Dean Extreme Points in Approximation Algorithms
1/18/2013 Rommel Jalasutram Simple, Fast and Deterministic Gossip and Rumor Spreading
1/11/2013 Brian Dean Path Decompositions of Trees
FALL 2012
Date Speaker Topic
11/30/2012 Brian Dean Locality-Sensitive Hashing and Similarity Computation
11/16/2012 Rommel Jalasutram Probabilistic Approximation of Metrics by Tree Metrics
11/9/2012 Brian Dean Introduction to Personal Pagerank
10/26/2012 Brian Dean On-Line Algorithms and Lost Cows
10/19/2012 Chad Waters Classic Nintendo Games are (NP-)Hard
10/12/2012 Brian Dean Embeddings in Approximation Algorithms
10/5/2012 Brian Dean My Favorite Problems from IOI 2012
9/28/2012 Rommel Jalasutram Randomized Rounding and Approximations
9/14/2012 Brian Dean Approximating the Traveling Salesman Path Problem (continued)
9/7/2012 Brian Dean Approximating the Traveling Salesman Path Problem
8/31/2012 Brian Dean How to Cut a Cake
Date Speaker Topic
4/27/2012 Raghuveer Mohan O(1)-Time Unsorting by Prefix-Reversals in a Boustrophedon Linked List
4/20/2012 Aditya Sriram Modeling Causality and Making Predictions
4/13/2012 Brian Dean How to Hang a Picture in Polynomial Time
4/6/2012 Rommel Jalasutram Aggregating Inconsistent Information. Ranking and Clustering
3/30/2012 Brian Dean Simple Algorithms for Approximate Order Statistics
3/9/2012 Brian Dean Feature Selection via Linear Programming
3/2/2012 Brian Dean Introduction to Streaming Algorithms
2/24/2012 Brian Dean Sparse Fourier Transforms
2/17/2012 Brian Dean Parametric Search
2/10/2012 Rommel Jalasutram Popular Matchings
2/3/2012 Brian Dean High-Multiplicity Scheduling Problems
1/27/2012 Brian Dean The Benefit of Doing Tasks in Random Order
1/20/2012 Sam Bryfczynski Using Clustering and Visualizations to Analyze Student Work
FALL 2011
Date Speaker Topic
12/02/2011 Sumod Mohan Gomory-Hu Clustering and Application to Image Segmentation
11/18/2011 Rommel Jalasutram Building the Cactus of a Graph
11/11/2011 Brian Dean Estimating Network Reliability
11/4/2011 Brian Dean Maximum Adjacency Orderings and Minimum Cuts
10/21/2011 Brian Dean Realistic 3D Cell Cytoskeletal Reconstruction from Machine Vision Analysis of Confocal Microscopy Images
10/14/2011 Rommel Jalasutram Very Simple Methods for All Pair Network Flow Analysis
10/07/2011 Brian Dean Global Minimum Cuts in Planar Graphs
9/30/2011 Brian Dean Algorithms for Sports
9/23/2011 Brian Dean Clustering with Parametric Minimum Cuts
9/16/2011 Brian Dean On-Line Load Balancing
9/9/2011 Brian Dean Community Structure in Signed Networks
9/2/2011 Brian Dean Computing the Girth of a Graph
8/26/2011 Brian Dean Selected Problems from Recent Informatics Olypiads
Date Speaker Topic
4/29/2011 Elizabeth Matthews Procedural Generation of Story-Driven Maps
4/22/2011 Brian Dean Fully-Dynamic Graph Connectivity
4/15/2011 Aditya Sriram Learning Topologies of Graphical Models using Parallel Interactive Markov Chain Monte Carlo methods
4/8/2011 Ben Cousins Jane: A New Tool for the Cophylogeny Reconstruction Problem
4/1/2011 Brian Dean Maintaining Dynamic Strongly-Connected Components and Transitive Closure in Directed Graphs
3/11/2011 Chad Waters Randomized Reduction
3/4/2011 Gift Kositwattanarerk Modern Algorithms for the Decoding Problem
2/25/2011 Rommel Jalasutram Weighted On-Line Bipartite Matching
2/18/2011 Raghuveer Mohan 2D Van Emde Boas Structures
2/11/2011 Chad Waters Optimal Pattern Matching in LZW-Compressed Strings
2/4/2011 Matt Dabney Approximating the Highway Problem
1/28/2011 Brian Dean Heuristics for Large-Scale Assignment Problems
1/21/2011 Brian Dean Matching a Million Points
1/14/2011 Brian Dean Auction Algorithms for Optimal Matchings
FALL 2010
Date Speaker Topic
12/3/2010 Brian Dean Approximation and Compression in Shortest Path Computation
11/19/2010 Shelby Darnell A Genetic Algorithm for Feature Reduction on Finger Shape and Dorsum Surface Features
11/5/2010 Rommel Jalasutram Multiple-Source Shortest Paths in Planar Graphs
10/29/2010 Raghuveer Mohan A Simpler Implementation and Analysis of Chazelle's Soft Heaps
10/22/2010 Brian Dean Parabolic Lifting, Etc.
10/15/2010 Brian Dean Encoding Numbers in Binary without Wasting Space
10/1/2010 Brian Dean Double Displacement and Deterministic Perfect Hash Table Construction
9/24/2010 Rommel Jalasutram Better and Simpler Approximation Algorithms for the Stable Matching Problem
9/17/2010 Brad Paynter An Optimization Approach to a Geometric Packing Problem
9/10/2010 Brian Dean Maximum Flows in Planar Graphs II
9/3/2010 Brian Dean Maximum Flows in Planar Graphs I
8/27/2010 Brian Dean Eulerian Augmentation
Date Speaker Topic
4/23/2010 Brian Dean Binary Search
4/16/2010 Brian Dean Algorithms for the Optimal Staying up Late Problem
4/9/2010 Rommel Jalasutram Self-Stabilizing Depth-First Search
4/2/2010 Shelby Darnell Reducing 3D Finger Surface Features Using Computational Intelligence
3/26/2010 Brian Dean Path Packing, Covering, and Cutting in Trees
3/12/2010 Brian Dean Splay Trees, Dynamic Trees, and Tango Trees
3/5/2010 Brian Dean Random Walks, Sampling, and Approximate Counting
2/26/2010 Sumod Mohan Computer Vision and Graph Cuts
2/19/2010 Rommel Jalasutram The Complexity of Computing a Nash Equilibrium
2/12/2010 Brian Dean System-Optimal Versus User-Optimal Network Routing
2/5/2010 Raghuveer Mohan New Algorithms for Building Cartesian Trees
1/29/2010 Brian Dean Optimal Stable Marriage Algorithms
1/22/2010 Brian Dean Adaptive Stable Marriage Algorithms
1/15/2010 Wayne Goddard Master-Slave Self-Stabilizing Algorithms
1/8/2010 Brian Dean Parametric Maximum Flows and Graph Clustering
FALL 2009
Date Speaker Topic
12/4/2009 Brian Dean Algorithmic Games
11/20/2009 Pradip Srimani Recent Results in Self-Stabilizing Algorithms
11/13/2009 Brian Dean Fair and Unfair Flow Allocations
11/6/2009 Brian Dean My Favorite Algorithmic Programming Competition Problems
10/30/2009 Brian Dean Algorithms for Problems on Regular Bipartite Graphs
10/16/2009 Brian Dean A Simple Method for Analyzing Randomized Divide-and-Conquer Algorithms
10/2/2009 David Jacobs A Self-Stabilizing Algorithm for Maximal Matching
9/18/2009 Steve Hedetniemi A New Look at an Old Self-Stabilizing Algorithm for {2}-Domination
9/11/2009 Brian Dean Encoding Connectivity in Graphs
9/4/2009 Brian Dean Reconstructing Edge-Disjoint Paths
8/28/2009 Brian Dean Shortest Path Computation in Planar Graphs
Date Speaker Topic
4/17/2009 Brian Dean Time-Dependent Shortest Path and Network Flow Problems
4/10/2009 Brian Dean Approximating Shortest Path Distances and Diameter
4/3/2009 Brian Dean New Approaches for Learning Greedy Orderings
3/27/2009 Wayne Goddard Self-Stabilizing Algorithms for Domination with a Distributed Daemon
3/13/2009 Brian Dean Shortest Paths and Matrix Multiplication
3/6/2009 Steve Hedetniemi NP-completeness Methods of Alice McRae: A Tutorial on NP-completeness
2/27/2009 Brad Paynter An Optimization Approach to a Geometric Packing Problem
2/20/2009 John Dabney An Efficient Algorithm for Verifying Stable Matchings
2/13/2009 Brian Dean Stable Allocation Problems and Algorithms
2/6/2009 Brian Dean Similarity Computation Based on Connectivity
1/30/2009 Brian Dean Approximating the Bounded-Degree Minimum Spanning Tree Problem
1/23/2009 Brian Dean Minimum-Degree Spanning Trees
1/16/2009 Brian Dean Rank-Sensitive Priority Queues
1/9/2009 Brian Dean Min-Max Theorems in Discrete Optimization
FALL 2008
Date Speaker Topic
12/5/2008 Jeremy Carter Folding and Cutting Paper
11/21/2008 Brian Dean Using Linear Programming to Find Bugs in Computer Programs and Humans
11/14/2008 Brian Dean Semidefinite Programming and Approximation Algorithms
11/7/2008 Brian Dean Finding a Central Element
10/31/2008 Daniela Ferrero Directed Hypergraphs as Interconnection Networks Models
10/24/2008 Brian Dean Lagrangian Relaxation, Parametric Optimization, and Spanning Tree Problems
10/17/2008 David Jacobs Three Ways to Compute the Characteristic Polynomial of a Tree
10/10/2008 Brian Dean Parametric Search and Ratio Objectives
9/26/2008 Pradip Srimani Introduction to Distributed Localized Graph Algorithms
9/19/2008 Brian Dean Unsplittable Bipartite Matchings
9/12/2008 Brian Dean Convex Bipartite Matchings
9/5/2008 Brian Dean On-Line Bipartite Matching
8/29/2008 Brian Dean Popular Matchings