Portal - CCC 2023

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

Arunachalam, Srinivasan

Livni Navon, Inbal Rachel

Mocelin Sdroievski, Nicollas

Sengupta, Akash Kumar

van Melkebeek, Dieter

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

38th Computational Complexity Conference (CCC 2023)