CCC23 Accepted Papers
Separation of the factorization norm and randomized communication complexity
Border Complexity of Symbolic Determinant under Rank One Restriction
On correlation bounds against polynomials
On the algebraic proof complexity of Tensor Isomorphism
Generative Models of Huge Objects
Bounded Relativization
Lower bounds for Polynomial Calculus with extension variables over finite fields
Spectral Expanding Expanders
Hardness against Linear Branching Programs and More
An Improved Trickle-Down Theorem for Partite Complexes
Derandomization with Minimal Memory Footprint
Improved Learning from Kolmogorov Complexity
New Lower Bounds against Homogeneous Non-Commutative Circuits
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors
Near-Optimal Set-Multilinear Formula Lower Bounds
Matrix Multiplication and Number On the Forehead Communication
Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols
Tight Correlation Bounds for Circuits Between AC0 and TC0
Criticality of AC^0-Formulae
Radical Sylvester-Gallai Theorem for Tuples of Quadratics
Reducing Tarski to Unique Tarski (in the Black-box Model)
A randomized classical oracle separating QMA and QCMA
Translationally Invariant Constraint Optimization Problems
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Trade-offs between Entanglement and Communication
New sampling lower bounds via the separator
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
Towards Optimal Depth-Reductions for Algebraic Formulas
Constant-Depth Circuits vs. Monotone Circuits
A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem
Leakage-Resilient Hardness v.s. Randomness
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation
The optimal depth of variational quantum algorithms is QCMA-hard to approximate
An Algorithmic Approach to Uniform Lower Bounds
On Coloured TFNP and Propositional Proof Systems