date  topic 

Jan 15 
Andrej Bogdanov On share size of threshold secret sharing schemes 
Jan 22 
Siu On Chan Sumsofsquares 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 
date  topic 

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

Oct 9 
Chin Ho Lee Some limitations of the sum of smallbias distributions 
Oct 16 
Prahladh Harsha On nonclassical 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! 
date  topic 

Jan 16 
Diptarka Chakraborty An algorithm for reachability in directed layered planar graphs 
Jan 23 
Chris Williamson The SzemerediTrotter 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 Negationlimited 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 
date  topic 

Sep 5 
Andrej Bogdanov On basing sizeverifiable oneway functions on NPhardness 
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 EdgeBicolored 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 
date  topic 

Jan 17 
Hong Zhou A unified algorithm for degreebounded 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 2Satisfiability problem 
Apr 4 
Gary Sham Subexponential time listdecoding of unbiased linear codes 
Apr 11 
Student pizza lunch 
Organized by Siyao Guo
date  topic 

Jan 18 
Sida Liu A proof of the entropypower inequality [pdf] 
Jan 25 
Yintat Lee A maxflow algorithm for undirected uncapacitatated 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 logrank conjecture for XOR functions 
Apr 12 
Chin Ho Lee Constructive discrepancy minimization 
Apr 19 
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 Booleanity 
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 
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 Algebraicgeometric codes 
Jun 8 
Luca Trevisan in SHB 121 
date  topic 

Sep 9 
Andrew Wan On the entropyinfluence 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 grouptheoretic 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 
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 LPbased 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 