CCC 2018 June 22-24, 2018 - San Diego, CA, USA

33rd Computational Complexity Conference (CCC 2018)



Rocco A. Servedio (Ed.)
ISBN 978-3-95977-069-9, LIPICS Vol. 102 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 15 MB)
Search Publication Server

Authors
  • Alon, Noga
  • Ben-Aroya, Avraham
  • Ben-Eliezer, Omri
  • Ben-Sasson, Eli
  • Bouland, Adam
  • Buss, Sam
  • Carmosino, Marco L.
  • Chattopadhyay, Eshan
  • Chen, Lijie
  • Chen, Yi-Hsiu
  • Chiesa, Alessandro
  • Chou, Chi-Ning
  • Doron, Dean
  • Edmonds, Jeff
  • Fischer, Eldar
  • Fitzsimons, Joseph F.
  • Fleischer, Lukas
  • Ghazi, Badih
  • Göös, Mika
  • Grier, Daniel
  • Guo, Zeyu
  • Guruswami, Venkatesan
  • Hatami, Pooya
  • Hirahara, Shuichi
  • Hosseini, Kaave
  • Impagliazzo, Russell
  • Itsykson, Dmitry
  • Kabanets, Valentine
  • Kamath, Pritish
  • Kane, Daniel
  • Kannan, Sampath
  • Knop, Alexander
  • Koh, Dax Enshan
  • Kopparty, Swastik
  • Kumar, Mrinal
  • Lingas, Andrzej
  • Li, Xin
  • Lovett, Shachar
  • Manohar, Peter
  • Medabalimi, Venkatesh
  • Mihajlin, Ivan
  • Mossel, Elchanan
  • Natarajan, Anand
  • Natarajan Ramamoorthy, Sivaramakrishnan
  • Oliveira, Igor C.
  • Pitassi, Toniann
  • Raghavendra, Prasad
  • Rao, Anup
  • Rao, Sankeerth
  • Reingold, Omer
  • Resch, Nicolas
  • Rothblum, Guy N.
  • Rothblum, Ron D.
  • Santhanam, Rahul
  • Sanyal, Swagato
  • Saraf, Shubhangi
  • Saxena, Nitin
  • Schaeffer, Luke
  • Servedio, Rocco A.
  • Shinkar, Igor
  • Sinhababu, Amit
  • Sokolov, Dmitry
  • Solomon, Noam
  • Ta-Shma, Amnon
  • Vadhan, Salil P.
  • Vidick, Thomas
  • Volk, Ben Lee
  • Volkovich, Ilya
  • Watson, Thomas
  • Williams, Richard Ryan
  • Xing, Chaoping
  • Yaroslavtsev, Grigory
  • Zhang, Jiapeng
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Servedio, Rocco A.

    Abstract | Document (365 KB) | BibTeX

    Pseudorandom Generators from Polarizing Random Walks
    Authors: Chattopadhyay, Eshan ; Hatami, Pooya ; Hosseini, Kaave ; Lovett, Shachar

    Abstract | Document (544 KB) | BibTeX

    A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n
    Authors: Kane, Daniel ; Rao, Sankeerth

    Abstract | Document (613 KB) | BibTeX

    A New Approach for Constructing Low-Error, Two-Source Extractors
    Authors: Ben-Aroya, Avraham ; Chattopadhyay, Eshan ; Doron, Dean ; Li, Xin ; Ta-Shma, Amnon

    Abstract | Document (559 KB) | BibTeX

    Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs
    Authors: Guruswami, Venkatesan ; Resch, Nicolas ; Xing, Chaoping

    Abstract | Document (533 KB) | BibTeX

    NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits
    Authors: Hirahara, Shuichi ; Oliveira, Igor C. ; Santhanam, Rahul

    Abstract | Document (706 KB) | BibTeX

    Limits on Representing Boolean Functions by Linear Combinations of Simple Functions: Thresholds, ReLUs, and Low-Degree Polynomials
    Authors: Williams, Richard Ryan

    Abstract | Document (579 KB) | BibTeX

    The Power of Natural Properties as Oracles
    Authors: Impagliazzo, Russell ; Kabanets, Valentine ; Volkovich, Ilya

    Abstract | Document (568 KB) | BibTeX

    Linear Sketching over F_2
    Authors: Kannan, Sampath ; Mossel, Elchanan ; Sanyal, Swagato ; Yaroslavtsev, Grigory

    Abstract | Document (797 KB) | BibTeX

    Communication Complexity with Small Advantage
    Authors: Watson, Thomas

    Abstract | Document (573 KB) | BibTeX

    Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity
    Authors: Guo, Zeyu ; Saxena, Nitin ; Sinhababu, Amit

    Abstract | Document (584 KB) | BibTeX

    Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
    Authors: Alon, Noga ; Kumar, Mrinal ; Volk, Ben Lee

    Abstract | Document (516 KB) | BibTeX

    Hardness Amplification for Non-Commutative Arithmetic Circuits
    Authors: Carmosino, Marco L. ; Impagliazzo, Russell ; Lovett, Shachar ; Mihajlin, Ivan

    Abstract | Document (536 KB) | BibTeX

    Hardness vs Randomness for Bounded Depth Arithmetic Circuits
    Authors: Chou, Chi-Ning ; Kumar, Mrinal ; Solomon, Noam

    Abstract | Document (513 KB) | BibTeX

    On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
    Authors: Chen, Lijie

    Abstract | Document (815 KB) | BibTeX

    Hardness of Function Composition for Semantic Read once Branching Programs
    Authors: Edmonds, Jeff ; Medabalimi, Venkatesh ; Pitassi, Toniann

    Abstract | Document (583 KB) | BibTeX

    Reordering Rule Makes OBDD Proof Systems Stronger
    Authors: Buss, Sam ; Itsykson, Dmitry ; Knop, Alexander ; Sokolov, Dmitry

    Abstract | Document (556 KB) | BibTeX

    Testing Linearity against Non-Signaling Strategies
    Authors: Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

    Abstract | Document (666 KB) | BibTeX

    Earthmover Resilience and Testing in Ordered Structures
    Authors: Ben-Eliezer, Omri ; Fischer, Eldar

    Abstract | Document (645 KB) | BibTeX

    New Hardness Results for the Permanent Using Linear Optics
    Authors: Grier, Daniel ; Schaeffer, Luke

    Abstract | Document (703 KB) | BibTeX

    Retracted: Two-Player Entangled Games are NP-Hard
    Authors: Natarajan, Anand ; Vidick, Thomas

    Abstract | Document (614 KB) | BibTeX

    Complexity Classification of Conjugated Clifford Circuits
    Authors: Bouland, Adam ; Fitzsimons, Joseph F. ; Koh, Dax Enshan

    Abstract | Document (732 KB) | BibTeX

    Efficient Batch Verification for UP
    Authors: Reingold, Omer ; Rothblum, Guy N. ; Rothblum, Ron D.

    Abstract | Document (690 KB) | BibTeX

    A Tight Lower Bound for Entropy Flattening
    Authors: Chen, Yi-Hsiu ; Göös, Mika ; Vadhan, Salil P. ; Zhang, Jiapeng

    Abstract | Document (659 KB) | BibTeX

    Worst-Case to Average Case Reductions for the Distance to a Code
    Authors: Ben-Sasson, Eli ; Kopparty, Swastik ; Saraf, Shubhangi

    Abstract | Document (581 KB) | BibTeX

    On the Complexity of the Cayley Semigroup Membership Problem
    Authors: Fleischer, Lukas

    Abstract | Document (487 KB) | BibTeX

    Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth
    Authors: Lingas, Andrzej

    Abstract | Document (382 KB) | BibTeX

    Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
    Authors: Natarajan Ramamoorthy, Sivaramakrishnan ; Rao, Anup

    Abstract | Document (681 KB) | BibTeX

    Dimension Reduction for Polynomials over Gaussian Space and Applications
    Authors: Ghazi, Badih ; Kamath, Pritish ; Raghavendra, Prasad

    Abstract | Document (793 KB) | BibTeX

    		  



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