CCC11 – Tentative Program

 

Wednesday

---------------


8:00-8:50 breakfast


8:50-9:40 2 talks


Improved Direct Product Theorems for Randomized Query Complexity, Andrew Drucker (MIT), Ronald V. Book Prize for Best Student Paper


Making Branching Programs Oblivious Requires Superlogarithmic Overhead, Paul Beame (University of Washington) and Widad Machmouchi (University of Washington)


9:40-10:05 coffee break


10:05-11:20 3 talks:

Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups, Ryan O'Donnell and Yi Wu and Yuan Zhou,


Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs, Yuichi Yoshida

(Kyoto University and Preferred Infrastructure)


Non-negatively Weighted #CSPs: An Effective Complexity Dichotomy, Jin-Yi Cai, (University of Wisconsin – Madison and Beijing University) Xi Chen (Columbia University), and Pinyan Lu (Microsoft Research Asia)


11:30-12:30 FCRC plenary


12:30-2 FCRC lunch


2-3:40 4 talks:


Symmetric LDPC codes are not necessarily locally testable, Eli Ben-Sasson (Technion), Ghid Maatouk (EPFL), Amir Shpilka (Technion and MSR) and Madhu Sudan (MSR)


Towards lower bounds on locally testable codes via density arguments, Eli Ben-Sasson (Technion) and Michael Viderman (Technion)

Linear-algebraic list decoding of folded Reed-Solomon codes, Venkatesan Guruswami (Carnegie Mellon University)


Noisy Interpolation of Sparse Polynomials, and Applications, Shubhangi Saraf (MIT) and Sergey Yekhanin (Microsoft Research)



3:40-4:05 coffee break


4:05-4:55 2 talks:


Paris-Harrington tautologies, Lorenzo Carlucci (Sapienza - Università di Roma), Nicola Galesi (Sapienza - Università di Roma) and Massimo Lauria (Sapienza - Università di Roma)


Relativized Separations of Worst-Case and Average-Case Complexities for NP, Russell Impagliazzo (IAS and UCSD)



8pm - : Rump session


Thursday

-----------


8:00-8:50 breakfast


8:50-9:40 1 talk

Non-Uniform ACC Circuit Lower Bounds, Ryan Williams (IBM Almaden), Best Paper Award


9:40-10:05 coffee break


10:05-11:20 3 talks:


Improved Constructions of Three Source Extractors, Xin Li (University of Texas at Austin)


A New Approach to Affine Extractors and Dispersers, Xin Li (University of Texas at Austin)


Symmetry of Information and bounds on nonuniform randomness extraction via Kolmogorov extractors, Marius Zimand (Towson University)


11:30-12:30 FCRC plenary

12:30-2 FCRC lunch

2-3:40 4 talks:


Near-Optimal and Explicit Bell Inequality Violations, Harry Buhrman (CWI and University of Amsterdam), Oded Regev (Tel Aviv University and ENS, Paris), Giannicola Scarpa (CWI), and Ronald de Wolf (CWI and University of Amsterdam)


Symmetry-assisted adversaries for quantum state generation, Andris Ambainis (University of Latvia)

Loïck Magnin (UL-Brussels, University Paris 11, NEC Laboratories America), Martin Roetteler (NEC Laboratories America), and Jérémie Roland (NEC Laboratories America)



Approximation algorithms for QMA-complete problems, Sevag Gharibian (University of Waterloo),

And Julia Kempe (Tel Aviv University and CNRS, University of Paris 7)


On Arthur Merlin Games in Communication Complexity, Hartmut Klauck (CQT and Nanyang Technological University).



3:40-4:05 coffee break


4:05-4:55 2 talks:


On the Minimal Fourier Degree of Symmetric Boolean Functions, Amir Shpilka (Technion and MSR) and Avishay Tal (Technion)


Property Testing Lower Bounds Via Communication Complexity, Eric Blais (Carnegie Mellon University), Joshua Brody (ITCS, IIIS, Tsinghua University), and Kevin Matulef (ITCS, IIIS, Tsinghua University)



8pm -: Business meeting


Friday

--------

8:00-8:50 breakfast


8:50-9:40 2 talks:


Improved pseudorandomness for regular branching programs, Anindya De (University of California, Berkeley)


Pseudorandom Generators for Combinatorial Checkerboards, Thomas Watson

(University of California, Berkeley)


9:40-10:05 coffee break


10:05-11:20 3 talks:


Bounded-depth circuits cannot sample good codes, Shachar Lovett (Institute of Advanced Study) and
Emanuele Viola (Northeastern University)


k-independent Gaussians Fools Polynomial Threshold Functions, Daniel M. Kane

(Harvard University)


Explicit Dimension Reduction and Its Applications, Zohar S. Karnin (Technion), Yuval Rabani (Hebrew University), and Amir Shpilka (Technion and MSR)



11:30-12:30 FCRC plenary


12:30-2 FCRC lunch


2-3:40 4 talks:


Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae, Matthew Anderson (University of Wisconsin – Madison), Dieter van Melkebeek (University of Wisconsin – Madison), and Ilya Volkovich (Technion)


Tensor Rank: Some Lower and Upper Bounds, Boris Alexeev (Princeton University), Michael Forbes (MIT), and Jacob Tsimerman (Princeton University)


On the Sum of Square Roots of Polynomials and Related Problems, Neeraj Kayal (Microsoft Research India) and Chandan Saha (Max Planck Institute for Informatics)


Linear Systems Over Finite Abelian Groups, Arkadev Chattopadhyay (University of Toronto) and Shachar Lovett (Institute for Advanced Study)