default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2023
Volume TR23, 2023
- Prerona Chatterjee, Pavel Hrubes:
New Lower Bounds against Homogeneous Non-Commutative Circuits. - Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran:
Diagonalization Games. - Shachar Lovett, Jiapeng Zhang:
Streaming Lower Bounds and Asymmetric Set-Disjointness. - Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, Chuanqi Zhang:
On linear-algebraic notions of expansion. - Paul Beame, Niels Kornerup:
Cumulative Memory Lower Bounds for Randomized and Quantum Computation. - Nader H. Bshouty:
Superpolynomial Lower Bounds for Learning Monotone Classes. - Jan Krajícek:
Extended Nullstellensatz proof systems. - Ondrej Jezil:
Limits of structures and Total NP Search Problems. - Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, Sébastien Tavenas:
Towards Optimal Depth-Reductions for Algebraic Formulas. - Per Austrin, Kilian Risse:
Sum-of-Squares Lower Bounds for the Minimum Circuit Size Problem. - Mikhail Dektiarev, Nikolai K. Vereshchagin:
Half-duplex communication complexity with adversary? can be less than the classical communication complexity. - Yogesh Dahiya, K. Vignesh, Meena Mahajan, Karteek Sreenivasaiah:
Linear threshold functions in decision lists, decision trees, and depth-2 circuits. - Noam Mazor:
A Lower Bound on the Share Size in Evolving Secret Sharing. - Tameem Choudhury, Karteek Sreenivasaiah:
Depth-3 Circuit Lower Bounds for k-OV. - Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. - Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals:
Proving Unsatisfiability with Hitting Formulas. - Deepanshu Kush, Shubhangi Saraf:
Near-Optimal Set-Multilinear Formula Lower Bounds. - Qipeng Liu, Ran Raz, Wei Zhan:
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory. - Pooya Hatami, William Hoza:
Theory of Unconditional Pseudorandom Generators. - Scott Aaronson, Shih-Han Hung:
Certified Randomness from Quantum Supremacy. - Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, Sidhant Saraogi:
Range Avoidance for Constant-Depth Circuits: Hardness and Algorithms. - Jiatu Li, Igor Carboni Oliveira:
Unprovability of strong complexity lower bounds in bounded arithmetic. - Xin Li:
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More. - Mark Bun, Nadezhda Voronova:
Approximate degree lower bounds for oracle identification problems. - Vikraman Arvind, Pushkar S. Joglekar:
Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization. - Shuichi Hirahara, Nobutaka Shimizu:
Hardness Self-Amplification: Simplified, Optimized, and Unified. - Joseph Zalewski:
Some Lower Bounds Related to the Missing String Problem. - Rahul Santhanam:
An Algorithmic Approach to Uniform Lower Bounds. - Nicollas M. Sdroievski, Dieter van Melkebeek:
Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols. - Jan Krajícek:
A proof complexity conjecture and the Incompleteness theorem. - Benny Applebaum, Eliran Kachlon, Arpita Patra:
The Round Complexity of Statistical MPC with Optimal Resiliency. - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Linear Independence, Alternants and Applications. - Sumanta Ghosh, Prahladh Harsha, Simão Herdade, Mrinal Kumar, Ramprasad Saptharishi:
Fast Numerical Multivariate Multipoint Evaluation. - Oded Goldreich:
On teaching the approximation method for circuit lower bounds. - Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira:
A Duality Between One-Way Functions and Average-Case Symmetry of Information. - Dean Doron, Roei Tell:
Derandomization with Minimal Memory Footprint. - Shuichi Hirahara:
Capturing One-Way Functions via NP-Hardness of Meta-Complexity. - Rahul Ilango, Jiatu Li, Ryan Williams:
Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic. - Arkadev Chattopadhyay, Yogesh Dahiya, Meena Mahajan:
Query Complexity of Search Problems. - Edward Pyne, Ran Raz, Wei Zhan:
Certified Hardness vs. Randomness for Log-Space. - Lila Fontes, Sophie Laplante, Mathieu Laurière, Alexandre Nolin:
The communication complexity of functions with large outputs. - Johan Håstad:
On small-depth Frege proofs for PHP. - Yotam Dikstein, Irit Dinur:
Coboundary and cosystolic expansion without dependence on dimension or degree. - Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar:
Separations between Combinatorial Measures for Transitive Functions. - Vinayak M. Kumar:
Tight Correlation Bounds for Circuits Between AC0 and TC0. - Yizhi Huang, Rahul Ilango, Hanlin Ren:
NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach. - Hunter Monroe:
Ruling Out Short Proofs of Unprovable Sentences is Hard. - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A d1/2+o(1) Monotonicity Tester for Boolean Functions on $d$-Dimensional Hypergrids. - Mika Göös, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov:
Top-Down Lower Bounds for Depth-Four Circuits. - Manasseh Ahmed, TsunMing Cheung, Hamed Hatami, Kusha Sareen:
Communication complexity of half-plane membership. - Benjamin Böhm, Olaf Beyersdorff:
QCDCL vs QBF Resolution: Further Insights. - Noah Fleming, Vijay Ganesh, Antonina Kolokolova, Chunxiao Li, Marc Vinyals:
Limits of CDCL Learning via Merge Resolution. - Leroy Chew:
Proof Simulation via Round-based Strategy Extraction for QBF. - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: III. - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: II. - Geoffrey Mon, Dana Moshkovitz, Justin Oh:
Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate. - Iddo Tzameret, Luming Zhang:
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. - Xin Li, Yan Zhong:
Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs. - Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach, Akhil Vanukuri, Prashant Nalini Vasudevan:
k-SUM in the Sparse Regime. - Abhimanyu Choudhury, Meena Mahajan:
Dependency schemes in CDCL-based QBF solving: a proof-theoretic study. - Benny Applebaum, Eliran Kachlon:
Conflict Checkable and Decodable Codes and Their Applications. - Jacobo Torán, Florian Wörz:
Cutting Planes Width and the Complexity of Graph Isomorphism Refutations. - Oded Goldreich:
On the Lower Bound on the Length of Relaxed Locally Decodable Codes. - Louis Golowich:
From Grassmannian to Simplicial High-Dimensional Expanders. - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
Protecting Single-Hop Radio Networks from Message Drops. - Guy Goldberg:
Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error. - Ben Davis, Robert Robere:
Colourful TFNP and Propositional Proofs. - Bruno Pasqualotto Cavalar, Igor Carboni Oliveira:
Constant-depth circuits vs. monotone circuits. - Shuichi Hirahara, Zhenjian Lu, Hanlin Ren:
Bounded Relativization. - Yuval Filmus, Itai Leigh, Artur Riazanov, Dmitry Sokolov:
Sampling and Certifying Symmetric Functions. - Yeyuan Chen, Yizhi Huang, Jiatu Li, Hanlin Ren:
Range Avoidance, Remote Point, and Hard Partial Truth Tables via Satisfying-Pairs Algorithms. - Xi Chen, Yuhao Li, Mihalis Yannakakis:
Reducing Tarski to Unique Tarski (in the Black-box Model). - Abhibhav Garg, Rafael Mendes de Oliveira, Shir Peleg, Akash Sengupta:
Radical Sylvester-Gallai Theorem for Tuples of Quadratics. - Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj:
Border Complexity of Symbolic Determinant under Rank One Restriction. - Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam:
Polynomial-Time Pseudodeterministic Construction of Primes. - Nir Bitansky, Chethan Kamath, Omer Paneth, Ron Rothblum, Prashant Nalini Vasudevan:
Batch Proofs are Statistically Hiding. - Or Meir:
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. - Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
Mutual Empowerment between Circuit Obfuscation and Circuit Minimization. - Halley Goldberg, Valentine Kabanets:
Improved Learning from Kolmogorov Complexity. - Noga Amit, Guy N. Rothblum:
Constant-Round Arguments from One-Way Functions. - Ryan Williams:
Self-Improvement for Circuit-Analysis Problems. - A. Srinivasan, Uma Girish:
Trade-offs between Entanglement and Communication. - Itai Dinur:
Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model. - Ari Karchmer:
Average-Case PAC-Learning from Nisan's Natural Proofs. - Dmitry Sokolov:
Random (log n)-CNF are Hard for Cutting Planes (Again). - Benny Applebaum, Oded Nir, Benny Pinkas:
How to Recover a Secret with $O(n)$ Additions. - Parker Newton, Silas Richelson, Chase Wilson:
A High Dimensional Goldreich-Levin Theorem. - Louis Golowich:
New Explicit Constant-Degree Lossless Expanders. - Itay Cohen, Roy Roth, Amnon Ta-Shma:
HDX Condensers. - Benny Applebaum, Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tianren Liu, Vinod Vaikuntanathan:
Succinct Computational Secret Sharing. - Swastik Kopparty, Vishvajeet N:
Extracting Mergers and Projections of Partitions. - Vinayak M. Kumar, Geoffrey Mon:
Relaxed Local Correctability from Local Testing. - Lijie Chen, Roei Tell:
New ways of studying the BPP = P conjecture. - David Heath, Vladimir Kolesnikov, Rafail Ostrovsky:
Tri-State Circuits: A Circuit Model that Captures RAM. - Huacheng Yu, Wei Zhan:
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. - Joshua Cook, Ron D. Rothblum:
Efficient Interactive Proofs for Non-Deterministic Bounded Space. - Andrej Bogdanov, Pravesh Kothari, Alon Rosen:
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. - Sourav Chakraborty, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Swagato Sanyal, Nitin Saurabh:
On the Composition of Randomized Query Complexity and Approximate Degree. - Shuichi Hirahara, Mikito Nanashima:
Learning in Pessiland via Inductive Inference. - Renato Ferreira Pinto Jr.:
Directed Poincaré Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions. - Chin Ho Lee, Edward Pyne, Salil P. Vadhan:
On the Power of Regular and Permutation Branching Programs. - Yanyi Liu, Rafael Pass:
On One-way Functions and the Worst-case Hardness of Time-Bounded Kolmogorov Complexity. - Meghal Gupta, Rachel Yun Zhang:
A Noise Resilient Transformation for Streaming Algorithms. - Lijie Chen, Roei Tell, Ryan Williams:
Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization. - Mika Göös, Ziyi Guan, Tiberiu Mosnoi:
Depth-3 Circuits for Inner Product. - Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Computations are Verifiable. - Andrej Bogdanov, TsunMing Cheung, Krishnamoorthy Dinesh, John C. S. Lui:
Classical simulation of one-query quantum distinguishers. - Pranav Bisht, Nikhil Gupta, Ilya Volkovich:
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. - Gil Cohen, Tal Yankovitz:
Asymptotically-Good RLCCs with $(\log{n})^{2+o(1)}$ Queries. - Vaibhav Krishan
:
MidBit+, Torus Polynomials and Non-classical Polynomials: Equivalences for ACC Lower Bounds. - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: IV. - Justin Holmgren, Ron Rothblum:
Linear-Size Boolean Circuits for Multiselection. - Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu:
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting. - Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk:
Determinants vs. Algebraic Branching Programs. - Amey Bhangale, Subhash Khot, Dor Minzer:
Effective Bounds for Restricted $3$-Arithmetic Progressions in $\mathbb{F}_p^n$. - François Le Gall, Yupan Liu, Qisheng Wang:
Space-bounded quantum state testing via space-efficient quantum singular value transformation. - Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum:
Distribution-Free Proofs of Proximity. - Yotam Dikstein, Irit Dinur:
Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers. - Mitali Bafna, Dor Minzer:
Characterizing Direct Product Testing via Coboundary Expansion. - Theodoros Papamakarios:
Depth d Frege systems are not automatable unless P=NP. - Vikraman Arvind, Abhranil Chatterjee:
On Lifting Lower Bounds for Noncommutative Circuits using Automata. - Noam Mazor:
Key-Agreement with Perfect Completeness from Random Oracles. - Zander Kelley, Shachar Lovett, Raghu Meka:
Explicit separations between randomized and deterministic Number-on-Forehead communication. - Omar Alrabiah, Venkatesan Guruswami, Ray Li:
Randomly punctured Reed-Solomon codes achieve list-decoding capacity over linear-sized fields. - Omar Alrabiah, Venkatesan Guruswami, Ray Li:
AG codes have no list-decoding friends: Approaching the generalized Singleton bound requires exponential alphabets. - Irit Dinur, Siqi Liu, Rachel Yun Zhang:
New Codes on High Dimensional Expanders. - Xue Chen, Kuan Cheng, Xin Li, Songtao Mao:
Random Shortening of Linear Codes and Application. - Sravanthi Chede, Leroy Chew, Balesh Kumar, Anil Shukla:
Understanding Nullstellensatz for QBFs. - Eshan Chattopadhyay, Jyun-Jie Liao:
Recursive Error Reduction for Regular Branching Programs. - Meghal Gupta, Rachel Yun Zhang:
On Interactive Coding Schemes with Adaptive Termination. - Yogesh Dahiya, Meena Mahajan, Sasank Mouli:
New lower bounds for Polynomial Calculus over non-Boolean bases. - David Ellis, Guy Kindler, Noam Lifshitz, Dor Minzer:
Product mixing in compact Lie groups. - Oded Goldreich:
On the complexity of enumerating ordered sets. - Prerona Chatterjee, Anamay Tengse:
On Annihilators of Explicit Polynomial Maps.