| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization.  |
CCC  |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Deepanshu Kush, Shubhangi Saraf |
Near-Optimal Set-Multilinear Formula Lower Bounds. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Kilian Risse |
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Prerona Chatterjee, Pavel Hrubes |
New Lower Bounds Against Homogeneous Non-Commutative Circuits. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Itay Cohen 0003 |
Spectral Expanding Expanders. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li 0006, Yu Zheng 0014, Minshen Zhu |
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yanyi Liu, Rafael Pass |
Leakage-Resilient Hardness vs Randomness. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Andris Ambainis, Aleksandrs Belovs |
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dieter van Melkebeek, Nicollas M. Sdroievski |
Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Srinivasan Arunachalam, Uma Girish |
Trade-Offs Between Entanglement and Communication. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitriy Kunisky, Xifan Yu |
A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Ivanov, Liam Pavlovic, Emanuele Viola |
On Correlation Bounds Against Polynomials. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She |
On the Algebraic Proof Complexity of Tensor Isomorphism. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Sasank Mouli, Toniann Pitassi |
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Pasqualotto Cavalar, Igor C. Oliveira |
Constant-Depth Circuits vs. Monotone Circuits. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen |
On the Impossibility of General Parallel Fast-Forwarding of Hamiltonian Simulation. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Tommaso d'Orsi, Luca Trevisan |
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorna Abdolazimi, Shayan Oveis Gharan |
An Improved Trickle down Theorem for Partite Complexes. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Natarajan, Chinmay Nirkhe |
A Distribution Testing Oracle Separating QMA and QCMA. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan 0001, Sébastien Tavenas |
Towards Optimal Depth-Reductions for Algebraic Formulas. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dean Doron, Roei Tell |
Derandomization with Minimal Memory Footprint. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Amnon Ta-Shma (eds.) |
38th Computational Complexity Conference, CCC 2023, July 17-20, 2023, Warwick, UK |
CCC |
2023 |
DBLP BibTeX RDF |
|
| 1 | Rahul Santhanam |
An Algorithmic Approach to Uniform Lower Bounds. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Yuhao Li 0002, Mihalis Yannakakis |
Reducing Tarski to Unique Tarski (In the Black-Box Model). |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Sandy Irani |
Translationally Invariant Constraint Optimization Problems. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Emanuele Viola |
New Sampling Lower Bounds via the Separator. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Lunjia Hu, Inbal Livni Navon, Omer Reingold |
Generative Models of Huge Objects. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara, Zhenjian Lu, Hanlin Ren |
Bounded Relativization. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar |
Criticality of AC⁰-Formulae. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Morgan Shirley |
Separation of the Factorization Norm and Randomized Communication Complexity. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Jaroslaw Blasiok |
Matrix Multiplication and Number on the Forehead Communication. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Abhranil Chatterjee 0001, Sumanta Ghosh, Rohit Gurjar, Roshan Raj |
Border Complexity of Symbolic Determinant Under Rank One Restriction. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Abhibhav Garg, Rafael Oliveira 0006, Shir Peleg, Akash Kumar Sengupta |
Radical Sylvester-Gallai Theorem for Tuples of Quadratics. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jyun-Jie Liao |
Hardness Against Linear Branching Programs and More. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ben Davis, Robert Robere |
Colourful TFNP and Propositional Proofs. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Halley Goldberg, Valentine Kabanets |
Improved Learning from Kolmogorov Complexity. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Lennart Bittel, Sevag Gharibian, Martin Kliesch |
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael E. Saks, Rahul Santhanam |
On Randomized Reductions to the Random Strings. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Karliner, Roie Salama, Amnon Ta-Shma |
The Plane Test Is a Local Tester for Multiplicity Codes. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara |
Symmetry of Information from Meta-Complexity. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard |
Linear Branching Programs and Directional Affine Extractors. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Zander Kelley, Raghu Meka |
Random Restrictions and PRGs for PTFs in Gaussian Space. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Jiatu Li, Tianqi Yang 0001 |
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, DeVon Ingram, William Kretschmer |
The Acrobatics of BQP. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Nutan Limaye, Srikanth Srinivasan 0001, Sébastien Tavenas |
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Blanc, Dean Doron |
New Near-Linear Time Decodable Codes Closer to the GV Bound. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Karthik C. S., Subhash Khot |
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Deepanshu Kush, Shubhangi Saraf |
Improved Low-Depth Set-Multilinear Circuit Lower Bounds. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Yanyi Liu, Rafael Pass |
On One-Way Functions from NP-Complete Problems. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Till Tantau |
On the Satisfaction Probability of k-CNF Formulas. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff |
ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Lyu 0002 |
Improved Pseudorandom Generators for AC⁰ Circuits. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Gal Arnon, Alessandro Chiesa, Eylon Yogev |
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Yanyi Liu, Rafael Pass |
Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Makrand Sinha, Ronald de Wolf |
Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | James Cook, Ian Mertz |
Trading Time and Space in Catalytic Branching Programs. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen |
Quantum Search-To-Decision Reductions and the State Synthesis Problem. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Harm Derksen, Visu Makam, Jeroen Zuiddam |
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne |
Hitting Sets for Regular Branching Programs. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Louis Golowich, Salil P. Vadhan |
Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan 0001 |
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Ivan Mihajlin, Anastasia Sofronova |
A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Sokolov 0001 |
Pseudorandom Generators, Resolution and Heavy Width. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sarah Bordage, Mathieu Lhotel, Jade Nardi, Hugues Randriam |
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, Kevin Pratt |
High-Dimensional Expanders from Chevalley Groups. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Vikraman Arvind, Pushkar S. Joglekar |
On Efficient Noncommutative Polynomial Factorization via Higman Linearization. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Erfan Khaniki |
Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Amol Aggarwal, Josh Alman |
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett (eds.) |
37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA. |
CCC |
2022 |
DBLP BibTeX RDF |
|
| 1 | Gal Beniamini |
The Approximate Degree of Bipartite Perfect Matching. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Alexandros Hollender, Siddhartha Jain 0002, Gilbert Maystre, William Pires, Robert Robere, Ran Tao |
Further Collapses in TFNP. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira |
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan |
The Composition Complexity of Majority. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Oliver Korten |
Derandomization from Time-Space Tradeoffs. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Jun-Ting Hsieh, Sidhanth Mohanty, Jeff Xu |
Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara, Mikito Nanashima |
Finding Errorless Pessiland in Error-Prone Heuristica. |
CCC |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | William Cole Franks, Philipp Reichenbach |
Barriers for Recent Methods in Geodesic Optimization. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Dmitry Sokolov 0001 |
The Power of Negative Reasoning. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anastasia Sofronova, Dmitry Sokolov 0001 |
Branching Programs with Bounded Repetitions and Flow Formulas. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vishnu Iyer, Avishay Tal, Michael Whitmeyer |
Junta Distance Approximation with Sub-Exponential Queries. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam |
On the Pseudo-Deterministic Query Complexity of NP Search Problems. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Akshay Kamath, Eric Price 0001, David P. Woodruff |
A Simple Proof of a New Set Disjointness with Applications to Data Streams. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua A. Grochow, Youming Qiao |
On p-Group Isomorphism: Search-To-Decision, Counting-To-Decision, and Nilpotency Class Reductions via Tensors. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Marshall Ball, Oded Goldreich 0001, Tal Malkin |
Communication Complexity with Defective Randomness. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | László Babai, Bohdan Kivva |
Matrix Rigidity Depends on the Target Field. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nati Linial, Adi Shraibman |
An Improved Protocol for the Exactly-N Problem. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitry Itsykson, Artur Riazanov |
Proof Complexity of Natural Formulas via Communication Arguments. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Dutta, Prateek Dwivedi 0001, Nitin Saxena 0001 |
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yaroslav Alekseev |
A Lower Bound for Polynomial Calculus with Extension Rule. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Hanlin Ren, Rahul Santhanam |
Hardness of KT Characterizes Parallel Cryptography. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Gilbert Maystre |
A Majority Lemma for Randomised Query Complexity. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson |
On the Power and Limitations of Branch and Cut. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyu Guo 0001 |
Variety Evasive Subspace Families. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuo Pang |
SOS Lower Bound for Exact Planted Clique. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma |
Error Reduction for Weighted PRGs Against Read Once Branching Programs. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara, Rahul Ilango, Bruno Loff |
Hardness of Constant-Round Communication Complexity. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty |
Fractional Pseudorandom Generators from Any Fourier Level. |
CCC |
2021 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license