Seminars in 2008
| 1 | Title: Matrix Rank, Rigidity and Complexity | |
| Speaker: Jayalal Sarma M.N, The Institute of Mathematical Sciences, Chennai, India | ||
| Time: 11:00-12:00, March 5, 2008 (Wednesday) |
| 2 | Title: Dense Subsets of Pseudorandom Sets | |
| Speaker: Luca Trevisan, University of California, Berkeley | ||
| Time: 14:00-15:00, March 24, 2008 (Monday) |
| 3 | Title: Lower Bounds for Approximating Vertex Cover in the Lovasz and Schrijver Hierarchy | |
| Speaker: Luca Trevisan, University of California, Berkeley | ||
| Time: 15:30-16:30, March 26, 2008 (Wednesday) |
| 4 | Title: Data: Making it be there when you want it and go away when you want it gone | ||
| Speaker: Radia Perlman, Sun Fellow, Sun Microsystems Inc. | |||
| Time: 11:00 am - 12:00 am, April 1, 2008 (Tuesday) |
| 5 | Title: Routing in large networks despite Byzantine failures | ||
| Speaker: Radia Perlman, Sun Fellow, Sun Microsystems Inc. | |||
| Time: 11:00 am - 12:00 am, April 3, 2008 (Thursday) |
| 6 | Title: Multiple-Input-Multiple-Output Detection using Semidefinite Relaxation | ||
| Speaker: Wing-Kin Ma, Ken, Department of Electronic Engineering, The Chinese University of Hong Kong | |||
| Time: 4:00 pm - 5:00 pm, April 14, 2008 (Monday) |
| 7 | Title: Lattice Problems and Norm Embeddings | |
| Speaker: Ricky Rosen, Tel Aviv University | ||
| Time: 16:30-17:30, April 16, 2008 (Wednesday) |
| 8 | Title: Input-indistinguishable Computation | |
| Speaker: Alon Rosen, Herzliya Interdisciplinary Center, Israel | ||
| Time: 15:30-16:30, April 16, 2008 (Wednesday) |
| 9 | Title: Content Pipe Divide and Network Distribution Capacity | ||
| Speaker: Mung Chiang, Electrical Engineering Department, Princeton University | |||
| Time: 11:00 am - 12:00 am, April 21, 2008 (Monday) |
| 10 | Title: The communication complexity of correlation | |
| Speaker: Jaikumar Radhakrishnan, Tata Institute of Fundamental Research, India | ||
| Time: 15:30-16:30, April 23, 2008 (Wednesday) |
| 11 | Title: Quantum walk based search algorithms | |
| Speaker: Miklos Santha, Universite Paris Sud, Laboratoire de Recherche en Informatique, France | ||
| Time: 16:30-17:30, April 23, 2008 (Wednesday) |
| 12 | Title: Expander graphs - a survey | |
| Speaker: Eyal Rozenman, California Institute of Technology | ||
| Time: 11:00-12:00, April 25, 2008 (Friday) |
| 13 | Title: Making classical zero knowledge protocols secure against quantum attacks | |
| Speaker: Pranab Sen, Tata Institute of Fundamental Research, India | ||
| Time: 15:30-16:30, May 7, 2008 (Wednesday) |
| 14 | Title: “Rules of Work” and My Insights | |
| Speaker: Peter Yum, Chinese University of Hong Kong | ||
| Time: 16:30-17:00, May 7, 2008 (Wednesday) |
| 15 | Title: Information Checking Protocol and Verifiable Secret Sharing | |
| Speaker: Pandu Rangan Chandrasekaran, Indian Institute of Technology | ||
| Time: 14:00-15:00, May 12, 2008 (Monday) |
| 16 | Title: Perfect Secure Message Transmission | |
| Speaker: Pandu Rangan Chandrasekaran, Indian Institute of Technology | ||
| Time: 15:00-17:00, May 13, 2008 (Tuesday) |
| 17 | Title: Protocols for Reliable/Secure Message Transmission tolerating Mixed and Mobile Adversary | |
| Speaker: Pandu Rangan Chandrasekaran, Indian Institute of Technology | ||
| Time: 15:30-16:30, May 14, 2008 (Wednesday) |
| 18 | Title: Private Branching Programs: On Communication-Efficient Cryptocomputing | |
| Speaker: Helger Lipmaa, University College London | ||
| Time: 13:30-14:30, May 21, 2008 (Wednesday) |
| 19 | Title: Optimal Cryptographic Hardness of Learning Monotone Functions | |
| Speaker: Andrew Wan, Columbia University | ||
| Time: 15:00-16:00, May 28, 2008 (Wednesday) |
| 20 | Title: Double Base Number System and Elliptic Curve Cryptography | |
| Speaker: Christophe Doche, Macquarie University | ||
| Time: 16:00-17:00, May 28, 2008 (Wednesday) |
| 21 | Title: ID-based Cryptography | |
| Speaker: Yi Mu, University of Wollongong, Australia | ||
| Time: 15:00-16:00, June 11, 2008 (Wednesday) |
| 22 | Title: Cryptographic Hashing at the Crossroads | |
| Speaker: Josef Pieprzyk, Macquarie University, Australia | ||
| Time: 16:00-17:00, June 11, 2008 (Wednesday) |
| 23 | Title: Efficient Algorithms for Agnostic Learning | |
| Speaker: Adam Klivans, University of Texas | ||
| Time: 14:20-15:20, June 12, 2008 (Thursday) |
| 24 | Title: Nash Bargaining via Flexible Budget Markets | |
| Speaker: Vijay Vazirani, Georgia Institute of Technology, USA | ||
| Time: 10:30-11:30, June 20, 2008 (Friday) |
| 25 | Title: The Smoothed Complexity of Integer Optimization Problems | |
| Speaker: Heiko Roeglin, Microsoft Research Asia | ||
| Time: 14:00-15:00, June 25, 2008 (Wednesday) |
| 26 | Title: Secure Internet Path Quality Monitoring: Tradeoffs in Security and Efficiency | |
| Speaker: David Xiao, Princeton University | ||
| Time: 15:00-16:00, June 25, 2008 (Wednesday) |
| 27 | Title: Pairing Implementation and Its Application to Cryptography | |
| Speaker: Prof. Eiji Okamoto, The University of Tsukuba | ||
|
Time: 16:00-17:00, Friday, October 10, 2008 |
| 28 | Title: Sparse High-Distance Linear Codes are Locally Testable and Correctable | |
| Speaker:Prof. Madhu Sudan, MIT | ||
| Time: 17:00-18:00, Friday, October 10, 2008 |
| 29 | Title: Efficient algorithms for the 2-gathering problem | |
| Speaker: Prof. Uri Zwick, Tel Aviv University | ||
| Time: 13:30-14:30, Wednesday, October 22, 2008 |
| 30 | Title: Threshold Public-Key Cryptography | |
| Speaker: Prof. David Pointcheval | ||
| Time: 14:00-15:00, Wednesday, October 29, 2008 |
| 31 | Title: A theory of goals | |
| Speaker: Dr. Brendan Juba | ||
|
Time: 14:00-15:00, Wednesday, November 5, 2008 |
| 32 | Title: Threshold Public-Key Cryptography | |
| Speaker: Dr. Elad Verbin | ||
|
Time: 16:00-17:00, Thursday, November 6, 2008 |
| 33 | Title: Khintchine-Type Inequalities and Their Applications in Optimization | |
| Speaker: Prof. Anthony So, the Chinese University of Hong Kong | ||
|
Time: 14:00-15:00, Wednesday, November 19, 2008
|
Seminars in 2007
| 1 | Title: Hamiltonicity of Regular Graphs and Blocks of Consecutive Ones in Symmetric Matrices | |
| Speaker: Francis Lau, The University of Hong Kong | ||
| Time: 14:00-15:30, March 13, 2007 |
| 2 | Title: Post Quantum Signatures | |
| Speaker: Johannes buchmann, Technische Universität Darmstadt | ||
| Time: 14:00-15:30, March 14, 2007 |
| 3 | Title: All problems in statistical zero-knowledge have a classical protocol secure against both classical and quantum verifiers | |
| Speaker: Dr. Shengyu Zhang, California Institute of Technology | ||
| Time: 14:00-15:30, March 27, 2007 |
| 4 | Two zero-knowledge interactive proofs for problems in graph theory with applications in cryptography | |
| Speaker: Yvo Desmedt, Department of Computer Science Adastral Campus University College London | ||
| Time: 16:30-17:30, March 28, 2007 |
| 5 | Title: An Appropriate Design for Trusted Computingand Digital Rights Management | |
| Speaker: Clark Thomborson, The University of Auckland | ||
| Time: 14:00-15:30, March 29, 2007 |
| 6 | China Theory Day I | ||
| Title: On the Quantum Query Complexity of Local Search in Two and Three Dimensions | |||
| Speaker: Xiaoming Sun, Tsinghua University | |||
| Title: On the Computation and Approximation of Two-Player Nash Equilibria | |||
| Speaker: Xi Chen, Tsinghua University | |||
| Title: Holographic Algorithms: From Art to Science | |||
| Speaker: Pinyan Lu, Tsinghua University | |||
| Time: 14:00-17:00, April 11, 2007 | |||
| 7 | China Theory Day II | ||
| Title: Counting Homomorphisms to Directed Acyclic Graphs | |||
| Speaker: Mike Paterson, University of Warwick | |||
| Title: Quantum Information and the PCP Theorem | |||
| Speaker: Ran Raz, Weizmann Institute | |||
| Title: Parallel Repetition of the Odd Cycle Game | |||
| Speaker: Mario Szegedy, Rutgers University | |||
| Time: 14:00-17:00, April 12, 2007 | |||
| 8 | Title: co-B\"uchi Rankings and omega-Automata Transformations | |
| Speaker: Qiqi Yan, Shanghai Jiao Tong University | ||
| Time: 15:00-16:30, April 20, 2007 |
| 9 | Seminar 1 | ||
| Title: Chernoff-type Direct Product Theorems | |||
| Speaker: Valentine Kabanets, Simon Fraser University | |||
| Time: 14:00-15:00, May 15, 2007 | |||
| Seminar 2 | |||
| Title: Describing vs. proving: connecting bounded arithmetic and descriptive complexity | |||
| Speaker: Antonina Kolokolova, Simon Fraser University | |||
| Time: 15:00-16:00, May 15, 2007 | |||
| 10 | Title: Quantum communication complexity of block-composed functions | |
| Speaker: Yaoyun Shi, EECS, University of Michigan, Ann Arbor | ||
| Time: 13:30-15:00, May 29, 2007 |
| 11 | Title: Algorithm for wireless networks | |
| Speaker: PengJun Wan, Illinois Institute of Technology | ||
| Time: 9:00 - 10:30, May 30, 2007 | ||
| 16:00 - 18:00, June 1, 2007 | ||
| 10:00 - 12:00, June 4, 2007 | ||
| 14:00 - 17:00, June 6, 2007 | ||
|
14:00 - 17:00, June 8, 2007 |
||
| 14:00 - 17:00, June 11 (Monday) | ||
| 14:00 - 17:00, June 12 (Tuesday) | ||
| 14:00 - 17:00, June 13 (Wednesday) | ||
| 14:00 - 17:00, June 14 (Thursday) | ||
| 14:00 - 17:00, June 15 (Friday) | ||
| 14:00 - 17:00, June 18 (Monday) | ||
| 14:00 - 17:00, June 19 (Tuesday) | ||
| 14:00 - 17:00, June 21 (Thursday) | ||
| 14:00 - 17:00, June 22 (Friday) |
| 12 | Title: Structure from Proximity | |
| Speaker: Leonidas J. Guibas, Computer Science Department, Stanford University | ||
| Time: 14:00-15:30, May 31, 2007 |
| 13 | Title: Probabilistic Graphical Models --- theory, algorithm, and application | |
| Speaker: Eric Xing, Carnegie Mellon University | ||
| Time: 15:30-17:00, May 31, 2007 | ||
| 14:00- 15:30, June 1, 2007 | ||
| 14:00- 15:30, June 4, 2007 | ||
|
15:30- 17:00, June 7, 2007 |
| 14 | Title: Automatic Generation and Analysis of Attack Graphs | |
| Speaker: Jeannette M. Wing, Computer Science Department, Carnegie Mellon University | ||
| Time: 15:30 - 17:00, June 5,2007 |
| 15 | Title: Priority sampling to estimating arbitrary subset sums | |
| Speaker: Mikkel Thorup, AT&T Labs--Research, Shannon Laboratory | ||
| Time: 10:40-11:25, June 7, 2007 |
| 16 | Title: Optimal Bounds for Predecessor Search and the First Separation between Linear and Polynomial Space | |
| Speaker: Mikkel Thorup, AT&T Labs--Research, Shannon Laboratory | ||
| Time: 14:00-15:00, June 7, 2007 |
| 17 | Title: The guessing number | |
| Speaker: Taoyang Wu , Queen Mary, University of London | ||
| Time: 10:00-11:00, June 11, 2007 |
| 18 | Title: Graph states and their applications | |
| Speaker: Caterina-Eloisa Mora, University of Innsbruck | ||
| Time: 11:00-12:00, June 11, 2007 |
| 19 | Title: Grand Challenges in Proof Complexity | |
| Speaker: Alexander Razborov, Steklov Mathematical Institute, Russian Academy of Science, Russia | ||
| Time: 15:00-16:30, September 13, 2007 | ||
| Time: 13:00-14:30, September 14, 2007 |
| 20 | Title: Text-Compression using the Burrows-Wheeler Transform | |
| Speaker: Elad Verbin, ITCS, Tsinghua University | ||
| Time: 14:40-15:40, September 14, 2007 |
| 21 | Title: Some Old and New Unsolved CS Problems | |
| Speaker: Juris Hartmanis, Cornell University, USA | ||
| 1993 Turing Award Winner | ||
| Time:9:00-10:00, September 20, 2007 (Thursday) |
| 22 | Title: Stochastic Analysis of File Swarming Systems | |
| Speaker: John C.S. Lui, The Chinese University of Hong Kong | ||
| Time: 15:40 - 16:40, October 15, 2007 (Monday) |
| 23 | Title: Spectral Algorithms | |
| Speaker: Ravi Kannan, Microsoft Research Labs, India | ||
| Time: 10:00 - 11:00, October 19, 2007 (Friday) |
| 24 | Title: DNSSEC: From Cryptographic Design to Real Deployment | |
| Speaker: Lixia Zhang, Computer Science Department, UCLA | ||
| Time: 11:00 - 12:00, October 19, 2007 (Friday) |
| 25 | Title: Playing Games With Probability | |
| Speaker: Elchanan Mossel, UC Berkeley | ||
| Time: 16:00-17:00, November 7, 2007 (Wednesday) |
| 26 | Title: Guassian tools in hardness of approximation, social choice and combinatorics | |
| Speaker: Elchanan Mossel, UC Berkeley | ||
| Time: 16:00-17:00, November 9, 2007 (Friday) |
| 27 | Title: Online Frequency Assignment in Wireless Communication Networks | |
| Speaker: Francis Chin, Computer Science Department, The University of Hong Kong (HKU) | ||
| Time: 15:30 - 16:50, November 12, 2007 (Monday) |
| 28 | Title: Finding Motifs Computationally | |
| Speaker: Francis Chin, Computer Science Department, The University of Hong Kong (HKU) | ||
| Time: 10:30 - 11:40, November 13, 2007 (Tuesday) |
| 29 | Title: Critical Percolation on Finite Graphs | |
| Speaker: Asaf Nachmias, UC Berkeley | ||
| Time: 11:00-12:00, December 3, 2007 (Monday) |
| 30 | Title: Broadcast Stream Authentication | |
| Speaker: Christophe Tartary, ITCS, Tsinghua University | ||
| Time: 16:00-17:30, December 4, 2007 (Tuesday) |
Seminars in 2006
| 1 | Title: Network Games and the Price of Anarchy or Stability | |
| Speaker: Eva Tardos, Cornell University | ||
| Time: February 24, 2006 | ||
| 2 | Title: I/O-Efficient Batched Union-Find and Its Applications to Terrain Analysis | |
| Speaker: Ke Yi, Duke University (now at AT & T Research Labs) | ||
| Time: March 8, 2006 | ||
| 3 | Title: Approximation Algorithms for the k-Facility Location Problem | |
| Speaker: Peng Zhang, Institute of Software, Chinese Academy of Sciences | ||
| Time: March 17, 2006 | ||
| 4 | Title: Stochastic Optimization is (almost) as Easy as Deterministic Optimization | |
| Speaker: David Shmoys, Cornell University | ||
| Time: March 20, 2006 | ||
| 5 | Title: Search via Quantum Walks | |
| Speaker: Ashwin Nayak, University of Waterloo | ||
| Time: March 21, 2006 | ||
| 6 | Title: Pseudorandomness and Combinatorial Constructions | |
| Speaker: Luca Trevisan, University of California, Berkeley | ||
| Time: March 29, 2006 | ||
| 7 | Title: Gowers Uniformity, Influence of Variables and Probabilistically Checkable Proofs | |
| Speaker: Luca Trevisan, University of California, Berkeley | ||
| Time: March 31, 2006 | ||
| 8 | Title: Exclusive Set Systems and Applications | |
| Speaker: David Woodruff, MIT | ||
| Time: April 7, 2006 | ||
| 9 | Title: A Short Introduction to Combinatorial Property Testing: Part I and Part II | |
| Speaker: Dana Ron, Tel Aviv University, Israel | ||
| Time: April 12 (Part I) and April 14 (Part II), 2006 | ||
| 10 | Title: Probabilistic Proof Systems: Part I and Part II | |
| Speaker: Oded Goldreich, Weizmann Institute of Science, Israel | ||
| Time: April 12 (Part I) and April 14 (Part II), 2006 | ||
| 11 | Title: How Many Founders Shall we assume for Haplotype Reconstruction? -- on Coalescence, Dirichlet Processes, and Nonparametric Bayes |
|
| Speaker: Eric Xing, Carnegie-Mellon University | ||
| Time: April 25, 2006 | ||
| 12 | Title: The Knuth-Yao Quadrangle Inequality Speedup is a Consequence of Total Monotonicity | |
| Speaker: Mordecai Golin, Hong Kong University of Science & Technology | ||
| Time: June 5, 2006 | ||
| 13 | Title: Theory of Computation as a Lens on the Sciences: the Example of Computational Molecular Biology | |
| Speaker: Richard Karp, University of California, Berkeley | ||
| Time: September 11, 2006 | ||
| 14 | Title: Graph Problems in the Streaming Model | |
| Speaker: Sampath Kannan, University of Pennsylvania | ||
| Time: October 19, 2006 | ||
| 15 | Title: Solving Huge Systems of Linear Equations | |
| Speaker: Adi Shamir, Weizmann Institute of Science, Israel | ||
| Time: December 14, 2006 | ||
| 16 | Title: Rigorous Bounds on Cryptanalytic Time/Memory Tradeoffs | |
| Speaker: Adi Shamir, Weizmann Institute of Science, Israel | ||
| Time: December 14, 2006 |
Seminars in 2005
| 1 | Title: The Power( and Weakness ) of Randomness in Computation | |
| Speaker: Avi Wigderson, Princeton Advanced Institution, USA | ||
| Time: April 27, 2005 | ||
| 2 | Title: Sting: an Automatic Defense System against Zero-day Worm Attacks | |
| Speaker: Dawn Song, Carnegie Mellon University, USA | ||
| Time: May 23, 2005 | ||
| 3 | Title: Defending against Large-scale Internet DDoS Attacks | |
| Speaker: Adrian Perrig, Carnegie Mellon University, USA | ||
| Time: May 23, 2005 | ||
| 4 | Title: Perspectives in Computer Science | |
| Speaker: Leslie G. Valiant, Harvard University, USA | ||
| Time: August 30, 2005 | ||
| 5 | Title: From Quantum Computers to Identification of Molecules | |
| Speaker: Tal Mor, Technion University, Israel | ||
| Time: September 6, 2005 | ||
| 6 | Title1: Union-find with deletions | |
| Title2: Spanners and emulators with sublinear distance errors | ||
| Speaker: Uri Zwick, Tel Aviv University, Israel | ||
| Time: From September 1 to September 30, 2005 | ||
| 7 | Title: Research in Voting Systems | |
| Speaker: Ronald L. Rivest , MIT, USA | ||
| Time: October 19, 2005 |
| 8 | Title: Research in Voting Systems | |
| Speaker: Ron Rivest | ||
| Time: October 19, 2005 |
| 9 | Title: Series Lectures Advanced Topics in Computational Molecular Genomics (totally eight lectures) | |
| Speaker: Michael QiWei Zhang, Cold Spring Harbor Laboratory, USA | ||
| Time: From November 11 to November 30, 2005 | ||
| 10 | Title: Quadratic Lower Bounds on Matrix Rigidity | |
| Speaker: Satyanarayana V. Lokam, University of Michigan, USA | ||
| Time: November 16, 2005 | ||
| 11 | Title: Meet the Master | |
| Speaker: John Hopcroft, Cornell University, USA | ||
| Time: November 18, 2005 |
| 12 | Title: The Mathematical Theory of Resource Allocation in Communication Networks: Part I and Part II | |
| Speaker: Edmund Yeh, Yale University, USA | ||
| Time: November 21 (Part I) and November 23 (Part II), 2005 |
Seminars in 2004
| 1 | Title: Design by Building up and Breaking through Abstractions | |
| Time: October.13,2004 | ||
| Speaker: Yanhong Annie Liu, State University of New York, USA | ||
| 2 | Title: The Analytic Techniques for MDx Hash Functions | |
| Speaker: XiaoYun Wang, ShanDong University, China | ||