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
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