| Date and Time | Speaker | Title | Room |
| Jan 11, 10:50am-noon |
Kevin Compton | Intro | CSE 3941 |
| Jan 18, 10:50am-noon |
Seth Pettie | Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture | CSE 3941 |
| Jan 25, 10:50am-noon |
Zhang Zhiqiang | The Sign-Rank of AC0, A. Razborov and A. Sherstov | CSE 3941 |
| Feb 1, 11:00am-noon |
Bei Zeng MIT |
Codeword Stabilized Quantum Codes. Abstract | DOW 1018 |
| Feb 8, 10:50am-noon |
Quentin Stout | Power, Time, and Location: Parallel algorithms addressing them all | CSE 3941 |
| Feb 15, 10:50am-noon |
Brian Wyman | This talk will be a sampling of recent results on locally decodable codes D. Woodruff, New Lower Bounds for General Locally Decodable Codes P. Raghavendra, A Note on Yekhanin's Locally Decodable Codes K. Kedlaya, S. Yekhanin, Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers |
CSE 3941 |
| Feb 22, 10:50am-noon |
Zhang Zhiqiang | A. Sherstov:
The Pattern Matrix Method for Lower Bounds on Quantum Communication and Y. Shi, Y. Zhu: The quantum communication complexity of block-composed functions |
CSE 3941 |
| Feb 29 | Spring Break | ||
| Mar 7 | Department Open House | ||
| Mar 14, 10:50am-noon |
Ye Du | Leontief Economies Encode Nonzero Sum Two-Player Games | CSE 2725 |
| Mar 21, 10:50am-noon |
Runyao Duan Tsinghua University |
Zero-error classical capacity of noisy quantum channels Abstract | DOW 1017 |
| Mar 28, 11:15am(sharp!)-12:10 |
Piotr Indyk MIT |
Sparse Recovery Using Sparse Random Matrices Abstract |
DOW 1017 |
| Apr 4, 10:50am-noon |
Alexander Sherstov The University of Texas at Austin |
The Unbounded-Error Communication Complexity of Symmetric Functions Abstract | DOW 1017 |
| Apr 11, 10:50am-noon |
- | tba | CSE 3941 |
| Date and Time | Speaker | Title | Room |
| Sept 7, 11am-noon |
Martin Strauss | One Sketch For All | CSE 3941 |
| Sept 14, 10:50am-noon |
Erin Rhode |
Compressed Bloom Filters (M. Mitzenmacher) and Distance-sensitive Bloom Filters (A. Kirsch and M. Mitzenmacher) |
CSE 3941 |
| Sept 21, 10:50am-noon |
CSE 3941 | ||
| Sept 28, 10:50am-noon |
Michael Wakin University of Michigan |
The Geometry of Compressed Sensing | CSE 3941 |
| Oct 5, 10:50am-noon |
Xuan Zheng | Piotr Indyk,Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1 | CSE 3941 |
| Oct 12, 10:50am-noon |
Andrew McGregor University of California, San Diego |
The Order of the Data Stream Abstract |
CSE 3941 |
| Oct 19, 10:50am-noon |
Anupam Gupta Carnegie Mellon University |
Max-Min Facility Location and Set Coverage Problems Abstract |
CSE 3941 |
| Oct 26, 10:50am-noon |
Eric Torng, Michigan State |
TCAM Razor and the Problem of Minimizing TCAM Packet Classifiers | CSE 3941 |
| Nov 2, 10:50am-noon |
Dungjade Shiowattana | Lossy Trapdoor Functions and Their Applications | CSE 3941 |
| Nov 9, 10:50am-noon |
Brian Wyman | Fast Sorting and Pattern-Avoiding Permutations David Arthur |
CSE 3941 |
| Nov 16, 10:50am-noon |
SODA'08 practice talks: Mark Iwen: A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods Ran Duan: Bounded Leg Distance and Reachability Oracles |
CSE 3941 | |
| Nov 23 | Thanksgiving | ||
| Nov 30, 10:50am-noon |
Runyao Duan Tsinghua University |
On the Perfect Distinguishability of Unitary Operations | CSE 3941 |
| Dec 7, 10:50am-noon |
Wei Huang | tba | CSE 3941 |
| Date and Time | Speaker | Title | Room |
| Jan 11, 4:30-5:30 |
Seth Pettie | Organizational meeting | CSE 3941 |
| Jan 18, 4:30-5:30 |
Everyone | 5-minute intro talks | CSE 3941 |
| Jan 25 (Thursday) |
Lance Fortnow University of Chicago |
The Complexity of Forecast Testing Abstract and Short Bio |
CSE 3725 |
| Feb 1 4:30-5:30 |
CSE 3941 | ||
| Feb 8, 4:30-5:30 |
Jon Brown | Boltzmann Sampling of Unlabelled Structures, Flajolet et al. | CSE 3941 |
| Feb 15, 4:30-5:30 |
Brian Wyman | New Locally Decodable Codes and Private Information Retrieval Schemes | CSE 3941 |
| Feb 22, 4:30-5:30 |
Dungjade Shiowattana | Aggregation of Partial Rankings, p-Ratings and Top-m Lists | CSE 3941 |
| Mar 1 |
Winter Break | ||
| Mar 8, 4:30-5:30 |
Wei Huang | Tensor rank and the ill-posedness of the best low-rank approximation problem | CSE 3941 |
| Mar 15, 4:30-5:30 |
Xuan Zheng | Private Approximation of Search Problems | CSE 3941 |
| Mar 22, 4:30-5:30 |
Ye Du | Computing Nash Equilibrium and Approximate Nash Equilibrium in Bimatrix Game | CSE 3941 |
| Mar 29, 4:30-5:30 |
Yufan Zhu | An information statistics approach to data stream and communication complexity | CSE 3941 |
| Apr 5, 4:30-5:30 |
CSE 3941 | ||
| Apr 12, 4:30-5:30 |
CSE 3941 | ||
| Apr 19, 4:30-5:30 |
Quentin Stout | Multi-million dollar binary search trees | CSE 3941 |
| Date and Time | Speaker | Title | Room |
| Sept 28, 4:30-5:30 | Seth Pettie | An Optimal Binary
Search
Tree? Demaine et al. paper | CSE 3941 |
| Oct 5, 4:30-5:30 | Julia Lipman | Publish and Perish | CSE 3941 |
| Oct 12, 4:30-5:30 | Ye Du | A Global Geometric Framework for
Nonlinear Dimensionality Reduction and Nonlinear Dimensionality Reduction by Locally Linear Embedding(Tenenbaum, de Silva, Langford and Roweis, Saul) |
CSE 3941 |
| Oct 19, 4:30-5:30 | Joel Lepak | Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces | CSE 3941 |
| Oct 26, 4:30-5:30 | Wei Huang |
Quantum Computation as Geometry
and A geometric approach to quantum circuit lower bounds |
CSE 3941 |
| Oct 27 (Friday) 2:00-3:00 |
Wim van Dam, âUC Santa Barbara |
Recent results in the search for new quantum algorithms
Abstract and Short Bio |
EECS 2311 |
| Nov 2, 4:30-5:30 | Yufan Zhu | Ranking Systems: The PageRank Axioms | CSE 3941 |
| Nov 9, 4:30-5:30 | Duan Ran | Evolvability | CSE 3941 |
| Nov 16, 4:30-5:30 | Xuan Zheng | Practical Privacy: The SuLQ Framework | CSE 3941 |
| Nov 23, 4:30-5:30 | Thanksgiving Break | ||
| Nov 30, 4:30-5:30 | Shengyu Zhang Caltech |
Zero-Knowledge Proof Systems Secure
against Quantum Attacks
Abstract and Short Bio |
CSE 3941 |
| Dec 7 | |||
| Dec 14, 4:30-5:30 | Xiaolin Shi | Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations | CSE 3941 |