CCC 2013 Accepted papers and abstracts

(In order of submission)

[Show with abstracts]
  • The Correct Exponent for the Gotsman-Linial Conjecture
    Daniel Kane (Stanford University)

  • On Rigid Matrices and U-Polynomials
    Noga Alon (Tel-Aviv University), Gil Cohen (Weizmann Institute of Science)

  • Formulas are exponentially stronger than monotone circuits in non-commutative setting
    Pavel Hrubes (University of Washington, Seattle), Amir Yehudayoff (Technion-IIT, Israel)

  • Just a Pebble Game
    Siu Man Chan (UC Berkeley)

  • Quantum XOR Games
    Oded Regev (Courant Institute, New York University, Thomas Vidick (Massachusetts Institute of Technology)

  • Strong LTCs with inverse polylogarithmic rate and soundness
    Michael Viderman (Technion)

  • Two-message quantum interactive proofs and the quantum separability problem
    Patrick Hayden (School of Computer Science, McGill University), Kevin Milner (School of Computer Science, McGill University), Mark M. Wilde (School of Computer Science, McGill University)

  • How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
    Andris Ambainis (University of Latvia, Riga), Ronald de Wolf (CWI and University of Amsterdam)

  • Approaching the chasm at depth four
    Ankit Gupta (Microsoft Research, India), Pritish Kamath (Microsoft Research, India), Neeraj Kayal (Microsoft Research, India), Ramprasad Saptharishi (Chennai Mathematical Institute)

  • Shared Randomness and Quantum Communication in the Multi-Party Model
    Dmitry Gavinsky (NEC Laboratories America), Tsuyoshi Ito (NEC Laboratories America), Guoming Wang (NEC Laboratories America; Computer Science Division, UC Berkeley)

  • On the Power of Non-Adaptive Learning Graphs
    Aleksandrs Belovs (University of Latvia), Ansis Rosmanis (David R. Cheriton School of Computer Science and Institute for Quantum Computing, University of Waterloo.)

  • Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits
    Yasuhiro Takahashi (NTT Communication Science Laboratories), Seiichiro Tani (NTT Communication Science Laboratories)

  • A Derandomized Switching Lemma and an improved Derandomization of AC0
    Luca Trevisan (Stanford University), TongKe Xue (Stanford University)

  • Random Arithmetic Formulas can be Reconstructed Efficiently
    Ankit Gupta (Microsoft Research India), Neeraj Kayal (Microsoft Research India), Youming Qiao (Centre for Quantum Technologies, National University of Singapore)

  • Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover
    Sushant Sachdeva (Princeton University), Rishi Saket (IBM T. J. Watson Research Center)

  • Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle
    Albert Atserias (UPC, Barcelona), Moritz Müller (Kurt Gödel Research Center, Vienna), Sergi Oliva (UPC, Barcelona)

  • Superlinear lower bounds for multipass graph processing
    Venkatesan Guruswami (CMU), Krzysztof Onak (IBM Research)

  • On the Parameterized and Approximation Hardness of Metric Dimension
    Sepp Hartung (Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany), André Nichterlein (Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany)

  • Covering CSPs
    Irit Dinur (Weizmann Institute), Gillat Kol (Weizmann Institute)

  • The distinguishability of product distributions by read-once branching programs
    John Steinberger (Tsinghua University IIIS)

  • An $O({n^{{1\over 2}+\epsilon}})$ Space Algorithm for Directed Planar Reachability with Polynomial Running Time
    T. Imai (Tokyo Institute of Technology), K. Nakagawa (Tokyo Institute of Technology), A. Pavan (Iowa State University), N. V. Vinodchandran (University of Nebraska-Lincoln), O. Watanabe (Tokyo Institute of Technology)

  • Short lists with short programs in short time
    Bruno Bauwens (Université de Lorraine), Anton Makhlin (Moscow State University), Nikolay Vereshchagin (Moscow State University), Marius Zimand (Towson University)

  • Constructing hard functions from learning algorithms
    Adam Klivans (University of Texas at Austin), Pravesh Kothari (University of Texas at Austin), Igor C. Oliveira (Columbia University)

  • Approximating Boolean functions with depth-2 circuits
    Eric Blais (MIT), Li-Yang Tan (Columbia University)

  • Towards a Reverse Newman.s Theorem in Interactive Information Complexity
    Joshua Brody (Aarhus University), Harry Buhrman (CWI Amsterdam and University of Amsterdam), Michal Koucky (Mathematical Institute of Czech Academy of Sciences, Prague), Bruno Loff (CWI Amsterdam), Florian Speelman (CWI Amsterdam), Nikolay Vereshchagin (Moscow State University)

  • LS+ Lower Bounds from Pairwise Independence
    Madhur Tulsiani (TTI Chicago), Pratik Worah (University of Chicago)

  • On Medium-Uniformity and Circuit Lower Bounds
    Rahul Santhanam (University of Edinburgh), Ryan Williams (Stanford University)

  • Composition limits and separating examples for some Boolean function complexity measures
    Justin Gilmer (Department of Mathematics, Rutgers University), Michael Saks (Department of Mathematics, Rutgers University), Srikanth Srinivasan (Department of Mathematics, IIT Bombay)

  • On the Lattice Smoothing Parameter Problem
    Kai-Min Chung (Cornell University), Daniel Dadush (New York University), Feng-Hao Liu (Brown University), Chris Peikert (Georgia Institute of Technology)