CCC 2015 June 17-19, 2015 - Portland, Oregon, USA

30th Conference on Computational Complexity (CCC 2015)



David Zuckerman (Ed.)
ISBN 978-3-939897-81-1, LIPICS Vol. 33 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 16 MB)
Search Publication Server

Authors
  • Applebaum, Benny
  • Artemenko, Sergei
  • Bera, Suman K.
  • Bhangale, Amey
  • Bhowmick, Abhishek
  • Chakrabarti, Amit
  • Chung, Kai-Min
  • Cormode, Graham
  • Galesi, Nicola
  • Goldreich, Oded
  • Gurjar, Rohit
  • Gur, Tom
  • Guruswami, Venkatesan
  • Harsha, Prahladh
  • Haviv, Ishay
  • Hirahara, Shuichi
  • Hrubes, Pavel
  • Kane, Daniel M.
  • Kayal, Neeraj
  • Kobayashi, Hirotada
  • Komargodski, Ilan
  • Korwar, Arpita
  • Lauria, Massimo
  • Le Gall, Francois
  • Li, Fu
  • Lin, Cedric Yen-Yu
  • Lin, Han-Hsuan
  • Lovett, Shachar
  • McGregor, Andrew
  • Miksa, Mladen
  • Murray, Cody D.
  • Natarajan Ramamoorthy, Sivaramakrishnan
  • Nishimura, Harumichi
  • Nordström, Jakob
  • Oliveira, Igor Carboni
  • Oliveira, Rafael
  • Pudlák, Pavel
  • Rao, Anup
  • Regev, Oded
  • Rossman, Benjamin
  • Saha, Chandan
  • Samorodnitsky, Alex
  • Santhanam, Rahul
  • Saxena, Nitin
  • Servedio, Rocco A.
  • Shaltiel, Ronen
  • Shkredov, Ilya
  • Shpilka, Amir
  • Tan, Li-Yang
  • Thaler, Justin
  • Thapen, Neil
  • Thierauf, Thomas
  • Tzameret, Iddo
  • Varma, Girish
  • Velingker, Ameya
  • Venkatasubramanian, Suresh
  • Viola, Emanuele
  • Volk, Ben Lee
  • Wang, Zhengyu
  • Wigderson, Avi
  • Williams, R. Ryan
  • Wright, John
  • Wu, Xiaodi
  • Yang, Guang
  • Yehudayoff, Amir
  • Yekhanin, Sergey
  • Yuen, Henry
  • Zuckerman, David
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Zuckerman, David

    Abstract | Document (352 KB) | BibTeX

    Strong Locally Testable Codes with Relaxed Local Decoders
    Authors: Goldreich, Oded ; Gur, Tom ; Komargodski, Ilan

    Abstract | Document (826 KB) | BibTeX

    An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets
    Authors: Guruswami, Venkatesan ; Velingker, Ameya

    Abstract | Document (536 KB) | BibTeX

    The List-Decoding Size of Fourier-Sparse Boolean Functions
    Authors: Haviv, Ishay ; Regev, Oded

    Abstract | Document (450 KB) | BibTeX

    Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds
    Authors: Bhowmick, Abhishek ; Lovett, Shachar

    Abstract | Document (483 KB) | BibTeX

    Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness
    Authors: Rao, Anup ; Yehudayoff, Amir

    Abstract | Document (546 KB) | BibTeX

    How to Compress Asymmetric Communication
    Authors: Natarajan Ramamoorthy, Sivaramakrishnan ; Rao, Anup

    Abstract | Document (561 KB) | BibTeX

    Majority is Incompressible by AC^0[p] Circuits
    Authors: Oliveira, Igor Carboni ; Santhanam, Rahul

    Abstract | Document (768 KB) | BibTeX

    Lower Bounds for Depth Three Arithmetic Circuits with Small Bottom Fanin
    Authors: Kayal, Neeraj ; Saha, Chandan

    Abstract | Document (719 KB) | BibTeX

    A Depth-Five Lower Bound for Iterated Matrix Multiplication
    Authors: Bera, Suman K. ; Chakrabarti, Amit

    Abstract | Document (476 KB) | BibTeX

    Factors of Low Individual Degree Polynomials
    Authors: Oliveira, Rafael

    Abstract | Document (561 KB) | BibTeX

    Verifiable Stream Computation and Arthur–Merlin Communication
    Authors: Chakrabarti, Amit ; Cormode, Graham ; McGregor, Andrew ; Thaler, Justin ; Venkatasubramanian, Suresh

    Abstract | Document (707 KB) | BibTeX

    Identifying an Honest EXP^NP Oracle Among Many
    Authors: Hirahara, Shuichi

    Abstract | Document (546 KB) | BibTeX

    Adaptivity Helps for Testing Juntas
    Authors: Servedio, Rocco A. ; Tan, Li-Yang ; Wright, John

    Abstract | Document (542 KB) | BibTeX

    A Characterization of Hard-to-cover CSPs
    Authors: Bhangale, Amey ; Harsha, Prahladh ; Varma, Girish

    Abstract | Document (668 KB) | BibTeX

    Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
    Authors: Oliveira, Rafael ; Shpilka, Amir ; Volk, Ben Lee

    Abstract | Document (598 KB) | BibTeX

    Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs
    Authors: Gurjar, Rohit ; Korwar, Arpita ; Saxena, Nitin ; Thierauf, Thomas

    Abstract | Document (592 KB) | BibTeX

    Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity
    Authors: Samorodnitsky, Alex ; Shkredov, Ilya ; Yekhanin, Sergey

    Abstract | Document (507 KB) | BibTeX

    On the (Non) NP-Hardness of Computing Circuit Complexity
    Authors: Murray, Cody D. ; Williams, R. Ryan

    Abstract | Document (533 KB) | BibTeX

    Circuits with Medium Fan-In
    Authors: Hrubes, Pavel ; Rao, Anup

    Abstract | Document (489 KB) | BibTeX

    Correlation Bounds Against Monotone NC^1
    Authors: Rossman, Benjamin

    Abstract | Document (569 KB) | BibTeX

    Non-Commutative Formulas and Frege Lower Bounds: a New Characterization of Propositional Proofs
    Authors: Li, Fu ; Tzameret, Iddo ; Wang, Zhengyu

    Abstract | Document (523 KB) | BibTeX

    The Space Complexity of Cutting Planes Refutations
    Authors: Galesi, Nicola ; Pudlák, Pavel ; Thapen, Neil

    Abstract | Document (462 KB) | BibTeX

    Tight Size-Degree Bounds for Sums-of-Squares Proofs
    Authors: Lauria, Massimo ; Nordström, Jakob

    Abstract | Document (482 KB) | BibTeX

    A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds
    Authors: Miksa, Mladen ; Nordström, Jakob

    Abstract | Document (544 KB) | BibTeX

    Generalized Quantum Arthur-Merlin Games
    Authors: Kobayashi, Hirotada ; Le Gall, Francois ; Nishimura, Harumichi

    Abstract | Document (598 KB) | BibTeX

    Parallel Repetition for Entangled k-player Games via Fast Quantum Search
    Authors: Chung, Kai-Min ; Wu, Xiaodi ; Yuen, Henry

    Abstract | Document (603 KB) | BibTeX

    Upper Bounds on Quantum Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester
    Authors: Lin, Cedric Yen-Yu ; Lin, Han-Hsuan

    Abstract | Document (589 KB) | BibTeX

    A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting
    Authors: Kane, Daniel M.

    Abstract | Document (485 KB) | BibTeX

    Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract)
    Authors: Applebaum, Benny ; Artemenko, Sergei ; Shaltiel, Ronen ; Yang, Guang

    Abstract | Document (564 KB) | BibTeX

    On Randomness Extraction in AC0
    Authors: Goldreich, Oded ; Viola, Emanuele ; Wigderson, Avi

    Abstract | Document (1,065 KB) | BibTeX

    		  



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