CUHK Theory Lunch

The Chinese University of Hong Kong

Spring 2016


date topic
Jan 15
 
Andrej Bogdanov
On share size of threshold secret sharing schemes
Jan 22
 
Siu On Chan
Sums-of-squares lower bounds for random instances
Jan 29
 
Russell Lai
Cryptography for Parallel RAM from Indistinguishability Obfuscation
Feb 5
 
Spring festival
Feb 12
 

Feb 19
 
Dominik Scheder
Decycling Directed Graphs
Feb 26
 
Isaac Huang
Tractable Projection Safety in Weighted CSPs
Mar 4
 

Mar 11
 
Chandra Nair
Auxiliary variables and superposition coding region for broadcast channels
Mar 18
 
Tongxin Li
Algorithms and Approximations for Capacities of Deletion Channels
Mar 25
 
Easter holiday

Fall 2015


date topic
Sep 11
 
Siu On Chan
Walks and evolving sets: Faster convergences and limitations
Sep 18
 
Salman Beigi
A monotone measure for non-local correlations
Sep 25
 
Xin Huang
The assignment game and its core
Oct 2
 

Oct 9
 
Chin Ho Lee
Some limitations of the sum of small-bias distributions
Oct 16
 
Prahladh Harsha
On non-classical polynomials
Oct 23
 
Siyao Guo
On the hardness of Learning with Rounding over small modulus
Oct 30
 
Chris Williamson
Dual polynomials and the approximate degree of OR
Nov 6
 

Nov 13
 
Sid Jaggi
Deniable / covert / stealthy / LPD communication
Nov 20
 
Dustin Wang
Hypercontractivity for the binary erasure channel
Nov 27
 
Zihan Tan
On the inequalities of projected volumes
Dec 4
 
Pascal Vontobel
Shut up and calculate!

Spring 2015


date topic
Jan 16
 
Diptarka Chakraborty
An algorithm for reachability in directed layered planar graphs
Jan 23
 
Chris Williamson
The Szemeredi-Trotter theorem
Feb 13
 
Shengyu Zhang
Fourier sparsity of GF(2) polynomials
Mar 6
 
Chris Williamson
Analogues of graph eigenvalues in arbitrary metric spaces
Mar 13
 
Zitian Chen
A characterization of capacity for online (causal) binary channels
Mar 20
 
Siyao Guo
Negation-limited formulas
Mar 27
 
Pascal Vontobel
Factor graph transforms
Apr 17
 
Andrej Bogdanov
Pseudorandomness, secret sharing, leakage resilience, and more
Apr 24
 
Chengyu Lin
Secretary markets with local information

Fall 2014


date topic
Sep 5
 
Andrej Bogdanov
On basing size-verifiable one-way functions on NP-hardness
Sep 12
 
Navid Alamati
Learning with errors and completeness of Gaussian distribution
Sep 19
 
Peter Poon
The mixing time of Glauber Dynamics for colouring regular trees
Sep 26
 
Chengyu Lin
A Simple FPTAS for Counting Edge Covers
Oct 3
 

Oct 10
 
Ye Junjie
Dual Connectedness of Edge-Bicolored Graphs and Beyond
Oct 17
 
Huang Xin
Teaching and complexity in computational learning theory
Oct 24
 
Zhou Hong
Max cut and sums of squares proofs
Oct 31
 
Siyao Guo
The power of negations in cryptography
Nov 7
 
Qiwen Wang
On the capacity of the insertion / deletion channel
Nov 14
 
Silas Richelson
How to construct a fully homomorphic encryption scheme
Nov 21
 
Pizza lunch day
Nov 28
 
Sheng Cai
Sparse signals with Unknown Phases Efficiently Recovered
Dec 5
 
Chandra Nair
On maximizing mutual information between boolean functions on noisy inputs

Spring 2014


date topic
Jan 17
 
Hong Zhou
A unified algorithm for degree-bounded survivable network design
Jan 24
 
Student pizza lunch
Jan 31
 
Spring festival
 
Feb 7
 

Feb 14
 
Siyao Guo (in SHB 1027)
Highlights of the ITCS 2014 conference
Feb 21
 
Sebastian Müller
From refuting random 3CNF to separations in proof complexity
Feb 28
 
Joseph Tsang
Majority is stablest: A discrete proof
Mar 7
 

Mar 14
 
Kwok Tsz Chiu
Low rank approximation and regression in input sparsity time
Mar 21
 

Mar 28
 
Ken Leung
The Quantum 2-Satisfiability problem
Apr 4
 
Gary Sham
Subexponential time list-decoding of unbiased linear codes
Apr 11
 
Student pizza lunch

Fall 2013


Organized by Siyao Guo

Spring 2013


date topic
Jan 18
 
Sida Liu
A proof of the entropy-power inequality [pdf]
Jan 25
 
Yintat Lee
A max-flow algorithm for undirected un-capacitatated graphs
Feb 1
 
Lap Chi Lau
Graphs from codes [pdf]
Feb 8
 
Yufei Tao
I/O Efficient Maxima and Quantile
Feb 15
 
Spring festival
 
Feb 22
 
Mar 1
 
Tsz Chiu Kwok
Solving SDD systems in nearly linear time
Mar 8
 
Siyao Guo
Parities, noise, and pseudorandom functions
Mar 15
 

Mar 22
 
Chiwang Chow
Classical hardness of learning with errors
Mar 29
 
Easter holiday
 
Apr 5
 
Hing Yin Tsang
Spectral norm and the log-rank conjecture for XOR functions
Apr 12
 
Chin Ho Lee
Constructive discrepancy minimization
Apr 19
 


Fall 2012


date topic
Sep 14
 
Organizational meeting
Sep 21
 
Sep 28
 
Shengyu Zhang in ERB 1009
On the communication complexity of sampling
Oct 5
 
Andrej Bogdanov in SHB 1021
Can semidefinite programs break pseudorandom generators?
Oct 12
 
Hing Yin Tsang in SHB 121
On parallel repetition
Oct 19
 
Oct 26
 
Kwok Tsz Chiu in SHB 121
On Cheeger's inequality
Nov 2
 
Chin Ho Lee in SHB 1021
Algorithms for linear equations
Nov 9
 
Hollis Wong in SHB 1021
Testing Fourier sparsity
Nov 16
 
Mak Yan Kei in SHB 1021
Testing Boolean-ity
Nov 23
 
Mayank Bakshi in SHB 1021
Computing sparse FFT
Nov 30
 
Chiwang Chow in SHB 1021
Linear equations with structured noise
Dec 7
 
Chen Fei in SHB 1021
Lossy trapdoor functions [pdf]
Dec 14
 
Siu On Chan in SHB 1021
Approximation resistance from pairwise independent subgroups

Spring 2012


date topic
Jan 9
 
Chandra Nair
Convex envelopes and new information inequalities
Jan 20
 
coding theory seminar
Jan 27
 
Spring Festival Week
Feb 3
 
coding theory seminar
Feb 10
 
Chiwang Chow
Algorithms for learning noisy parities
Feb 17
 
coding theory seminar in SHB 121
Feb 24
 
coding theory seminar
Mar 2
 
coding theory seminar
Mar 9
 
 
Mar 16
 
coding theory seminar in SHB 121
Mar 23
 
coding theory seminar
Mar 30
 
coding theory seminar in SHB 121
Apr 6
 
Easter holiday
Apr 13
 
Kenneth
Algebraic-geometric codes
Jun 8
 
Luca Trevisan in SHB 121

Fall 2011


date topic
Sep 9
 
Andrew Wan
On the entropy-influence conjecture
Sep 16
 
Sid Jaggi
Binary error correcting network codes
Sep 23
 

Sep 30
 
Mak Yan Kei
On quantum property testing
Oct 7
 
Guo Siyao
3XOR and finding triangles in a graph
Oct 14
 
Li Fan
Testing clique and biclique collections
Oct 21
 
Oct 28
 
Liu Yang
On nonnegative rank
Nov 4
 
Hollis Wong
Influence and sensitivity lower bounds for boolean functions
Nov 11
 
Lee Chin Ho
On homomorphic encryption
Nov 18
 
Kwok Tsz Chiu
On group-theoretic approaches to fast matrix multiplication
Nov 25
 
Guo Chengwei
Making a graph Eulerian by removing few edges
Dec 2
 
Ma Chenglong
Hedging bets with correlated quantum strategies

Spring 2011


date topic
Jan 21
 
Amin Gohari
On the capacity region in network coding
Jan 28
 

Feb 4
 
Spring Festival Week
Feb 11
 

Feb 18
 
Chow Chi Wang
Deterministic primality testing
Feb 25
 
Li Fan
Lower bounds on testing bipartiteness
Mar 4
 
Kwok Tsz Chiu
Constructive algorithms for discrepancy minimization
Mar 11
 
Hackson Leung
Generalized nested dissection
Mar 18
 
Leo Cheung
Faster algorithms for Hamiltonian cycles
Mar 25
 

Apr 1
 
Yu Yuanming
Improved LP-based approximations of steiner trees
Apr 8
 
Guo Chengwei
The complexity of a puzzle game: Clickomania
Apr 15
 
Geng Yanlin
An information inequality
Apr 22
 
Easter Holiday
Apr 27
 
Hollis Wong in room 1027
Quantum proofs for classical theorems