Past Theory Seminars

February 22, 2007 Details have changed!
Please note the non-standard day, time, and room: Thursday, 5-6pm, 380 Soda Hall.

The Hiring Problem and Lake Wobegon Strategies

Michael Mitzenmacher
Harvard University

February 12, 2007New algorithms for online learning and portfolio management

Elad Hazan
IBM Almaden Research Center

January 25, 2007 Please note the non-standard day and location: 380 Soda Hall, Thursday, 4-5pm.

Determinant Versus Permanent

Manindra Agrawal
IIT Kanpur

December 4, 2006A rigorous analysis of the cavity method for counting matchings

Mohsen Bayati
Stanford University

November 27, 2006Monte Carlo Markov chains in Statistical Physics: Some recent progress and open problems

Fabio Martinelli
University of Rome 3

November 6, 2006Algorithms and thresholds for random SAT: from a physical theory to a combinatorial picture

Elitza Maneva
IBM Almaden

October 9, 2006Algorithms for edit distance on permutations

Robert Krauthgamer
IBM Almaden

September 25, 2006Low distortion embeddings for edit distance

Yuval Rabani
Technion, Haifa, Israel

October 2, 2006 There is no seminar this week. September 11, 2006Optimal Cost-Sharing Mechanisms

Tim Roughgarden
Stanford University

August 28, 2006Spending Constraint Utilities, with Applications to the Adwords Market

Vijay Vazirani
Georgia Institute of Technology

May 15, 2006 Note: Location is 380 Soda Hall for this seminar only.

Dissertation Talk:
Quantum fault-tolerance against probabilistic Pauli noise

Ben Reichardt
U.C. Berkeley

May 8, 2006A relative-error CUR decomposition for matrices and its data applications

Michael W. Mahoney
Yahoo! Research

May 1, 2006Approximation Algorithms for Stochastic Optimization

Anupam Gupta
Carnegie Mellon University

April 24, 2006Capacity-Achieving List Decodable Codes for Worst-Case Errors

Venkat Guruswami
University of Washington

April 17, 2006On the Fourier Coefficients of Symmetric Boolean Functions (with applications to learning Symmetric Juntas)

Aranyak Mehta
IBM Almaden

March 13, 2006 Note: This week the seminar is being held in 380 Soda Hall.

Beyond VCG: Frugality of Truthful Mechanisms

David Kempe
University of Southern California

Note: There is no seminar the week of March 27 due to Spring Break.

March 6, 2006Coloring Geometric Hypergraphs

Shakhar Smorodinsky
Courant Institute, NYU

February 27, 2006Cohomology in Grothendieck Topologies and Lower Bounds in Boolean Complexity

Joel Friedman
University of British Columbia

February 13, 2006Privacy-preserving protocols through polynomial encodings

Michael Freedman
NYU/Stanford

Note: There is no seminar the week of February 20 due to Presidents' Day.

February 6, 2006A non-interactive approach to database privacy

Shuchi Chawla
Stanford University

January 30, 2006Algorithms for Proteomics and Glycomics

Marshall Bern
Palo Alto Research Center

December 16, 2005 Note: Special Theory Seminar
11am-12:30pm Friday, in Soda 310

Three Variations on the Theme of Comparative Genomics:
Metagenomics, Mitochondrial Gene Rearrangements and MicroRNAs

Kevin Chen
U.C. Berkeley
Dissertation talk

December 5, 2005Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

David Zuckerman
U.T. Austin

November 28, 2005SNP and haplotype analysis - algorithms and applications

Eran Halperin
International Computer Science Institute

November 21, 2005UGC & SDP; or, Are there any more polynomial time algorithms?

Ryan O'Donnell
Microsoft Research

November 7, 2005Computing Equilibria

Christos Papadimitriou
U.C. Berkeley

Theory seminar will not meet on November 14 due to BATS on November 18.

October 31, 2005Private approximation of search problems

Amos Beimel
Ben Gurion University

October 17, 2005Playing the k-armed bandit against an adaptive adversary

Tom Hayes
U.C. Berkeley

Theory seminar will not meet on October 24 due to FOCS.

October 10, 2005On the Capacity of Information Networks

Bobby Kleinberg
U.C. Berkeley

October 3, 2005Raptor Codes

Amin Shokrollahi
EPF Lausanne

September 26, 2005 Expansion, embeddings, and metric geometry

James Lee
U.C. Berkeley
Dissertation talk

September 19, 2005Group-theoretic Algorithms for Matrix Multiplication

Prof. Chris Umans
Caltech

September 12, 2005Universal Mechanism Design

Prof. Silvio Micali
MIT

Note: This talk will be held in 306 Soda instead of the Woz.

September 8, 2005Worst-case versus average-case hardness for NP

Andrej Bogdanov
U.C. Berkeley
Dissertation Talk

Note: This talk is scheduled for 1-2:30pm on Thursday, September 8.

August 29, 2005Aggregating Inconsistent Information: Ranking and Clustering

Nir Ailon
Princeton University

May 16, 2005Dissertation Talk: Combinatorics of Viterbi Sequences

Eric Kuo
UC Berkeley

May 2, 2005On FFTs and PCPPs (for Reed-Solomon codes)

Eli Ben-Sasson
Technion and Toyota Technological Institute at Chicago

April 18, 2005Models of Real-World Random Networks

MSRI Workshop, April 18 to April 22, 2005

April 4, 2005Oracles Are Subtle But Not Malicious

Scott Aaronson
Institute for Advanced Study in Princeton

March 28, 2005Flow-based Rounding, Power Law Graphs, and SDP Embeddings

Kevin Lang
Yahoo Research Labs

March 21 - 25, 2005

Spring Break.

March 14, 2005Sidon Sets, Turan Bounds, and Hardness of Discrete Logarithm

Ilya Mironov
Microsoft Silicon Valley Research Center

March 7, 2005Phase Transitions in Computation and Reconstruction

MSRI Workshop, March 7 to March 11, 2005

February 28, 2005A* Search with Triangle Inequality

Andrew Goldberg
Microsoft Research-- Silicon Valley

February 14, 2005On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

Oded Regev
Tel Aviv University

February 7, 2005Online Conflict-Free Coloring

Haim Kaplan
Tel Aviv University

January 31, 2005Markov chains in algorithms and statistical physics

MSRI Workshop, January 31 to February 4, 2005

January 24, 2005Approximate Distance Oracles and Spanners with Sublinear Error Terms

Uri Zwick
Tel Aviv University

2004

December 6, 2004Graph Partitioning, Clustering with Qualitative Information
and Grothendieck-type Inequalities

Assaf Naor
Microsoft Research

November 29, 2004Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth

Mohammad Taghi Hajiaghayi
MIT

November 22, 2004New Notions of Security: Network Security without Trusted Setup

Amit Sahai
UCLA

November 15, 2004Scaling Exponents in Random Combinatorial Optimization

David Aldous
UC Berkeley Statistics

November 1, 2004The mixing time for the Thorp shuffle

Ben Morris
Microsoft Research & Indiana University

October 26, 2004Geometric Embeddings, Graph Partitioning, and Expander Flows: A survey of recent results

Sanjeev Arora
Princeton University

October 11, 2004The Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem

Balaji Prabhakar
Stanford

September 20, 2004An almost-sure polynomial bound on the diameter of the symmetric group

Tom Hayes
UC-Berkeley

September 13, 2004Price of Anarchy, Locality Gap, and a Network Service Provider Game

Rohit Khandekar
UC-Berkeley

August 30, 2004The power of Quantum Encodings

Iordanis Kerenidis
UC Berkeley

March 8, 2004Learning Mixtures of Product Distributions

Ryan O'Donnell
Institute for Advanced Study

May 24, 2004Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field

Sean Hallgren
NEC Research

May 10, 2004Quantum Algorithms and the Fourier Transform (Dissertation Talk)

Lawrence Ip
UC Berkeley

May 7, 2004Approximation via Cost Sharing

Tim Roughgarden
UC Berkeley

April 26, 2004Limits on Efficient Computation in the Physical World

Scott Aaronson
UC Berkeley

April 19, 2004Quantization of walk based classical algorithms and a new spectral theorem

Mario Szegedy
Rutgers University

April 2, 2004Convex Tree Colorings

Sagi Snir
Technion- Israel Institute of Technology

March 22, 2004Derandomized "low-degree" tests via "epsilon-biased" sets, with Applications to short Locally Testable Codes and PCPs

Avi Wigderson
IAS Princeton

March 15, 2004Approximating metrics by simpler metrics: Why and how?

Kunal Talwar
UC Berkeley

March 8, 2004Learning Mixtures of Product Distributions

Ryan O'Donnell
Institute for Advanced Study

March 1, 2004Finding nearby copies of objects in peer-to-peer networks
(Dissertation talk)

Kris Hildrum
UC Berkeley

February 23, 2004 BTE encryption: construction and applications

Shai Halevi
IBM

February 9, 2004 Quasi-Ramanujan 2-lifts and a converse to the Expander Mixing Lemma

Yonatan Bilu
Hebrew University

February 2, 2004Fast Monte Carlo Algorithms for Massive Data Sets and Approximating Max-Cut

Michael W. Mahoney
Yale

January 26, 2004 Mixing in Time and Space for Discrete Spin Systems
(Dissertation Talk)

Dror Weitz
UC Berkeley

2003

December 15, 2003Tight Bounds for Approximate Nearest Neighbour Search

Amit Chakrabarti
Dartmouth College

December 1, 2003Convergence Time to Nash Equilibria in Load Balancing Systems

Yishay Mansour
Tel-Aviv University

November 24, 2003Adiabatic Computation: Quantum Computation for the Classical Computer Scientist

Dorit Aharonov
Hebrew University and UC Berkeley

November 17, 2003Incidences and Related Problems

Micha Sharir
Tel Aviv University and MSRI

September 29, 2003Markov Chains for Randomly Coloring Graphs

Tom Hayes
Toyota Technological Institute at Chicago

September 22, 2003Towards an Algorithmic Theory of Self-Assembly

Ashish Goel
Stanford University

September 8, 2003New Exhaustive, Heuristic, and Interactive Approaches for 2-Dimensional Bin Packing

Michael Mitzenmacher
Harvard University

May 19, 2003On Determinant-Based Algorithms For Counting Matchings in Graphs

Steve Chien
UC Berkeley

May 12, 2003Algorithms for Planar Graphs
Dissertation Talk

Jittat Fakcharoenphol
UC Berkeley

May 5, 2003Derandomizing Polynomial Identity Tests means Proving Circuit Lower Bounds

Valentine Kabanets
UC San Diego

April 21, 2003Anisotropic Voronoi Diagrams and Guaranteed-Quality Anisotropic Mesh Generation

Francois Labelle
UC Berkeley

April 14, 2003Constrained Delaunay Tetrahedralizatios, Bistellar Flips, and Provably Good Boundary Recovery

Jonathan Shewchuk
UC Berkeley

March 17, 2003Putting the Combinatorics in Combinatorial Game Theory

David Wolfe
Gustavus Adolphus College

March 10, 2003On the Power of Quantum Proofs

Amir Shpilka
Harvard/MIT

March 3, 2003Sampling Lower Bounds via Information Theory

Ziv Bar-Yossef
IBM

February 10, 2003 Analysis of Boolean Functions and (a small sample of) its Applications

Muli Safra
Tel Aviv University

2002

November 25: A theory of complexity for continuous time systems

Asa Ben-Hur
Dept. of Biochemistry, Stanford

November 12: Tuesday, due to Veteran's day holiday. Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers

Michael Langberg
Weizmann Institute

October 28: Evolving sets and mixing

Ben Morris
UC Berkeley

October 21: What's up with random k-SAT?

Dimitris Achlioptas
Microsoft Research

October 14: The Minimum Generalized Vertex Cover Problem

Asaf Levin
Tel Aviv University

October 7: How Intractable is the ``Invisible Hand'': Polynomial Time Algorithms for Market Equilibria

Vijay Vazirani
Georgia Tech

October 1:
(Hughes Room , 2:00-3:30 p.m) with Networking, Communications and DSP Seminar

Adaptive TCP Flow Control

Alex Kesselman
Tel Aviv University

September 30: Reconstruction from Subsequences

Leonard Schulman
Caltech

September 9: Mixing in Time and Space on the Integer Lattice: A Combinatorial View

Dror Weitz
UC Berkeley

May 13: An information statistics approach to data stream and communication complexity

T.S. Jayram
IBM Almaden

May 6: The Complexity of Massive Data Set Computations

Ziv Bar-Yossef
UC Berkeley Dissertation Talk

April 29 (MacKay Lecture): Dynamics of TCP/AQM and a Scalable Control

Steven Low
CS & EE, Caltech

April 22: Competitiveness via Consensus

Andrew V. Goldberg
Microsoft Research--Silicon Valley

April 15 (MacKay Lecture): The Primal-Dual Schema and its Applications to Cooperative Games:
Global Optimality via Local Improvements

Vijay V. Vazirani
College of Computing at Georgia Tech

April 8 (MacKay Lecture): 310 Soda Hall Probability Theory, Information Theory and Covering Problems

Nicholas Pippenger
University of British Columbia

March 11: New Results in Free-space Quantum Cryptography

Richard Hughes
Los Alamos National Laboratory

February 25: A Reduction of dimensionality in the Euclidean Space that Preserves Volumes, and Applications

Avner Magen
NEC Research, Princeton

Wednesday January 16:
2pm in 373 Soda Frugal Path Mechanisms

Aaron Archer
Cornell University

January 14:
In 373 Soda Hall A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set

Guy Kortsarz
Rutgers University

January 10:
In 373 Soda Hall
2-3pm Asymmetric Maximum Travelling Salesperson

Moshe Lewenstein
IBM Research

2001

December 10
In 320 Soda Hall A Practical Shortest Path Algorithm with Linear Expected Time

Andrew V. Goldberg

December 3 Equitable, Group Strategyproof Cost Allocations via Primal-Dual-Type Algorithms

Kamal Jain
Microsoft Research

October 8 Coloring k-colorable Graphs Using Smaller Palettes

Eran Halperin
ICSI and UC Berkeley

September 10: On Approximating Optimal Auctions

Amir Ronen
Stanford & UC Berkeley

April 30: On-line Learning of Non-Stationary Data

Manfred Warmuth
UC Santa Cruz

April 23: Compressed Bloom Filters and Compressing the Web Graph

Michael Mitzenmacher
Harvard University

Tuesday, March 20, 4:30pm in 306 Soda
Spectral Analysis for Data Mining

Anna Karlin
University of Washington

February 5, 2001: Serving Billions of Pages to Hundreds of Millions of People is Harder Than It Seems

Udi Manber
Yahoo! Inc.

January 29: An application of complex semidefinite programming to approximation algorithms

David P. Williamson
IBM Almaden

2000

December 11: Approximating the Permanent

Alistair Sinclair
UC Berkeley

November 27: Hill-Climbing is as Good as Metropolis for Planted Bisection Problems

Russell Impagliazzo
UC San Diego

Friday November 17: Normal Subgroup Reconstruction and Quantum Computation Using Group Representations

Sean Hallgren
UC Berkeley

Tuesday November 7: Extracting Randomness via Repeated Condensing

Ronen Shaltiel
Institute for Advanced Study

November 6: Dissertation Talk
The Origins of the Deadline: Optimizing Communication in Organizations.

Edouard Servan-Schreiber
UC Berkeley

October 30: Joint Theory-Quantum Seminar
1:30pm in 310 Soda
Fast parallel algorithms for the quantum Fourier transform

Richard Cleve

Theory Seminar
3:00pm in 380 Soda
Quantum Interactive Proofs

Alexei Kitaev
Microsoft

October 23, 2000: Solving Low Degree Polynomials

Don Coppersmith
IBM Research and MSRI

October 16, 2000: Concurrent Reachability Games and Beyond

Luca de Alfaro
UC Berkeley

October 9, 2000
Note special time and location!
3:40 - 5:00 PM, 3108 Etcheverry Hall
Refreshments 3:00 - 3:40 PM, 4th Floor Hallway (north wing) Etcheverry Hall

Two applications of Lagrangean relaxation to approximation algorithms

Dr. David P. Williamson
IBM Almaden

Sep 11, 2000: Dissertation Talk
Approximability and Completeness in the Polynomial Hierarchy.

Chris Umans
UC Berkeley

Aug 21, 2000: Dissertation Talk
Embeddings of Finite Metrics

Anupam Gupta
UC Berkeley

Aug 17, 2000: Quantum Communication Complexity

Gilles Brassard
Universite de Montreal,

May 25, 2000: Approximation algorithms for the 0-Extension Problem

Yuval Rabani
Technion

May 15, 2000: Approximation algorithms for minimum bisection

Robert Krauthgamer
Weizmann Institute

Wednesday Apr 26, 2000: (also April 28, May 1 and 3). New Directions for Random Walks
(a series of four independent talks)

Peter Winkler
Bell Labs

Apr 10, 2000: (also April 12 & 14). Tarski Lectures: Complexity of proofs and computations

Alexander Razborov
Steklov Mathematical Institute

Mar 20, 2000: Bipartite entanglement: majorization and positive maps

Barbara Terhal
IBM T.J. Watson

Mar 15, 2000: (Wozniak Lounge, 11am) Extractors and their applications

David Zuckerman
UT Austin/UC Berkeley

Mar 13, 2000: Explicit Time-Space Tradeoff Lower Bounds

Paul Beame
University of Washington

Mar 6, 2000: A Study of Statistical Zero-Knowledge Proofs

Salil Vadhan
MIT

Feb 28, 2000: Stochastic Load Balancing and Related Problems

Ashish Goel
University of Southern California

Feb 14, 2000: Dissertation Talk
Lower bounds for quantum communication and computation

Ashwin Nayak
UC Berkeley

Feb 7, 2000: MSRI-Soda Lecture
Fourier transforms, quantum algorithms and complexity

Umesh Vazirani
UC Berkeley

Jan 24, 2000: An Optimal Algorithm for Hyperplane Depth in the Plane

Stefan Langerman
Rutgers University

January 13, 2000 (Thursday): Two-dimensional Gantt charts and a scheduling algorithm of Lawler

David P. Williamson
IBM Watson

January 12, 2000 (Wednesday after the theory lunch, Wozniak Lounge): Approximation algorithms for the vertex cover problem in graphs and hypergraphs

Eran Halperin
Tel Aviv University

1999

Dec 6, 1999: Balanced Allocations: The Heavily Loaded Case

Berthold Voecking
ICSI

Nov 29, 1999: Direct Gradient-Based Reinforcement Learning

Jonathan Baxter
Australian National University

Nov 22, 1999: Competitive Auctions and Digital Goods

Andrew Goldberg
Intertrust

Nov 8, 1999: Towards an Algorithmic Version of the General Lovasz Local Lemma

Artur Czumaj
University of Paderborn

Nov 1, 1999: Ph.D. Dissertation talk
Sampling from Gibbs distributions

Eric Vigoda
UC Berkeley

Oct 25, 1999: Privacy Preserving Auctions and Mechanism Design

Moni Naor
Weizmann Institute

October 11, 1999: All Pairs Shortest Paths in Undirected Graphs

Uri Zwick
Tel Aviv University

October 4, 1999: Approximation Algorithms for Scheduling via Linear Programming and Randomization

David Shmoys
Cornell (visiting UC Berkeley)

September 27, 1999: Classification with Pairwise Relationships: Metric Labeling and Markov Random Fields.

Eva Tardos
Cornell (visiting UC Berkeley)

September 20, 1999: Cuts, Trees and L1-embeddings

Anupam Gupta
UC Berkeley

September 13, 1999:

David Shmoys' talk has been postponed to October 4th.
Sridhar Rajagopalan's talk will be a joint Theory-Digital Libraries talk.

September 10, 1999: (Friday, 10am - 11am) Towards an Optimal Bit-Reversal Permutation Program

Larry Carter
UCSD CS Dept

August 23, 1999: Statistical Zero-Knowledge: An Introduction
and a Survey of Recent Developments

Amit Sahai
MIT

August 20, 1999: (Friday, 11am - noon) The all-or-nothing nature of Secure Computation

Silvio Micali
MIT

May 27, 1999: (Thursday) Computer Science in the Early Universe

Michael Freedman
Microsoft Research

May 17, 1999: Learning Mixtures of Gaussians

Sanjoy Dasgupta
UC Berkeley

May 12, 1999: (Soda 380, 12:30pm -- after theory lunch) Algorithmic Mechanism Design

Amir Ronen
Hewbrew University

May 11, 1999: (Tuesday, 380 Soda) Self-Testing Quantum Source

Andrew Yao
Princeton and UC Berkeley

May 10, 1999: Randomized Motion Planning: Algorithms and Applications

Nancy Amato
Texas A&M

April 26, 1999: Short Proofs are Narrow - Resolution made simple

Eli Ben-Sasson
Hebrew University

April 19, 1999: Dynamic Graph Algorithms: An Overview

Valerie King
U Victoria/UC Berkeley

April 14, 1999: 1011 Evans, 4-5pm Neyman Statistics Seminar
Transfer Principles for Complexity Theory

Lenore Blum
ICSI

April 12, 1999: (Note change in speaker) Quantum Fourier Sampling Simplified

Sean Hallgren
UC Berkeley

April 5, 1999: Collective Sampling and Leader Election
in the Perfect Information Model

David Zuckerman
UT Austin/UC Berkeley

March 29, 1999: Trawling the web for cyber-communities: the Campfire project

Sridhar Rajagopalan
IBM Research

March 29, 1999: (2 - 3:30pm, Wozniak Lounge) The complexity of lattice and coding problems
and their cryptographic applications

Daniele Micciancio
MIT
Faculty Candidate

March 15, 1999: Clustering for Edge-Cost Minimization

Leonard Schulman
Georgia Tech.

March 8, 1999: Pseudo-Random Functions, Permutations

Omer Reingold
Weizmann Institute

March 3, 1999: A Method for Experimentally Exploring Search Spaces:
The Case of Graphs with Small Planted Bisections

Russell Impagliazzo
UC San Diego

March 1, 1999: List decoding of polynomial codes

Madhu Sudan
MIT

February 22, 1999: On Realizing Random Oracles

Ran Canetti
IBM Research

February 8, 1999: Highly Efficient PCPs for Optimization Problems

Ronitt Rubinfeld
Cornell University

January 25, 1999: Games of No Chance

Elwyn Berlekamp
UC Berkeley

Tuesday, January 19, 1999, Soda 380: Task Assignment in a Distributed Server

Mor Harchol-Balter
MIT

1998

November 23, 1998: Algorithmic theories of learning

Santosh Vempala
MIT

November 16, 1998: All Pairs Shortest Paths
using Bridging Sets and Rectangular Matrix Multiplications

Uri Zwick
Tel Aviv University

November 12, 1998: 2:30 - 3:30pm, 380 Soda On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem

Vijay Vazirani
Georgia Tech

November 12, 1998: 373 Soda Joint AI/Theory Seminar
Sparse Sampling Methods for Learning and Planning

Michael Kearns
AT&T Labs

November 6, 1998: 1:00 - 2:30pm, 306 Soda How Secure are Digital Safes?

Rafail Ostrovsky
Bellcore

November 2, 1998: Ph.D. Dissertation Talk
Using Hamilton's quaternions to approximate the permanent.

Lars Rasmussen
UC Berkeley

October 26, 1998: The Complexity of DNF Minimization and Related Problems

Chris Umans
UC Berkeley

October 19, 1998: On List Update and Work Function Algorithms

Anna Karlin
University of Washington

October 12, 1998: Min-Wise Independent Permutations

Moses Charikar
Stanford University

September 21, 1998: Randomness vs. Time:
De-randomization under a uniform assumption

Avi Wigderson
Hebrew University

August 31, 1998: A Sublinear Bipartite Tester for Bounded-Degree Graphs

Dana Ron
MIT

August 31, 1998 (Room 380, 11am-12pm)

Pseudo-Random Functions and their Relaxation

Omer Reingold
Weizmann Institute of Science

April 20: Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality

Piotr Indyk
Stanford University

Wednesday, March 18 in Soda 380: Team-Maxmin Equilibria

Bernhard von Stengel
ETH Zurich

March 16 in Soda 373 Random walks on groups: recent developments and applications

Igor Pak
Yale University

March 2: Approximating a finite metric by O(n \log n) trees

Chandra Chekuri
Stanford University

February 23: The Ramsey number R(3,t) has asymptotic order of magnitude t^2 / \log t

Jeong Han Kim
Microsoft Research

Tuesday, February 17 in Soda 380: Fractional K-Medians by Randomized Rounding

Neal Young
Dartmouth College

Tuesday, February 10, 4-5 PM in 405 Soda Hall : A New proof of Hastad's Tight Bounds

Guy Kindler
Tel Aviv University.

February 9 in Soda 373 : The Closest Vector Problem is Hard to Approximate

Irit Dinur
Tel Aviv University.

Thursday, January 29 in 373 Soda Hall: Undirected Single Source Shortest Paths in Linear Time

Mikkel Thorup
University of Copenhagen

Wednesday, January 28 in 373 Soda Hall: Towards the k-Colorability Threshold

Dimitris Achlioptas
University of Toronto

1997

December 8: Maximizing Throughput of Reliable Bulk Network Transmission

PhD Dissertation Talk
John Byers
U.C. Berkeley

December 1: Satisfiability Coding Lemma

Mohan Paturi
U.C. San Diego

November 3 Self-Correcting Programs and Error Correcting Codes

PhD Dissertation Talk

Hal Wasserman
U.C. Berkeley

October 27: Nearly-Optimal PCP Characterization of NP

Muli Safra
Tel-Aviv University

Tuesday, October 14: Random Projection. A Tool for Algorithms

Santosh Vempala
MIT

October 6 Spatial Codes and the Hardness of String Folding

Ashwin Nayak
U.C. Berkeley

September 29 Pebbles, Programming and Parallelism

Guy Blelloch
Carnegie Mellon University, visiting UC Berkeley

September 15 How Useful is Old Information?

Michael Mitzenmacher
Digital Systems Research Center

August 25, 1997 Chaotic Evolution via Generalized Probabilistic Automata (Probabilistic Arrays)

Azaria Paz
Technion

Tuesday, April 15 (3-4 PM) How to Hide Geometric Structure in Flat Files

Jack Snoeyink
University of British Columbia

April 14 Designing Geometric Algorithms: How and Why

Bernard Chazelle
Princeton University

April 7 Ramsey's Theorem and Enormous Lower Bounds

Harvey Friedman
Ohio State University

Tuesday, April 1 Secure Database Access

Rafail Ostrovsky
Bellcore

March 31 Reducing the Complexity of Reductions

Steven Rudich
Carnegie Mellon University

March 17 Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems

Sanjeev Arora
Princeton University

March 10 Learning Noisy Perceptrons by a Perceptron in Polynomial Time

Edith Cohen
UC Berkeley and AT&T Labs-Research

March 3 Beautiful and Fast: New Minimum Cut Algorithms

Andrew Goldberg
NEC Research Institute, Inc.

Friday, February 28 PhD Dissertation Talk

Ethan Bernstein
UC Berkeley

February 10 Nearest Neighbor Search in High Dimensions

Jon Kleinberg
IBM Almaden and Cornell University

February 3, 1997 The Topology and Geometry of Two-Dimensional Wiring Patterns

F. Miller Maley
MSRI

January 27, 1997 Practical Loss-Resilient Codes

Michael Mitzenmacher
Digital Systems Research Center

1996

December 16 Limited Bandwidth Parallel Computation

Micah Adler
UC Berkeley

December 9 A New Approximation Algorithm for Finding Heavy Planar Subgraphs

Howard Karloff
Georgia Tech, visiting UC Berkeley

December 2 Meshing, Morphing and Mapping

Marshall Bern
Xerox PARC

November 25 Drug Design, Kinematic Data Structures, and Dynamic Servers

Rajeev Motwani
Stanford University

November 4 Fast and Precise Computation of Fast Fourier Transforms Using Cyclotomic Integers

Amin Shokrollahi
ICSI

October 28: Approximating Total Flow Time on Parallel Machines

Danny Raz
ICSI & UC Berkeley

October 21: Factoring Polynomials over Finite Fields

Joachim von zur Gathen
U. Paderborn, visiting ICSI

October 7: New Bounds for Computing Vertex Connectivity

Monika R. Henzinger
Digital Systems Research Center &
Cornell University

September 30: Private Information Retrieval

Benny Chor
Technion

September 16: Survey talk on Distributed Paging

Yair Bartal
ICSI & UC Berkeley

September 9: All Pairs Almost Shortest Paths

Uri Zwick
ICSI & UC Berkeley
-- 306 Soda Hall --

September 5: On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited

Moni Naor
Weizmann Institute

May 30th: Polynomial-time Approximation Schemes for Euclidean TSP
and other Geometric Problems

Sanjeev Arora
Princeton University

May 13th: Approximation Algorithms for Facility Location Problems

Samir Khuller
University of Maryland

May 6th: Optimal Fault-Tolerant Sorting Networks

Yuan Ma
Stanford University

April 15th: Designing Schedules that Minimize Average Completion Time

Cliff Stein
Department of Computer Science
Dartmouth College

April 22nd: Probabilistic Approximations of Metric Spaces
and its Algorithmic Applications

Yair Bartal
ICSI

April 29th: Spectral Partitioning Works:
Planar graphs and finite element meshes

Dan Spielman
UC Berkeley

April 8th: Negative Cycle Detection Algorithms

Andrew Goldberg
NEC

April 1st: Brute force counting

John Mount
MSRI

March 4th: Towards an analysis of local optimization algorithms

Anastasios Dimitriou
UC San Diego

February 26th: Approximation algorithms for semidefinite programs arising from MAX CUT and COLORING

Phil Klein
Brown University

February 12th: Cluster algorithms for critical points in statistical physics

Jon Machta
Amherst

January 22nd: Perfect Matchings in Balanced hypergraphs

Ajai Kapoor
CMU

January 19th: Read-Write Protocols with Scheduling Constraints

Eli Gafni
UC Los Angeles

1995

December 4th, 1995: Linear-Time Encodable and Decodable Error-Correcting Codes

Dan Spielman
UC Berkeley

November 27th: Steady State Analysis of Computer Processes

Eli Upfal
IBM & Weizmann Institute

November 20th: Linear Time Erasure Codes With Nearly Optimal Recovery

Mike Luby
ICSI and UC Berkeley

November 13th: An Overview of Electronic Cash Including Trustee-based Electronic Cash

Pete Gemmell
Sandia Labs

October 30th: Vector Partition Functions

Bernd Sturmfels
Mathematics, UC Berkeley

October 16th: Applications of Rabin's fingerprinting

Andrei Broder
Digital SRC, Palo Alto, CA

October 9th: A Better Approximation Algorithm for Finding Planar Subgraphs

Howard Karloff
Georgia Tech

October 2nd: On The Hardness of Approximation Problems

Muli Safra
Tel-Aviv University

September 25: New Approximation Algorithms for the Steiner Tree Problems

Marek Karpinski and Alexander Zelikovsky
Department of Computer Science, University of Bonn

September 20th: On the geometry of graphs & its algorithmic applications (I)

Nathan Linial
Hebrew University, Jerusalem

September 18th: Logarithmic Approximation of Minimum Weight $k$ Trees

Sridhar Rajagopalan
DIMACS and Princeton

September 13th: On the geometry of graphs & its algorithmic applications (I)

Nathan Linial
Hebrew University, Jerusalem

September 11th: Splitters and near-optimal derandomization

Leonard J. Schulman
Georgia Tech

August 28th: Approximation Algorithms for the Feedback Set Problem

Seffi Naor
Technion, Israel