CCC 2023 July 17-20, 2023, Warwick, UK

38th Computational Complexity Conference (CCC 2023)



Amnon Ta-Shma (Ed.)
ISBN 978-3-95977-282-2, LIPICS Vol. 264 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 14 MB)
Search Publication Server

Authors
  • Abdolazimi, Dorna
  • Aharonov, Dorit
  • Alman, Josh
  • Ambainis, Andris
  • Arunachalam, Srinivasan
  • Austrin, Per
  • Belovs, Aleksandrs
  • Bittel, Lennart
  • Block, Alexander R.
  • Blocki, Jeremiah
  • Błasiok, Jarosław
  • Cavalar, Bruno P.
  • Chatterjee, Abhranil
  • Chatterjee, Prerona
  • Chattopadhyay, Eshan
  • Chen, Xi
  • Cheng, Kuan
  • Cheung, Tsun-Ming
  • Chia, Nai-Hui
  • Chung, Kai-Min
  • Cohen, Gil
  • Cohen, Itay
  • d'Orsi, Tommaso
  • Davis, Ben
  • Doron, Dean
  • Fournier, Hervé
  • Galesi, Nicola
  • Garg, Abhibhav
  • Gharibian, Sevag
  • Ghosh, Sumanta
  • Girish, Uma
  • Goldberg, Halley
  • Grigorescu, Elena
  • Grochow, Joshua A.
  • Gurjar, Rohit
  • Harsha, Prahladh
  • Hatami, Hamed
  • Hirahara, Shuichi
  • Hosseini, Kaave
  • Hrubeš, Pavel
  • Hsieh, Yao-Ching
  • Hu, Lunjia
  • Impagliazzo, Russell
  • Irani, Sandy
  • Ivanov, Peter
  • Kabanets, Valentine
  • Kliesch, Martin
  • Kumar, Vinayak M.
  • Kunisky, Dmitriy
  • Kush, Deepanshu
  • Li, Xin
  • Li, Yuhao
  • Liao, Jyun-Jie
  • Limaye, Nutan
  • Lin, Han-Hsuan
  • Lin, Yao-Ting
  • Liu, Yanyi
  • Livni Navon, Inbal Rachel
  • Lu, Zhenjian
  • Malod, Guillaume
  • Mocelin Sdroievski, Nicollas
  • Molli, Tulasimohan
  • Mouli, Sasank
  • Natarajan, Anand
  • Nirkhe, Chinmay
  • Oliveira, Igor C.
  • Oliveira, Rafael
  • Oveis Gharan, Shayan
  • Pass, Rafael
  • Pavlovic, Liam
  • Peleg, Shir
  • Pitassi, Toniann
  • Raj, Roshan
  • Reingold, Omer
  • Ren, Hanlin
  • Risse, Kilian
  • Robere, Robert
  • Santhanam, Rahul
  • Saraf, Shubhangi
  • Sengupta, Akash Kumar
  • Shankar, Ashutosh
  • She, Adrian
  • Shen, Yu-Ching
  • Shirley, Morgan
  • Srinivasan, Srikanth
  • Ta-Shma, Amnon
  • Tavenas, Sébastien
  • Tell, Roei
  • Trevisan, Luca
  • van Melkebeek, Dieter
  • Viola, Emanuele
  • Yannakakis, Mihalis
  • Yu, Xifan
  • Zheng, Yu
  • Zhu, Minshen
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Ta-Shma, Amnon

    Abstract | Document (493 KB) | BibTeX

    Separation of the Factorization Norm and Randomized Communication Complexity
    Authors: Cheung, Tsun-Ming ; Hatami, Hamed ; Hosseini, Kaave ; Shirley, Morgan

    Abstract | Document (793 KB) | BibTeX

    Border Complexity of Symbolic Determinant Under Rank One Restriction
    Authors: Chatterjee, Abhranil ; Ghosh, Sumanta ; Gurjar, Rohit ; Raj, Roshan

    Abstract | Document (706 KB) | BibTeX

    On Correlation Bounds Against Polynomials
    Authors: Ivanov, Peter ; Pavlovic, Liam ; Viola, Emanuele

    Abstract | Document (863 KB) | BibTeX

    On the Algebraic Proof Complexity of Tensor Isomorphism
    Authors: Galesi, Nicola ; Grochow, Joshua A. ; Pitassi, Toniann ; She, Adrian

    Abstract | Document (1,043 KB) | BibTeX

    Generative Models of Huge Objects
    Authors: Hu, Lunjia ; Livni Navon, Inbal Rachel ; Reingold, Omer

    Abstract | Document (678 KB) | BibTeX

    Bounded Relativization
    Authors: Hirahara, Shuichi ; Lu, Zhenjian ; Ren, Hanlin

    Abstract | Document (1,257 KB) | BibTeX

    Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields
    Authors: Impagliazzo, Russell ; Mouli, Sasank ; Pitassi, Toniann

    Abstract | Document (835 KB) | BibTeX

    Spectral Expanding Expanders
    Authors: Cohen, Gil ; Cohen, Itay

    Abstract | Document (751 KB) | BibTeX

    Hardness Against Linear Branching Programs and More
    Authors: Chattopadhyay, Eshan ; Liao, Jyun-Jie

    Abstract | Document (939 KB) | BibTeX

    An Improved Trickle down Theorem for Partite Complexes
    Authors: Abdolazimi, Dorna ; Oveis Gharan, Shayan

    Abstract | Document (723 KB) | BibTeX

    Derandomization with Minimal Memory Footprint
    Authors: Doron, Dean ; Tell, Roei

    Abstract | Document (821 KB) | BibTeX

    Improved Learning from Kolmogorov Complexity
    Authors: Goldberg, Halley ; Kabanets, Valentine

    Abstract | Document (881 KB) | BibTeX

    New Lower Bounds Against Homogeneous Non-Commutative Circuits
    Authors: Chatterjee, Prerona ; Hrubeš, Pavel

    Abstract | Document (700 KB) | BibTeX

    On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
    Authors: Block, Alexander R. ; Blocki, Jeremiah ; Cheng, Kuan ; Grigorescu, Elena ; Li, Xin ; Zheng, Yu ; Zhu, Minshen

    Abstract | Document (888 KB) | BibTeX

    Near-Optimal Set-Multilinear Formula Lower Bounds
    Authors: Kush, Deepanshu ; Saraf, Shubhangi

    Abstract | Document (948 KB) | BibTeX

    Matrix Multiplication and Number on the Forehead Communication
    Authors: Alman, Josh ; Błasiok, Jarosław

    Abstract | Document (771 KB) | BibTeX

    Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols
    Authors: van Melkebeek, Dieter ; Mocelin Sdroievski, Nicollas

    Abstract | Document (921 KB) | BibTeX

    Tight Correlation Bounds for Circuits Between AC0 and TC0
    Authors: Kumar, Vinayak M.

    Abstract | Document (1,057 KB) | BibTeX

    Criticality of AC⁰-Formulae
    Authors: Harsha, Prahladh ; Molli, Tulasimohan ; Shankar, Ashutosh

    Abstract | Document (2,051 KB) | BibTeX

    Radical Sylvester-Gallai Theorem for Tuples of Quadratics
    Authors: Garg, Abhibhav ; Oliveira, Rafael ; Peleg, Shir ; Sengupta, Akash Kumar

    Abstract | Document (926 KB) | BibTeX

    Reducing Tarski to Unique Tarski (In the Black-Box Model)
    Authors: Chen, Xi ; Li, Yuhao ; Yannakakis, Mihalis

    Abstract | Document (1,725 KB) | BibTeX

    A Distribution Testing Oracle Separating QMA and QCMA
    Authors: Natarajan, Anand ; Nirkhe, Chinmay

    Abstract | Document (978 KB) | BibTeX

    Translationally Invariant Constraint Optimization Problems
    Authors: Aharonov, Dorit ; Irani, Sandy

    Abstract | Document (758 KB) | BibTeX

    An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
    Authors: Ambainis, Andris ; Belovs, Aleksandrs

    Abstract | Document (667 KB) | BibTeX

    Trade-Offs Between Entanglement and Communication
    Authors: Arunachalam, Srinivasan ; Girish, Uma

    Abstract | Document (892 KB) | BibTeX

    New Sampling Lower Bounds via the Separator
    Authors: Viola, Emanuele

    Abstract | Document (785 KB) | BibTeX

    A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
    Authors: d'Orsi, Tommaso ; Trevisan, Luca

    Abstract | Document (686 KB) | BibTeX

    Towards Optimal Depth-Reductions for Algebraic Formulas
    Authors: Fournier, Hervé ; Limaye, Nutan ; Malod, Guillaume ; Srinivasan, Srikanth ; Tavenas, Sébastien

    Abstract | Document (782 KB) | BibTeX

    Constant-Depth Circuits vs. Monotone Circuits
    Authors: Cavalar, Bruno P. ; Oliveira, Igor C.

    Abstract | Document (1,121 KB) | BibTeX

    A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph
    Authors: Kunisky, Dmitriy ; Yu, Xifan

    Abstract | Document (1,227 KB) | BibTeX

    Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem
    Authors: Austrin, Per ; Risse, Kilian

    Abstract | Document (979 KB) | BibTeX

    Leakage-Resilient Hardness vs Randomness
    Authors: Liu, Yanyi ; Pass, Rafael

    Abstract | Document (800 KB) | BibTeX

    On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation
    Authors: Chia, Nai-Hui ; Chung, Kai-Min ; Hsieh, Yao-Ching ; Lin, Han-Hsuan ; Lin, Yao-Ting ; Shen, Yu-Ching

    Abstract | Document (1,118 KB) | BibTeX

    The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate
    Authors: Bittel, Lennart ; Gharibian, Sevag ; Kliesch, Martin

    Abstract | Document (956 KB) | BibTeX

    An Algorithmic Approach to Uniform Lower Bounds
    Authors: Santhanam, Rahul

    Abstract | Document (819 KB) | BibTeX

    Colourful TFNP and Propositional Proofs
    Authors: Davis, Ben ; Robere, Robert

    Abstract | Document (823 KB) | BibTeX

    		  



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