default search action
Electronic Colloquium on Computational Complexity, Volume 2024
Volume TR24, 2024
- Sam Buss, Neil Thapen:
A Simple Supercritical Tradeoff between Size and Height in Resolution. - Takashi Ishizuka:
PLS is contained in PLC. - Noam Mazor, Rafael Pass:
Search-to-Decision Reductions for Kolmogorov Complexity. - Omkar Baraskar, Agrim Dewan, Chandan Saha:
Testing equivalence to design polynomials. - Daniel Noble, Brett Hemenway, Rafail Ostrovsky:
MetaDORAM: Breaking the Log-Overhead Information Theoretic Barrier. - Sabee Grewal, Justin Yirka:
The Entangled Quantum Polynomial Hierarchy Collapses. - Karthik C. S., Pasin Manurangsi:
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results. - Pavel Hrubes:
Hard submatrices for non-negative rank and communication complexity }. - Dmytro Gavinsky:
Unambiguous parity-query complexity. - Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP is not Turing-Closed. - Paul Beame, Niels Kornerup:
Quantum Time-Space Tradeoffs for Matrix Problems. - Hamed Hatami, Pooya Hatami:
Structure in Communication Complexity and Constant-Cost Complexity Classes. - Oded Goldreich:
On locally-characterized expander graphs (a survey). - Elette Boyle, Ilan Komargodski, Neekon Vafa:
Memory Checking Requires Logarithmic Overhead. - Harpreet Bedi:
Degree 2 lower bound for Permanent in arbitrary characteristic. - Swagato Sanyal:
Randomized query composition and product distributions. - Siddhartha Jain, Jiawei Li, Robert Robere, Zhiyang Xun:
On Pigeonhole Principles and Ramsey in TFNP. - Huck Bennett, Surendra Ghentiyala, Noah Stephens-Davidowitz:
The more the merrier! On the complexity of finding multicollisions, with connections to codes and lattices. - Yotam Dikstein, Irit Dinur, Alexander Lubotzky:
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. - Mitali Bafna, Noam Lifshitz, Dor Minzer:
Constant Degree Direct Product Testers with Small Soundness. - Prasad Chaugule, Nutan Limaye:
On the closures of monotone algebraic classes and variants of the determinant. - Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, Pavel Dvorak:
Exponential Separation Between Powers of Regular and General Resolution Over Parities. - Shuichi Hirahara, Naoto Ohsaka:
Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems. - Changrui Mu, Shafik Nassar, Ron Rothblum, Prashant Nalini Vasudevan:
Strong Batching for Non-Interactive Statistical Zero-Knowledge. - Mason DiCicco, Vladimir Podolskii, Daniel Reichman:
Nearest Neighbor Complexity and Boolean Circuits. - Pavel Hrubes:
A subquadratic upper bound on sum-of-squares compostion formulas. - Dor Minzer, Kai Zhe Zheng:
Near Optimal Alphabet-Soundness Tradeoff PCPs. - Ashish Dwivedi, Zeyu Guo, Ben Lee Volk:
Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields. - Noel Arteche, Gaia Carenini, Matthew Gray:
Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard. - Olaf Beyersdorff, Tim Hoffmann, Luc Nicolas Spachmann:
Proof Complexity of Propositional Model Counting. - Daniel M. Kane, Anthony Ostuni, Kewen Wu:
Locality Bounds for Sampling Hamming Slices. - Joshua Cook, Dana Moshkovitz:
Explicit Time and Space Efficient Encoders Exist Only With Random Access. - Sam Buss, Emre Yolcu:
Regular resolution effectively simulates resolution. - Bruno Loff, Alexey Milovanov:
The hardness of decision tree complexity. - Sreejata Kishor Bhattacharya:
Aaronson-Ambainis Conjecture Is True For Random Restrictions. - Tal Yankovitz:
A stronger bound for linear 3-LCC. - Yaroslav Alekseev, Yuval Filmus, Alexander Smal:
Lifting dichotomies. - Olaf Beyersdorff, Kaspar Kasche, Luc Nicolas Spachmann:
Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree. - Shuichi Hirahara, Naoto Ohsaka:
Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration. - Kuan Cheng, Ruiyang Wu:
Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors. - Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich:
Launching Identity Testing into (Bounded) Space. - Lisa-Marie Jaser, Jacobo Torán:
Pebble Games and Algebraic Proof Systems Meet Again. - Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk:
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits. - Rohit Gurjar, Taihei Oki, Roshan Raj:
Fractional Linear Matroid Matching is in quasi-NC. - Ilario Bonacina, Maria Luisa Bonet, Sam Buss, Massimo Lauria:
Redundancy for MaxSAT. - Sasank Mouli:
Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable. - Oded Goldreich:
On the query complexity of testing local graph properties in the bounded-degree graph model. - Kuan Cheng, Yichuan Wang:
$BPL\subseteq L-AC^1$. - Karthik Gajulapalli, Zeyong Li, Ilya Volkovich:
Oblivious Classes Revisited: Lower Bounds and Hierarchies. - Omri Shmueli:
Quantum Algorithms in a Superposition of Spacetimes. - Yanyi Liu, Rafael Pass:
A Direct PRF Construction from Kolmogorov Complexity. - Justin Yirka:
Even quantum advice is unlikely to solve PP. - Noam Mazor, Rafael Pass:
Gap MCSP is not (Levin) NP-complete in Obfustopia. - Karthik Gajulapalli, Alexander Golovnev, Samuel King:
On the Power of Adaptivity for Function Inversion. - Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass:
Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement. - Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Local Correction of Linear Functions over the Boolean Cube. - Xi Chen, Yuhao Li, Mihalis Yannakakis:
Computing a Fixed Point of Contraction Maps in Polynomial Queries. - Shuichi Hirahara, Nobutaka Shimizu:
Planted Clique Conjectures Are Equivalent. - Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. - Lijie Chen, Jiatu Li, Igor Carboni Oliveira:
Reverse Mathematics of Complexity Lower Bounds. - Divesh Aggarwal, Pranjal Dutta, Zeyong Li, Maciej Obremski, Sidhant Saraogi:
Improved Lower Bounds for 3-Query Matching Vector Codes. - Omar Alrabiah, Venkatesan Guruswami:
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. - Shuichi Hirahara, Mikito Nanashima:
One-Way Functions and Zero Knowledge. - Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami:
No Complete Problem for Constant-Cost Randomized Communication. - Meghal Gupta, Mihir Singhal, Hongxun Wu:
Optimal quantile estimation: beyond the comparison model. - Siu On Chan, Hiu Tsun Ng, Sijin Peng:
How Random CSPs Fool Hierarchies. - Mi-Ying (Miryam) Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang:
Breaking Square-Root Loss Barriers via Min-Entropy. - Pravesh Kothari, Peter Manohar:
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. - Swastik Kopparty, Amnon Ta-Shma, Kedem Yakirevitch:
Character sums over AG codes. - Xinyu Mao, Guangxu Yang, Jiapeng Zhang:
Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing. - Yahel Manor, Or Meir:
Lifting with Inner Functions of Polynomial Discrepancy. - Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch:
Tropical proof systems. - Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay:
Trading Determinism for Noncommutativity in Edmonds' Problem. - Vaibhav Krishan, Sundar Vishwanathan:
Towards ACC Lower Bounds using Torus Polynomials. - Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu:
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. - Oliver Korten, Toniann Pitassi:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle. - Divesh Aggarwal, Leong Jin Ming, Alexandra Veliche:
Worst-Case to Average-Case Hardness of LWE: A Simple and Practical Perspective. - Oded Goldreich:
On the relaxed LDC of BGHSV: A survey that corrects the record. - Tuomas Hakoniemi, Nutan Limaye, Iddo Tzameret:
Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers. - Robert Andrews, Avi Wigderson:
Constant-Depth Arithmetic Circuits for Linear Algebra Problems. - Sravanthi Chede, Leroy Chew, Anil Shukla:
Circuits, Proofs and Propositional Model Counting. - Yotam Dikstein, Max Hopkins:
Chernoff Bounds and Reverse Hypercontractivity on HDX. - Lijie Chen, Jiatu Li, Igor Carboni Oliveira:
On the Unprovability of Circuit Size Bounds in Intuitionistic S12. - Vikraman Arvind, Pushkar S. Joglekar:
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results. - Zhenjian Lu, Rahul Santhanam:
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. - Hao Wu:
A nearly-4logn depth lower bound for formulas with restriction on top. - Renato Ferreira Pinto Jr.:
Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach. - Tamer Mour, Alon Rosen, Ron Rothblum:
Locally Testable Tree Codes. - Gil Cohen, Itay Cohen, Gal Maor:
Tight Bounds for the Zig-Zag Product. - Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, Tal Yankovitz:
A Study of Error Reduction Polynomials. - Dean Doron, Jonathan Mosheiff, Mary Wootters:
When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound? - Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, Chao Yan:
Hilbert Functions and Low-Degree Randomness Extractors. - Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, João Ribeiro:
Low-Degree Polynomials Are Good Extractors. - Tal Herman, Guy N. Rothblum:
Interactive Proofs for General Distribution Properties. - Yanyi Liu, Noam Mazor, Rafael Pass:
A Note on Zero-Knowledge for NP and One-Way Functions. - Noga Amit, Guy N. Rothblum:
Constant-Round Arguments for Batch-Verification and Bounded-Space Computations from One-Way Functions. - Zhiyang Xun, David Zuckerman:
Near-Optimal Averaging Samplers. - Noga Amit, Orr Paradise, Guy N. Rothblum, Shafi Goldwasser:
Models That Prove Their Own Correctness. - Pavel Hrubes:
A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials. - Changrui Mu, Prashant Nalini Vasudevan:
Instance-Hiding Interactive Proofs. - Or Keret, Ron Rothblum, Prashant Nalini Vasudevan:
Doubly-Efficient Batch Verification in Statistical Zero-Knowledge. - Inbar Ben Yaacov, Yotam Dikstein, Gal Maor:
Sparse High Dimensional Expanders via Local Lifts. - Farzan Byramji, Vatsal Jha, Chandrima Kayal, Rajat Mittal:
Relations between monotone complexity measures based on decision tree complexity. - Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha:
NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials. - Benny Applebaum, Kaartik Bhushan, Manoj Prabhakaran:
Communication Complexity vs Randomness Complexity in Interactive Proofs. - James Cook, Jiatu Li, Ian Mertz, Edward Pyne:
The Structure of Catalytic Space: Capturing Randomness and Time via Compression. - Benjamin Rossman:
Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication. - Benny Applebaum, Eliran Kachlon:
Stochastic Secret Sharing with $1$-Bit Shares and Applications to MPC. - Oded Goldreich:
On the Cook-Mertz Tree Evaluation procedure. - Joshua Cook, Dana Moshkovitz:
Time and Space Efficient Deterministic Decoders. - Siddharth Iyer, Anup Rao:
An XOR Lemma for Deterministic Communication Complexity. - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena:
The Rate of Interactive Codes is Bounded Away from 1. - Nikhil Vyas, Ryan Williams:
On Oracles and Algorithmic Methods for Proving Lower Bounds. - Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David J. Wu:
Dot-Product Proofs and Their Applications. - Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam:
On the Complexity of Avoiding Heavy Elements. - Lijie Chen, Ron D. Rothblum, Roei Tell:
Fiat-Shamir in the Plain Model from Derandomization (Or: Do Efficient Algorithms Believe that NP = PSPACE?). - Ludmila Glinskih, Artur Riazanov:
Partial Minimum Branching Program Size Problem is ETH-hard. - Amnon Ta-Shma, Ron Zadiario:
The Expander Hitting Property When the Sets Are Arbitrarily Unbalanced. - Vishwas Bhargava, Anamay Tengse:
Explicit Commutative ROABPs from Partial Derivatives. - Halley Goldberg, Valentine Kabanets:
Consequences of Randomized Reductions from SAT to Time-Bounded Kolmogorov Complexity. - Nader H. Bshouty:
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. - Antoine Joux, Anand Kumar Narayanan:
A high dimensional Cramer's rule connecting homogeneous multilinear equations to hyperdeterminants. - Vishwas Bhargava, Devansh Shringi:
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. - Oded Goldreich:
Solving Tree Evaluation in o(log n · log log n) space. - Pavel Hrubes, Pushkar S. Joglekar:
On read-k projections of the determinant. - Takashi Ishizuka:
On the Complexity of Some Restricted Variants of Quotient Pigeon and a Weaker Variant of König. - Bill Fefferman, Soumik Ghosh, Wei Zhan:
Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits. - Yaroslav Alekseev, Dmitry Itsykson:
Lifting to regular resolution over parities via games. - Amey Bhangale, Subhash Khot, Dor Minzer:
On Approximability of Satisfiable k-CSPs: V. - Sabee Grewal, Vinayak M. Kumar:
Improved Circuit Lower Bounds With Applications to Exponential Separations Between Quantum and Classical Circuits. - Hadar Strauss:
Emulating Computationally Sound Public-Coin IPPs in the Pre-Coordinated Model. - Arkadev Chattopadhyay, Pavel Dvorak:
Super-critical Trade-offs in Resolution over Parities Via Lifting. - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao:
Two-Sided Lossless Expanders in the Unbalanced Setting. - Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira:
One-Way Functions and pKt Complexity. - Dean Doron, William Hoza:
Implications of Better PRGs for Permutation Branching Programs. - Marten Folkertsma, Ian Mertz, Florian Speelman, Quinten Tupker:
Fully Characterizing Lossy Catalytic Computation. - Jiatu Li, Edward Pyne, Roei Tell:
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. - Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, Jayalal Sarma:
Almost-catalytic Computation. - Tal Herman:
Public Coin Interactive Proofs for Label-Invariant Distribution Properties. - Ryan Williams:
The Orthogonal Vectors Conjecture and Non-Uniform Circuit Lower Bounds. - Noga Amir, Oded Goldreich, Guy N. Rothblum:
Doubly Sub-linear Interactive Proofs of Proximity. - Dar Gilboa, Siddhartha Jain, Jarrod R. McClean:
Consumable Data via Quantum Communication. - Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira, Dimitrios Tsintsilidas:
Provability of the Circuit Size Hierarchy and Its Consequences. - Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass:
Lower Bounds on the Overhead of Indistinguishability Obfuscation. - Shanthanu S. Rai:
Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields. - Swastik Kopparty, Mrinal Kumar, Harry Sha:
High Rate Multivariate Polynomial Evaluation Codes. - Noor Athamnah, Ron D. Rothblum, Eden Florentz-Konopnicki:
Rate-1 Zero-Knowledge Proofs from One-Way Functions. - Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj:
Characterizing and Testing Principal Minor Equivalence of Matrices. - Vijay Bhattiprolu, Euiwoong Lee:
Inapproximability of Sparsest Vector in a Real Subspace. - Alexander A. Sherstov, Andrey A. Storozhenko:
The Communication Complexity of Approximating Matrix Rank. - Jesse Goodman, Xin Li, David Zuckerman:
Improved Condensers for Chor-Goldreich Sources. - Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima:
Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. - Bruno Pasqualotto Cavalar, Eli Goldin, Matthew Gray, Peter Hall:
A Meta-Complexity Characterization of Quantum Cryptography. - Yupan Liu, Qisheng Wang:
On estimating the trace of quantum state powers. - Xin Li, Songtao Mao:
Improved Explicit Near-Optimal Codes in the High-Noise Regimes. - Dean Doron:
Binary Codes with Distance Close to Half. - Igor Razgon:
The splitting power of branching programs of bounded repetition and CNFs of bounded width. - Oded Goldreich:
On defining PPT-search problems. - Agnes Schleitzer, Olaf Beyersdorff:
Computationally Hard Problems Are Hard for QBF Proof Systems Too. - Roei Tell:
On defining PPT-search problems and PPT-optimization problems. - Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar, Srikanth Srinivasan, Madhu Sudan:
Low Degree Local Correction Over the Boolean Cube. - Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Online Condensing of Unpredictable Sources via Random Walks. - John Bostanci, Yeongwoo Hwang:
Commuting Local Hamiltonians Beyond 2D. - François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang:
Space-bounded quantum interactive proof systems. - Ronen Shaltiel:
Multiplicative Extractors for Samplable Distributions. - Clément L. Canonne, Francis E. Su, Salil P. Vadhan:
The Randomness Complexity of Differential Privacy. - Michael Jaber, Shachar Lovett, Anthony Ostuni:
Corners in Quasirandom Groups via Sparse Mixing. - Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach:
Condensing against Online Adversaries. - Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li:
Quantum Communication Advantage in TFNP. - Songhua He, Yuanzhi Li, Periklis A. Papakonstantinou, Xin Yang:
Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL. - Albert Atserias, Iddo Tzameret:
Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. - Mark Braverman, Or Zamir:
Optimality of Frequency Moment Estimation. - Dean Doron, João Ribeiro:
Nearly-Linear Time Seeded Extractors with Short Seeds. - Swastik Kopparty, Harry Sha:
Small Shadow Partitions. - Noah Fleming, Yuichi Yoshida:
Sensitivity Lower Bounds for Approximaiton Algorithms. - Norbert Blum:
On the approximation method and the P versus NP problem. - Daniel Kane, Anthony Ostuni, Kewen Wu:
Locally Sampleable Uniform Symmetric Distributions. - Tomer Gewirtzman, Ron Rothblum:
Zero-Knowledge in Streaming Interactive Proofs. - Lijie Chen, Jiatu Li, Jingxun Liang:
Maximum Circuit Lower Bounds for Exponential-time Arthur Merlin. - Fatemeh Ghasemi, Swastik Kopparty, Madhu Sudan:
Improved PIR Schemes using Matching Vectors and Derivatives. - Fernando Granha Jeronimo, Nir Magrafta, Joseph Slote, Pei Wu:
Coherence in Property Testing: Quantum-Classical Collapses and Separations. - Susanna F. de Rezende, Noah Fleming, Duri Andrea Janett, Jakob Nordström, Shuo Pang:
Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman. - Mika Göös, Gilbert Maystre, Kilian Risse, Dmitry Sokolov:
Supercritical Tradeoffs for Monotone Circuits. - Oliver Janzer, Peter Manohar:
A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs. - Edward Pyne, Nathan S. Sheffield, William Wang:
Catalytic Communication. - Arpon Basu, Jun-Ting Hsieh, Pravesh Kothari, Andrew D. Lin:
Improved Lower Bounds for all Odd-Query Locally Decodable Codes. - Jiawei Li, Yuhao Li, Hanlin Ren:
Metamathematics of Resolution Lower Bounds: A TFNP Perspective. - Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer:
On Approximability of Satisfiable k-CSPs: VI. - Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer:
On Approximability of Satisfiable k-CSPs: VII. - Amey Bhangale, Subhash Khot, Yang P. Liu, Dor Minzer:
Reasonable Bounds for Combinatorial Lines of Length Three. - Yanyi Liu, Noam Mazor, Rafael Pass:
On Witness Encryption and Laconic Zero-Knowledge Arguments. - Yanyi Liu, Noam Mazor, Rafael Pass:
On White-Box Learning and Public-Key Encryption. - Clément L. Canonne, Sayantan Sen, Joy Qiping Yang:
Settling the complexity of testing grainedness of distributions, and application to uniformity testing in the Huge Object model. - Pranjal Dutta, Amit Sinhababu, Thomas Thierauf:
Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. - G. V. Sumukha Bharadwaj, Raja S:
Randomized Black-Box PIT for Small Depth +-Regular Non-commutative Circuits. - Vladimir Podolskii, Alexander Shekhovtsov:
Randomized Lifting to Semi-Structured Communication Complexity via Linear Diversity. - Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Amit Levi, Gopinath Mishra, Sayantan Sen:
Testing vs Estimation for Index-Invariant Properties in the Huge Object Model. - Marius Zimand:
On one-way functions and the average time complexity of almost-optimal compression. - Farzan Byramji, Russell Impagliazzo:
Lifting to Randomized Parity Decision Trees. - Tyler Besselman, Mika Göös, Siyao Guo, Gilbert Maystre, Weiqiang Yuan:
Direct Sums for Parity Decision Trees. - Marshall Ball, Ronen Shaltiel, Jad Silbak:
Extractors for Samplable Distributions with Low Min-Entropy. - Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley:
A Lower Bound on the Trace Norm of Boolean Matrices and its Applications.
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 2025-11-11 02:25 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: