default search action
Electronic 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
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. - Benny Applebaum, Oded Nir:
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography. - Mi-Ying (Miryam) Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang:
Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments. - Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman:
An improved protocol for ExactlyN with more than 3 players. - Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi:
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits. - Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani:
Extractors for Polynomial Sources over $\mathbb{F}_2$. - Nader H. Bshouty, Gergely Harcos:
A Tight Lower Bound of Ω(log n) for the Estimation of the Number of Defective Items. - Tom Gur, Wilfred Salmon, Sergii Strelchuk:
Provable Advantage in Quantum PAC Learning. - Noam Mazor, Rafael Pass:
Counting Unpredictable Bits: A Simple PRG from One-way Functions. - Lijie Chen, Shuichi Hirahara, Hanlin Ren:
Symmetric Exponential Time Requires Near-Maximum Circuit Size. - Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran:
Total Variation Distance Estimation Is as Easy as Probabilistic Inference. - Oded Goldreich, Laliv Tauber:
On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model. - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time. - Srinivasan Arunachalam, Uma Girish, Noam Lifshitz:
One Clean Qubit Suffices for Quantum Communication Advantage. - Ronen Shaltiel, Jad Silbak:
Explicit Codes for Poly-Size Circuits and Functions that are Hard to Sample on Low Entropy Distributions. - Prerona Chatterjee, Kshitij Gajjar, Anamay Tengse:
Monotone Classes Beyond VNP. - Hao Wu:
An Improved Composition Theorem of a Universal Relation and Most Functions via Effective Restriction. - Yanyi Liu, Rafael Pass:
One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions. - Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Towards Simpler Sorting Networks and Monotone Circuits for Majority. - Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer:
On the Rational Degree of Boolean Functions and Applications. - Venkatesan Guruswami, Xuandi Ren, Sai Sandeep:
Baby PIH: Parameterized Inapproximability of Min CSP. - Zeyong Li:
Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform. - Vladimir V. Podolskii, Dmitrii Sluch:
One-Way Communication Complexity of Partial XOR Functions. - Oded Goldreich:
On coarse and fine approximate counting of t-cliques. - Guangxu Yang, Jiapeng Zhang:
Communication Lower Bounds for Collision Problems via Density Increment Arguments. - Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf:
Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes. - Tal Herman, Guy N. Rothblum:
Doubly-Efficient Interactive Proofs for Distribution Properties. - Pravesh Kothari, Peter Manohar:
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. - Nikhil Balaji, Samir Datta:
USSR is in P/poly. - Shuo Wang, Guangxu Yang, Jiapeng Zhang:
Communication Complexity of Set-Intersection Problems and Its Applications. - Rahul Ilango:
SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle. - Dmytro Gavinsky:
Patterned non-determinism in communication complexity. - Marshall Ball
Non-malleable codes with optimal rate for poly-size circuits. - Edward Pyne:
Time-Space Tradeoffs for BPL via Catalytic Computation. - Marshall Ball
Extracting Randomness from Samplable Distributions, Revisited. - Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha:
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. - Shuichi Hirahara, Rahul Ilango, Ryan Williams:
Beating Brute Force for Compression Problems. - Meghal Gupta:
Constant Query Local Decoding Against Deletions Is Impossible. - Louis Golowich, Venkatesan Guruswami:
Quantum Locally Recoverable Codes. - James Cook, Ian Mertz:
Tree Evaluation is in Space O(log n · log log n). - Noam Mazor, Rafael Pass:
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False. - William Hoza:
A Technique for Hardness Amplification Against $\mathrm{AC}^0$. - Kiran S. Kedlaya, Swastik Kopparty:
On the degree of polynomials computing square roots mod p. - Louis Golowich, Tali Kaufman:
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. - Ian Mertz:
Reusing Space: Techniques and Open Problems. - Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka:
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. - Mika Göös, Ilan Newman, Artur Riazanov, Dmitry Sokolov:
Hardness Condensation by Restriction. - Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan:
An Improved Line-Point Low-Degree Test. - Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled:
Derandomized Squaring: An Analytical Insight into Its True Behavior. - Gabriel Bathie, Ryan Williams:
Towards Stronger Depth Lower Bounds. - Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar:
Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes. - Ce Jin, Ryan Williams, Nathaniel Young:
A VLSI Circuit Model Accounting For Wire Delay. - Klim Efremenko, Michal Garlík, Dmitry Itsykson:
Lower bounds for regular resolution over parities. - Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Parameterized Inapproximability Hypothesis under ETH. - John Kallaugher, Ojas Parekh, Nadezhda Voronova:
Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model. - Leonid Gurvits, Nathan Klein, Jonathan Leake:
From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. - Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
On the Power of Homogeneous Algebraic Formulas. - Noam Mazor, Rafael Pass:
A Note On the Universality of Black-box MKtP Solvers. - Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz:
On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity. - Siddharth Iyer, Anup Rao:
XOR Lemmas for Communication via Marginal Information. - Shai Evra, Shay Gadot, Ohad Klein, Ilan Komargodski:
Verifying Groups in Linear Time. - Huacheng Yu, Wei Zhan:
Sampling, Flowers and Communication. - Sepehr Assadi, Gillat Kol, Zhijun Zhang:
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams. - Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, Dor Minzer:
Parallel Repetition of k-Player Projection Games. - Ján Pich, Rahul Santhanam:
Towards P $\neq$ NP from Extended Frege Lower Bounds. - Joseph Shunia:
An Efficient Deterministic Primality Test. - Alexander Shekhovtsov, Georgii Zakharov:
Enumerating Complexity Revisited. - C. Ramya, Pratik Shastri:
Lower Bounds for Planar Arithmetic Circuits. - Hamed Hatami, Kaave Hosseini, Shachar Lovett, Anthony Ostuni:
Refuting approaches to the log-rank conjecture for XOR functions. - John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen:
An efficient quantum parallel repetition theorem and applications. - Marshall Ball
(Inefficient Prover) ZAPs from Hard-to-Invert Functions. - Yilei Chen, Jiatu Li:
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography. - Omri Ben-Eliezer, Tomer Grossman, Moni Naor:
Does Prior Knowledge Help Detect Collisions? - Dean Doron, Edward Pyne, Roei Tell:
Opening Up the Distinguisher: A Hardness to Randomness Approach for BPL = L that Uses Properties of BPL. - Yotam Dikstein, Irit Dinur:
Swap cosystolic expansion. - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach:
On the Existence of Seedless Condensers: Exploring the Terrain. - Rafael Pass, Oren Renard:
Characterizing the Power of (Persistent) Randomness in Log-space. - Prerona Chatterjee, Deepanshu Kush, Shubhangi Saraf, Amir Shpilka:
Exponential Lower Bounds Against Sums of ROABPs. - Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai:
Hard Languages in $\text{NP}\cap\text{coNP}$ and NIZK Proofs from Unstructured Hardness. - Oded Goldreich, Laliv Tauber:
On Testing Group Properties.
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-27 21:28 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: