Institute of Theoretical Computer Science and Communications


2017


Workshops

Apr 12 A Workshop on Information Theory and Mathematics - co-organized by HK IT-chapter, INC, and ITCSC
Jan 16-29 ITCSC-INC Winter School 2017

Joint Seminars

May 04
CSE-ITCSC Joint Seminar
The Electric Vehicle Touring Problem
Prof. Chung-Shou Liao, National Tsing Hua University

2016


Workshops

Dec 20 Hong Kong TheoryFest 2016
Aug 22-26 China Theory Week 2016
Jan 25-29 ITCSC-INC Winter School 2016

Joint Seminars

Dec 20
CSE-ITCSC Joint Seminar
Computational Medicine and Health Care
Prof. Danny Chen, University of Notre Dame
Oct 27
ITCSC Joint Seminar
The Hardness of Minimum Fill-In: A Dark Secret of the Old Chinese Art
Dr. Yixin Cao, The Hong Kong Polytechnic University
May 26
CSE-ITCSC Joint Seminar
Differentially Private Release and Learning of Threshold Functions
Mr. Mark Bun, Harvard University
Apr 21
CSE-ITCSC Joint Seminar
The Border between Possible and Impossible in Data Privacy
Prof. Salil Vadhan, Harvard University and National Chiao-Tung University
Apr 18
CSE-ITCSC Joint Seminar
Randomness Extraction from Generalized Santha-Vazirani Sources
Dr. Omid Etesami, Institute for Research in Fundamental Sciences (IPM)
Jan 21
CSE-ITCSC Joint Seminar
The Power of Adaptivity in Data Analysis
Mr. Thomas Steinke, Harvard University

2015


Workshops

Jan 26-30 ITCSC-INC Winter School 2015
Jan 9 Hong Kong Theory Day 2015

CSE Seminars

Dec 22
CSE Seminar
Correlation Bounds Against Monotone NC^1
Prof. Benjamin Rossman, National Institute of Informatics
Dec 22
CSE Seminar
Lower Bounds for Bounded-Depth Formulas
Prof. Benjamin Rossman, National Institute of Informatics

Joint Seminars

Dec 7
CSE-ITCSC Joint Seminar
Efficient Pseudorandom Functions via On-the-Fly Adaptation
Prof. Dominique Schröder, Saarland University
Oct 19
CSE-ITCSC Joint Seminar
Old and New PCP Constructions: Towards the Sliding Scale Conjecture
Prof. Prahladh Harsha, Tata Institute of Fundamental Research
Sep 23
CSE-ITCSC Joint Seminar
Compressing Communication in Distributed Protocols
Mr. Ilan Komargodski, Weizmann Institute
Jun 15
ITCSC-INC Joint Seminar
Communication Amid Uncertainty
Dr. Madhu Sudan, Microsoft Research New England
Apr 8
CSE-ITCSC Joint Seminar
Reed-Muller Codes for Random Errors and Erasures
Prof. Amir Shpilka, Tel-Aviv University

2014


Workshops

Jan 20-23 ITCSC-INC Winter School 2014

Joint Seminars

Dec 1
CSE-ITCSC Joint Seminar
Random Oracles in the Real World through the Eyes of Obfuscation
Mr. Arno Mittelbach, TU Darmstadt
Nov 17
CSE-ITCSC Joint Seminar
An Algebraic Approach to Non-Malleability
Dr. Silas Richelson, University of California, Los Angeles
Oct 21
CSE-ITCSC Joint Seminar
Majority is incompressible by AC^0[p] circuits
Mr. Igor Oliveira, Columbia University
Aug 7
CSE-ITCSC Joint Seminar
An Algebraic Approach to Non-Malleability
Prof. Alon Rosen, Herzliya Interdisciplinary Center
Aug 7
CSE-ITCSC Joint Seminar
Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
Dr. Kai-Min Chung, Academia Sinica
Jun 20
CSE-ITCSC Joint Seminar
Authentication in Constrained Settings
Prof. Katerina Mitrokotsa, Chalmers University of Technology
Jan 6
CSE-ITCSC Joint Seminar
Space-Bounded Communication Complexity
Mr. Song Hao, Tsinghua University

2013


Workshops

July 8-9 Workshop on Theoretical Aspects of Big Data
Jan 14-17 ITCSC-INC Winter School 2013 [photos]

Joint Seminars

Jan 4
CSE-ITCSC-INC Joint Seminar
A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs
Prof. Luca Trevisan, Stanford University

ITCSC Seminars

Feb 21 Cryptography with Streaming Devices
Prof. Periklis Papakonstantinou, IIIS/ITCS Tsinghua University

2012


Workshops

Jul 25-27 Network Science Workshop
Jul 23-24 Machine Learning Workshop
Jul 18-20 Tsinghua-MIT-CUHK Research Center Workshop on Theoretical Computer Science
Jun 18-22 Quantum Information Workshop
Jan 15-19 ITCSC-INC Winter School 2012 [photos]

ITCSC Colloquium

Jan 4 Global Solutions with Local Information: Optimizing Large-Scale Networks Based on Local Information
Prof. Thomas Moscibroda, Lead Researcher, Microsoft Research Asia, Microsoft Corporation
Jan 4 Stability vs. Cost of Matchings
Prof. Roger Wattenhofer, ETH Zurich, Switzerland

Joint Seminars

Dec 14
Engineering Faculty Distinguished Lecture
The Science of Information: From Communications to DNA Sequencing
Prof. David Tse, University of California at Berkeley
Jun 6
ITCSC-INC Joint Seminar
New results on interference channels with three user pairs
Dr. Bernd Bandemer, Postdoctoral researcher, University of California, San Diego
Apr 12
CSE-ITCSC-INC Joint Seminar
Graph Connectivity, Network Coding, Expander Graph, and Matrix Rank
Prof. Lap Chi Lau, Assistant Professor, CSE Department, CUHK

ITCSC Seminars

Aug 9 Can we teleport a quantum clock? Fundamental limits to the use of entanglement to simulate quantum communication
Prof. Giulio Chiribella, Associate Professor, IIIS, Tsinghua University
Aug 2 Entanglement in Physical States
Dr. Alioscia Hamma, Distinguished Research Fellow, Perimeter Institute for Theoretical Physics, Canada
Apr 26 The Exponential Mechanism for Social Welfare: Private, Truthful, and Nearly Optimal
Mr. Zhiyi Huang, PhD Student, CIS Department, University of Pennsylvania
Jan 18 Extreme-value Theorems for Optimal Multidimensional Pricing
Mr. Yang Cai, PhD Student, CSAIL, MIT

2011


Workshops

Jan 17-21 ITCSC-INC Winter School 2011 [photos]

Joint Colloquium

Nov 8
CSE-ITCSC Joint Colloquium
Circuit Complexity meets the Theory of Randomness
Prof. Eric Allender, Professor, Rutgers University

Joint Seminars

Sep 15
IE-ITCSC Joint Seminar
Binary Independent Component Analysis and Its Applications
Prof. Rong Zheng, Assocaite Professor, Department of Computer Science, University of Houston
Sep 8
CSE-ITCSC Joint Seminar
Mansour's Conjecture for Random DNF formulas
Prof. Andrew Wan, Assistant Professor, ITCS, Tsinghua University
CSE-ITCSC Joint Seminar
New questions in pseudo-randomness for answering old problems
Dr. Periklis Papakonstantinou, Assistant Professors, ITCS, Tsinghua University
Sep 1
CSE-ITCSC Joint Seminar
Property Testing Lower Bounds via Communication Complexity
Dr. Kevin Matulef, Postdoctoral Researcher, ITCS, Tsinghua University
Aug 30
IE-ITCSC Joint Seminar
Economics of Cooperative Spectrum Sharing: Bargaining, Contract, and Auction
Prof. Jianwei Huang, Assistant Professor, Department of Information Engineering, CUHK
Aug 22
INC-ITCSC Joint Seminar
Coding for Online (Causal) Adversaries
Prof. Michael Langberg, Open University of Israel
Jul 14
IE-ITCSC Joint Seminar
Scaling laws- how useful are they at predicting network performance?
Prof. Ravi R. Mazumdar, Professor and University Research Chair, University of Waterloo, Canada
Jan 14
IE-ITCSC Joint Seminar
Smart Grid Communications and Networking: An Overview
Prof. Dusit Niyato, Assistant Professor, Nanyang Technological University, Singapore

ITCSC Seminars

May 3 Towards the capacity region of two receiver broadcast channels
Prof. Chandra Nair, Department of Information Engineering, CUHK
Jan 14 Sparse Johnson-Lindenstrauss Transforms
Dr. Jelani Nelson, MIT CSAIL

2010


Workshops

Aug 9-11 Mini-workshop on the Theory of Computing
Mar 23-Apr 14 Elliptic Curve Cryptography
Mar 8-9 The Broadcast Channel Summit
Jan 24-30 ITCSC-INC Winter School 2010 [photos]
Jan 4 Crypto Day

Colloquium

Feb 22 Two "Simple" Problems That Imply Strong Circuit Lower Bounds
Prof. Ran Raz, Professor of Mathematics and Computer Science, The Weizmann Institute of Science.
Strong Parallel Repetition Theorem for Free Projection Games
Ms. Ricky Rosen, PhD student, Tel-Aviv University

Joint Seminars

Apr 30
IE-ITCSC Joint Seminar
Synthesizing Distributed Algorithms for Combinatorial Network Optimization
Prof. Minghua Chen, Assistant Professor, Department of Information Engineering, CUHK
Jan 14
IE-ITCSC Joint Seminar
Generating Secret in a Network
Dr.Chung Chan, Ph.D. student, Massachusetts Institute of Technology, USA
Jan 12
IE-ITCSC Joint Seminar
Cooperative Interference Management in Multi-Cell Downlink Beamforming
Prof. Shuguang Cui, Assistant Professor, Department of Electrical and Computer Engineering, Texas A&M University
Jan 6
IE-ITCSC Joint Seminar
Location-Aware Wireless Networks
Prof. Moe Win, Associate Professor, Massachusetts Institute of Technology, Cambridge, MA, USA

ITCSC Seminars

Nov 17 Feedback-driven Opportunistic Access Strategies in Cognitive Radio Networks
Prof. Xin Liu, Associate Professor, Department of Computer Science, University of California at Davis
Jul 28 Cryptographic Elections - Challenges and Opportunities
Dr. Alon Rosen, School of Computer Science, The Herzliya Interdisciplinary Center
Mar 15 Dynamic Indexability and the Optimality of B-trees and Hash Tables
Prof. Ke Yi, Assistant Professor, Department of Computer Science and Engineering, HKUST
Jan 11 Efficient Indexes of Document Retrieval Problems
Prof. Wing-Kai Hon, Assistant Professor, Department of Computer Science, National Tsing Hua University, Taiwan

2009


Workshops

Jan 15-21 ITCSC-INC Winter School 2009 [photos]

Colloquium

Dec 21 Bipartite Ratio And Bipartite Density Of Triangle Free Subcubic Graphs
Prof. Zhu Xuding, Department of Applied Mathematics, National Sun-Yat-sen University, Taiwan
Aug 5 Algorithms for Data Management
Prof. Samir Khuller, Computer Science Department, University of Maryland
Apr 29 Data Reduction and FPT Kernelization: Practical Algorithms and Lower Bounds
Prof. Michael Fellows, Professor of Computer Science, University of Newcastle, Australia
Apr 27 The Multivariate Approach to Algorithms and Complexity
Prof. Michael Fellows, Professor of Computer Science, University of Newcastle, Australia

Theory Seminar Series

Aug 18 On Broadcast Scheduling
Prof. Samir Khuller, Computer Science Department, University of Maryland
Jul 21 Sorting on Complete Bipartite Graphs
Prof. Xiaoming Sun, Associate Professor, Tsinghua University, BeijingProf. Andrew Yao, Director of ITCSC, CUHK
Jul 14 Codes against Online Adversaries
Prof. Sidharth Jaggi, Assistant Professor, Department of Information Engineering, CUHK
Jul 7 Mathematical Modeling of Incentive Policies in P2P Networks
Prof. John Lui, Chairman / Professor, Department of Computer Science & Engineering, CUHK
Jun 30 Lower Bounds of Communication Complexity by Information Complexity
Prof. Shengyu Zhang, Assistnat Professor, Department of Computer Science & Engineering, CUHK

Joint Seminars

Dec 14 A Semidefinite Programming Approach to the Graph Realization Problem
Prof. Jean Walrand, Professor, EECS, University of California, Berkeley, USA
Apr 16 Network Coding - A Paradigm Shift in Data Transport
Prof. Shuo-Yen Robert Li, Professor of Information Engineering, CUHK
Research on Network Virtualization
Prof. Akihiro Nakao, Associate Professor, University of Tokyo

ITCSC Seminars

Nov 19 Combinatorial Constructions of One-way Functions and Their Security
Prof. Andrej Bogdanov, Assistant Professor, Department of Computer Science & Engineering, CUHK
Nov 9 Universal Rigidity and Edge Sparsification for Sensor Network Localization
Prof. Anthony So, Assistant Professor, Department of Systems Engineering & Engineering Management, CUHK
Oct 28 On Marton's achievable region and proof of an information inequality using a Caratheodory type argument
Prof. Chandra Nair, Assistant Professor, Department of Information Engineering, CUHK
Oct 19 On The Power of A Unique Quantum Witness
Prof. Shengyu Zhang, Assistnat Professor, Department of Computer Science & Engineering, CUHK
Sep 15 Capacity of Large-scale CSMA Wireless Networks
Dr. Sid Chi-kin Chau, Croucher Foundation Research Fellow, Electrical and Electronic Department, University College London
Sep 11 Least Privilege Concept in Workflow Model
Prof. Patrick C. K. Hung, University of Ontario Institute of Technology (UOIT), Canada
Sep 3 Facets of Entropy
Prof. Raymond W. H. Yeung, Professor of Information Engineering, CUHK
Aug 31 An Axiomatic Theory of Fairness
Prof. Mung Chiang, Electrical Engineering Department, Princeton University
Aug 12 An Evidence Based Learning Approach To Development And Evaluation Of An Interprofessional Education Core Competency Framework
Prof. Jayshiro Tashiro, Professor, Health Education Technology Research Unit University of Ontario Institute of Technology
Jul 29 Perfect Matchings in O(n^{1.5}) Time in Regular Bipartite Graphs
Prof. Sanjeev Khanna, Professor of Computer and Information Science, University of Pennsylvania
Jul 15 An Approximation Approach to Network Information Theory
Prof. David Tse, Professor, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley
Jul 6 Fairness with an Honest Minority and a Rational Majority
Dr. Alon Rosen, School of Computer Science, The Herzliya Interdisciplinary Center
Jun 24 Two-message quantum interactive proofs are in PSPACE
Prof. Rahul Jian, Assistant Professor, Department of Computer Science, National University of Singapore
Jun 22 Facets of Entropy
Prof. Raymond W. H. Yeung, Professor of Information Engineering, CUHK
Jun 10 Redundancy-Related Bounds on Generalized Huffman Codes
Dr. Michael Baer, Member of Technical Staff at VMware, Inc.
May 13 Scalable Nonblocking Switches and Geometric Intuition
Prof. Shuo-Yen Robert Li, Professor of Information Engineering, CUHK
May 11 Unified Algebraic Theory for Sorting, Routing, Multicasting, & Concentration Networks
Prof. Shuo-Yen Robert Li, Professor of Information Engineering, CUHK
May 7 A Tool Oriented Approach to Network Capacity
Prof. Michelle Effros, Professor of Electrical Engineering, California Institute of Technology
Apr 9 Lower Bounds in Communication Complexity
Prof. Shengyu Zhang, Assistant Professor, Department of Computer Science & Engineering, CUHK
Apr 6 Complexity-based Cryptography: A match that was once made in heaven
Prof. Andrej Bogdanov, Assistant Professor, Department of Computer Science & Engineering, CUHK
Mar 9 Channel Codes Against Causal Adversaries
Prof. Sidharth Jaggi, Assistant Professor, Department of Information Engineering, CUHK
Mar 2 Probabilistic Analysis of Semidefinite Programming Relaxations, with Application to Detection for Multiple-Input Multiple-Output Systems
Prof. Anthony So, Assistant Professor, Department of Systems Engineering & Engineering Management, CUHK
Feb 16 Rank Aggregation: Together We're Strongs
Dr. Frans Schalekamp, Postdoctoral Researcher, Institute for Theoretical Computer Science, Tsinghua University
Feb 12 Deterministic Sampling Algorithms for Network Design
Dr. Anke van Zuylen, Postdoctoral Researcher, Institute for Theoretical Computer Science, Tsinghua University
Feb 9 Back-of-the-Envelope Computation of Throughput Distributions in CSMA Wireless Networks
Prof. Liew Soung Chang, Chairman and Professor, Department of Information Engineering, CUHK
Feb 2 Three Results on the Discrete Memoryless Broadcast Channel
Prof. Chandra Nair, Assistant Professor, Department of Information Engineering, CUHK

2008


Workshops

May 23 CUHK-Tsinghua Student Workshop on Theoretical Computer Science
Feb 1
Theory Afternoon
Random walk on graphs and its algorithmic applications
Dr. Shengyu Zhang, Postdoctoral Researcher
Computer Science Department and Institute for Quantum Computing, California Institute of Technology
On Recent Developments in Learning with Agnostic Noise
Dr. Elad Verbin, Postdoctoral, Institute of Theoretical Computer Science, Tsinghua University
Jan 21-26 ITCSC-INC Winter School 2008 [photos]
Jan 15
Theory Afternoon
Sublinear Time Algorithms
Prof. Luca Trevisan , Professor, University of Califronia, Berkeley
Average-case hardness for errorless heuristics
Dr. Andrej Bogdanov, Tsinghua University

Colloquium

Dec 29 Graphs and Polymorphisms
Prof. Pavol Hell, Professor, School of Computing Science, Simon Fraser University, Canada
Nov 18 Some Computer Science Techniques in Bioinformatics
Prof. Wen-Lian Hsu, Distinguished Research Fellow, Institute of Information Science, Academia Sinica, Taiwan
Nov 14 The Internet is Flat: a Brief History of Networking in the Next Ten Years
Prof. Don Towsley, Professor, Department of Computer Science, University of Massachusetts
Nov 11 Modeling Disruption Tolerant Networks: Fluid Models and Mobility Models
Prof. Don Towsley, Professor, Department of Computer Science, University of Massachusetts

Invited Seminars

Dec 18 Multipartite Quantum Entanglement and Tensor Rank
Prof. Yaoyun Shi, Associate Professor, Electrical Engineering and Computer Science University of Michigan, Ann Arbor
Dec 15 Computing Equilibria in Large Games
Dr. Constantinos Daskalakis, Postdoctoral Researcher, Microsoft Research-New England
Nov 26 Making Dense Networks Smarter with Randomized Network Coding and Distributed Signal Processing
Prof. Kannan Ramchandra, Professor, Department of Electrical Engineering and Computer Science, Univesity of California, Berkeley
Oct 3 Approximation Algorithms on Metric Spaces and Graphs
Dr. Hubert Chan, Postdoctoral Researcher, Max Planck Institute for Informatics in Germany
Sep 8 Streaming Capacity of P2P
Dr. Shao Liu, Postdoctoral Researcher, Department of Electrical Engineering, Princeton University
Sep 3 Design and Analysis of TCP for the Next Decade Internet
Dr. Shao Liu, Postdoctoral Researcher, Department of Electrical Engineering, Princeton University
Jun 6 Optimisation on Manifolds
Prof. Jonathan Manton, Executive Director, Australian Research Council
Jun 2 Computation: How does Nature compute and how should we?
Prof. Jonathan Manton, Executive Director, Australian Research Council
May 30 The Connectivity of Finite Random Geometric Graphs
Dr. Chi-kin Chau, Croucher Foundation Research Fellow, University College London
May 27 Power-Aware High-Performance Computing: The Dawn of the Green Computing Era
Prof. Ishfaq Ahmad, Professor, Computer Science and Engineering Department, University of Texas at Arlington
Apr 28 Making Classical Zero Knowledge Protocols Secure Against Quantum Attacks(Part II)
Dr. Pranab Sen, Reader, School of Technology and Computer Science, Tata Institute of Fundamental Research
Apr 23 Making Classical Zero Knowledge Protocols Secure Against Quantum Attacks(Part I)
Dr. Pranab Sen, Reader, School of Technology and Computer Science, Tata Institute of Fundamental Research
Apr 21 Content Pipe Divide and Network Distribution Capacity
Prof. Mung Chiang, Assistant Professor, Princeton University
Apr 3 Routing in large networks despite Byzantine failures
Dr. Radia Perlman, Sun Fellow, Sun Microsystems Inc.
Apr 1 Data: Making it be there when you want it and go away when you want it gone
Dr. Radia Perlman, Sun Fellow, Sun Microsystems Inc.

Weekly Seminars

Oct 30 Utility-Optimal Random Access without Message Passing
Prof. Jianwei Huang, Assistant Professor, Department of Information Engineering, CUHK
Oct 23 Blind Maximum-Likelihood Detection of Orthogonal Space-Time Block Codes:
   High-Performance Efficient Implementations, Identifiability, and Code Constructions

Prof. Ken Ma, Assistant Professor, Department of Electronic Engineering , CUHK
Oct 2 Reliable Communication in the Absence of a Common Clock
Prof. Raymond Yeung, Professor of Information Engineering , CUHK
Sep 29 Martingales of Patterns
Prof. Shuo-Yen Robert Li, Professor, Department of Information Engineering , CUHK
Sep 25 Khintchine-Type Inequalities and Their Applications in Optimization
Prof. Anthony So, Assistant Professor, Department of Systems Engineering & Engineering Management, CUHK
Sep 8 Iterative Relaxation
Prof. Lap-Chi Lau, Assistant Professor, Department of Computer Science & Engineering, CUHK
Apr 14 Multiple-Input-Multiple-Output Detection using Semidefinite Relaxation
Prof. Ken Ma, Assistant Professor, Department of Electronic Engineering , CUHK
Apr 7 A Simple Model for P2P Streaming
Prof. Dah-ming Chiu, Professor, Department of Information Engineering , CUHK
Mar 17 Optimal power control in wireless ad hoc networks by linear multiplicative fractional programming
Prof. Angela Zhang, Assistant Professor, Department of Information Engineering, CUHK
Mar 10 Approximating graph orientations with high rooted-connectivity
Prof. Lap-Chi Lau, Assistant Professor, Department of Computer Science & Engineering, CUHK
Mar 3 Approximation Algorithms for Nonconvex Quadratic Optimization
Prof. Shuzhong Zhang, Professor, Department of Systems Engineering & Engineering Management, CUHK
Feb 18 Utility Maximization in Peer-to-peer Systems
Prof. Minghua Chen, Assistant Professor, Department of Information Engineering, CUHK
Feb 4 Designing Faster Algorithms by Random Separation
Prof. Leizhen Cai, Professor, Department of Computer Science & Engineering, CUHK
Jan 28 Power Control in Multi-carrier Communication Systems
Prof. Jianwei Huang, Assistant Professor, Department of Information Engineering, CUHK
Jan 14 On Broadcast Channels With 3 Or More Receivers
Prof. Chandra Nair, Assistant Professor, Department of Information Engineering, CUHK

2007


Invited Seminars

Nov 28 A deterministic subexponential algorithm for solving parity games
Prof. Uri Zwick, Professor, Department of Computer Science, Tel Aviv University
Overhang
Prof. Uri Zwick, Professor, Department of Computer Science, Tel Aviv University
Nov 21 Interplays of Computer Science and Economics
Prof. Xiaotie Deng, Chair Professor, Department of Computer Science, City University of Hong Kong

Weekly Seminars

Dec 5 "Real" and "Complex" network codes
Prof. Sidharth Jaggi, Assistant Professor, Department of Information Engineering, CUHK
Nov 28 A Semidefinite Programming Approach to the Graph Realization Problem
Prof. Anthony So, Assistant Professor, Department of Systems Engineering & Engineering Management, CUHK
Nov 14 Network Coding and Its Ramifications
Prof. Raymond Yeung, Professor, Department of Information Engineering, CUHK
Nov 7 Steiner tree packing
Prof. Lap-Chi Lau, Assistant Professor, Department of Computer Science & Engineering, CUHK
CUHK