CCC 2016 May 29 to June 1, 2016 - Tokyo, Japan

31st Conference on Computational Complexity (CCC 2016)



Ran Raz (Ed.)
ISBN 978-3-95977-008-8, LIPICS Vol. 50 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 19 MB)
Search Publication Server

Authors
  • Aaronson, Scott
  • Ai, Yuqing
  • Ambainis, Andris
  • Anderson, Matthew
  • Artemenko, Sergei
  • Ben-David, Shalev
  • Bhattacharyya, Arnab
  • Bouland, Adam
  • Brakensiek, Joshua
  • Carmosino, Marco L.
  • Chattopadhyay, Eshan
  • Chen, Ruiwen
  • Cohen, Gil
  • de Beaudrap, Niel
  • Deng, Xiaotie
  • de Wolf, Ronald
  • Dinur, Irit
  • Edmonds, Jack R.
  • Feng, Zhe
  • Filmus, Yuval
  • Forbes, Michael A.
  • Fortnow, Lance
  • Gharibian, Sevag
  • Göös, Mika
  • Gopalan, Parikshit
  • Gopi, Sivakanth
  • Gurjar, Rohit
  • Guruswami, Venkatesan
  • Harrow, Aram
  • Hirahara, Shuichi
  • Hu, Wei
  • Impagliazzo, Russell
  • Iraids, Janis
  • Jayram, T. S.
  • Kabanets, Valentine
  • Kim, John Y.
  • Kindler, Guy
  • Kokainis, Martins
  • Kolokolova, Antonina
  • Kopparty, Swastik
  • Korwar, Arpita
  • Kothari, Robin
  • Kumar, Mrinal
  • Lee, Troy
  • Liu, Zhengyang
  • Li, Yi
  • Mancinska, Laura
  • Meir, Or
  • Mossel, Elchanan
  • Natarajan, Anand V.
  • O'Donnell, Ryan
  • Prakash, Anupam
  • Qi, Qi
  • Radhakrishnan, Jaikumar
  • Raz, Ran
  • Santhanam, Rahul
  • Saptharishi, Ramprasad
  • Saraf, Shubhangi
  • Saxena, Nitin
  • Servedio, Rocco A.
  • Shaltiel, Ronen
  • Shpilka, Amir
  • Sinha, Gaurav
  • Smotrovs, Juris
  • Srinivasan, Srikanth
  • Tzameret, Iddo
  • Vishnoi, Nisheeth K.
  • Volk, Ben Lee
  • Watanabe, Osamu
  • Wigderson, Avi
  • Williams, Richard Ryan
  • Wimmer, Karl
  • Woodruff, David P.
  • Wu, Xiaodi
  • Xu, Zeying
  • Yuen, Henry
  • Zhang, Xue
  • Zhao, Yu
  • Zuckerman, David
    		•

    		  
    Front Matter, Table of Contents, Preface, Awards, Conference Organization, External Reviewers
    Authors: Raz, Ran

    Abstract | Document (357 KB) | BibTeX

    Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
    Authors: Chen, Ruiwen ; Santhanam, Rahul ; Srinivasan, Srikanth

    Abstract | Document (678 KB) | BibTeX

    Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
    Authors: Williams, Richard Ryan

    Abstract | Document (538 KB) | BibTeX

    Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity
    Authors: Dinur, Irit ; Meir, Or

    Abstract | Document (803 KB) | BibTeX

    Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions
    Authors: Ambainis, Andris ; Kokainis, Martins ; Kothari, Robin

    Abstract | Document (542 KB) | BibTeX

    A Composition Theorem for Conical Juntas
    Authors: Göös, Mika ; Jayram, T. S.

    Abstract | Document (655 KB) | BibTeX

    Tight Bounds for Communication-Assisted Agreement Distillation
    Authors: Guruswami, Venkatesan ; Radhakrishnan, Jaikumar

    Abstract | Document (556 KB) | BibTeX

    New Extractors for Interleaved Sources
    Authors: Chattopadhyay, Eshan ; Zuckerman, David

    Abstract | Document (653 KB) | BibTeX

    Non-Malleable Extractors - New Tools and Improved Constructions
    Authors: Cohen, Gil

    Abstract | Document (598 KB) | BibTeX

    Pseudorandomness When the Odds are Against You
    Authors: Artemenko, Sergei ; Impagliazzo, Russell ; Kabanets, Valentine ; Shaltiel, Ronen

    Abstract | Document (724 KB) | BibTeX

    Learning Algorithms from Natural Proofs
    Authors: Carmosino, Marco L. ; Impagliazzo, Russell ; Kabanets, Valentine ; Kolokolova, Antonina

    Abstract | Document (715 KB) | BibTeX

    Decoding Reed-Muller Codes Over Product Sets
    Authors: Kim, John Y. ; Kopparty, Swastik

    Abstract | Document (565 KB) | BibTeX

    Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs
    Authors: Bhattacharyya, Arnab ; Gopi, Sivakanth

    Abstract | Document (569 KB) | BibTeX

    Degree and Sensitivity: Tails of Two Distributions
    Authors: Gopalan, Parikshit ; Servedio, Rocco A. ; Wigderson, Avi

    Abstract | Document (660 KB) | BibTeX

    New Hardness Results for Graph and Hypergraph Colorings
    Authors: Brakensiek, Joshua ; Guruswami, Venkatesan

    Abstract | Document (639 KB) | BibTeX

    Invariance Principle on the Slice
    Authors: Filmus, Yuval ; Kindler, Guy ; Mossel, Elchanan ; Wimmer, Karl

    Abstract | Document (422 KB) | BibTeX

    Harmonicity and Invariance on Slices of the Boolean Cube
    Authors: Filmus, Yuval ; Mossel, Elchanan

    Abstract | Document (514 KB) | BibTeX

    On the Sum-of-Squares Degree of Symmetric Quadratic Functions
    Authors: Lee, Troy ; Prakash, Anupam ; de Wolf, Ronald ; Yuen, Henry

    Abstract | Document (699 KB) | BibTeX

    Limits of Minimum Circuit Size Problem as Oracle
    Authors: Hirahara, Shuichi ; Watanabe, Osamu

    Abstract | Document (582 KB) | BibTeX

    New Non-Uniform Lower Bounds for Uniform Classes
    Authors: Fortnow, Lance ; Santhanam, Rahul

    Abstract | Document (506 KB) | BibTeX

    New Characterizations in Turnstile Streams with Applications
    Authors: Ai, Yuqing ; Hu, Wei ; Li, Yi ; Woodruff, David P.

    Abstract | Document (605 KB) | BibTeX

    Evolution and Computation (Invited Talk)
    Authors: Vishnoi, Nisheeth K.

    Abstract | Document (226 KB) | BibTeX

    Tight SoS-Degree Bounds for Approximate Nash Equilibria
    Authors: Harrow, Aram ; Natarajan, Anand V. ; Wu, Xiaodi

    Abstract | Document (584 KB) | BibTeX

    Understanding PPA-Completeness
    Authors: Deng, Xiaotie ; Edmonds, Jack R. ; Feng, Zhe ; Liu, Zhengyang ; Qi, Qi ; Xu, Zeying

    Abstract | Document (905 KB) | BibTeX

    Polynomial Bounds for Decoupling, with Applications
    Authors: O'Donnell, Ryan ; Zhao, Yu

    Abstract | Document (539 KB) | BibTeX

    Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
    Authors: Aaronson, Scott ; Ambainis, Andris ; Iraids, Janis ; Kokainis, Martins ; Smotrovs, Juris

    Abstract | Document (570 KB) | BibTeX

    Sculpting Quantum Speedups
    Authors: Aaronson, Scott ; Ben-David, Shalev

    Abstract | Document (604 KB) | BibTeX

    A Linear Time Algorithm for Quantum 2-SAT
    Authors: de Beaudrap, Niel ; Gharibian, Sevag

    Abstract | Document (608 KB) | BibTeX

    Complexity Classification of Two-Qubit Commuting Hamiltonians
    Authors: Bouland, Adam ; Mancinska, Laura ; Zhang, Xue

    Abstract | Document (673 KB) | BibTeX

    Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs
    Authors: Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin

    Abstract | Document (545 KB) | BibTeX

    Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
    Authors: Anderson, Matthew ; Forbes, Michael A. ; Saptharishi, Ramprasad ; Shpilka, Amir ; Volk, Ben Lee

    Abstract | Document (638 KB) | BibTeX

    Reconstruction of Real Depth-3 Circuits with Top Fan-In 2
    Authors: Sinha, Gaurav

    Abstract | Document (1,026 KB) | BibTeX

    Proof Complexity Lower Bounds from Algebraic Circuit Complexity
    Authors: Forbes, Michael A. ; Shpilka, Amir ; Tzameret, Iddo ; Wigderson, Avi

    Abstract | Document (559 KB) | BibTeX

    Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity
    Authors: Forbes, Michael A. ; Kumar, Mrinal ; Saptharishi, Ramprasad

    Abstract | Document (620 KB) | BibTeX

    Arithmetic Circuits with Locally Low Algebraic Rank
    Authors: Kumar, Mrinal ; Saraf, Shubhangi

    Abstract | Document (675 KB) | BibTeX

    Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing
    Authors: Kumar, Mrinal ; Saraf, Shubhangi

    Abstract | Document (669 KB) | BibTeX

    		  



    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI