default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2026
Volume TR16, 2016
- Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza:
Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs. - Ryan Williams:
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation. - Boris Brimkov, Illya V. Hicks:
On the logspace shortest path problem. - Dax Enshan Koh:
Further extensions of Clifford circuits and their classical simulation complexities. - Olaf Beyersdorff, Leroy Chew, Mikolas Janota:
Extension Variables in QBF Resolution. - Neeraj Kayal, Chandan Saha, Sébastien Tavenas:
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits. - Guy Kindler:
Property Testing, PCP, andJuntas. - Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova:
Algorithms from Natural Lower Bounds. - Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Identity Testing for constant-width, and commutative, read-once oblivious ABPs. - Alexander A. Razborov:
On the Width of Semi-Algebraic Proofs and Algorithms. - Olaf Beyersdorff, Ján Pich:
Understanding Gentzen and Frege systems for QBF. - John M. Hitchcock, Hadi Shafei:
Autoreducibility of NP-Complete Sets. - Ludwig Staiger:
Bounds on the Kolmogorov complexity function for infinite words. - Gil Cohen, Leonard J. Schulman:
Extractors for Near Logarithmic Min-Entropy. - Oded Goldreich:
The uniform distribution is complete with respect to testing identity to a fixed distribution. - Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson:
Doubly infinite separation of quantum information and communication. - Georgios Stamoulis:
Limitations of Linear Programming Techniques for Bounded Color Matchings. - Kuan Cheng, Xin Li:
Randomness Extraction in AC0 and with Small Locality. - Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. - Zachary Remscrim:
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. - Shachar Lovett, Jiapeng Zhang:
Noisy Population Recovery from Unknown Noise. - Alexander Golovnev, Alexander S. Kulikov, Alexander Smal, Suguru Tamaki:
Circuit size lower bounds and #SAT upper bounds through a general framework. - Ilan Komargodski, Moni Naor, Eylon Yogev:
How to Share a Secret, Infinitely. - Patrick Scharpfenecker, Jacobo Torán:
Solution-Graphs of Boolean Formulas and Isomorphism. - Shachar Lovett:
The Fourier structure of low degree polynomials. - Anindya De, Michael E. Saks, Sijian Tang:
Noisy population recovery in polynomial time. - Sagnik Mukhopadhyay:
Tribes Is Hard in the Message Passing Model. - Olaf Beyersdorff, Joshua Blinkhorn:
Dependency Schemes in QBF Calculi: Semantics and Soundness. - Joshua Brakensiek, Venkatesan Guruswami:
New hardness results for graph and hypergraph colorings. - Gil Cohen:
Non-Malleable Extractors with Logarithmic Seeds. - Titus Dose:
Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers. - Roei Tell:
A Note on Tolerant Testing with One-Sided Error. - Venkatesan Guruswami, Jaikumar Radhakrishnan:
Tight bounds for communication assisted agreement distillation. - Mohamed El Halaby:
On the Computational Complexity of MaxSAT. - Irit Dinur, Or Meir:
Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. - Eshan Chattopadhyay, Xin Li:
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols. - Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel:
Pseudorandomness when the odds are against you. - Meena Mahajan, Nitin Saurabh:
Some Complete and Intermediate Polynomials in Algebraic Complexity Theory. - Adam Bouland, Laura Mancinska, Xue Zhang:
Complexity Classification of Two-Qubit Commuting Hamiltonians. - Baris Aydinlioglu, Eric Bach:
Affine Relativization: Unifying the Algebrization and Relativization Barriers. - Johan Håstad:
An average-case depth hierarchy theorem for higher depth. - Oded Goldreich, Tom Gur:
Universal Locally Testable Codes. - Mikolas Janota:
On Q-Resolution and CDCL QBF Solving. - Kaave Hosseini, Shachar Lovett:
Structure of protocols for XOR functions. - Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi:
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity. - Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck. - Mohammad Bavarian, Thomas Vidick, Henry Yuen:
Parallel repetition via fortification: analytic view and the quantum case. - Olaf Beyersdorff, Leroy Chew, Renate A. Schmidt, Martin Suda:
Lifting QBF Resolution Calculi to DQBF. - Cynthia Dwork, Moni Naor, Guy N. Rothblum:
Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems. - Roei Tell:
Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. - Ronald Cramer, Chaoping Xing, Chen Yuan:
On Multi-Point Local Decoding of Reed-Muller Codes. - Gil Cohen:
Making the Most of Advice: New Correlation Breakers and Their Applications. - Jiawei Gao, Russell Impagliazzo:
Orthogonal Vectors is hard for first-order properties on sparse graphs. - Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. - Tim Roughgarden, Omri Weinstein:
On the Communication Complexity of Approximate Fixed Points. - Shafi Goldwasser, Dhiraj Holden:
On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances. - Ilario Bonacina:
Total space in Resolution is at least width squared. - Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin:
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. - Alon Rosen, Gil Segev, Ido Shahaf:
Can PPAD Hardness be Based on Standard Cryptographic Assumptions? - Henry Yuen:
A parallel repetition theorem for all entangled games. - Omer Reingold, Ron Rothblum, Guy N. Rothblum:
Constant-Round Interactive Proofs for Delegating Computation. - Avishay Tal:
On The Sensitivity Conjecture. - Pavel Hubácek, Eylon Yogev:
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds. - Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman:
Exponential Lower Bounds for Monotone Span Programs. - Xi Chen, Yu Cheng, Bo Tang:
A Note on Teaching for VC Classes. - Oded Goldreich, Maya Leshkowitz:
On Emulating Interactive Proofs with Public Coins. - Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani:
Pebbling Meets Coloring : Reversible Pebble Game On Trees. - Srikanth Srinivasan:
On Polynomial Approximations to AC0. - Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson:
Degree and Sensitivity: tails of two distributions. - Mika Göös, Rahul Jain, Thomas Watson:
Extension Complexity of Independent Set Polytopes. - Jan Krajícek, Igor Carboni Oliveira:
Unprovability of circuit upper bounds in Cook's theory PV. - Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. - Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Michael Riabzev:
Improved concrete efficiency and security analysis of Reed-Solomon PCPPs. - Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. - Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC0. - Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma:
Characterization and Lower Bounds for Branching Program Size using Projective Dimension. - Zvika Brakerski, Justin Holmgren
, Yael Tauman Kalai:
Non-Interactive RAM and Batch NP Delegation from any PIR. - Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. - Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli:
Sum-of-squares hierarchy lower bounds for symmetric formulations. - Oded Goldreich:
Reducing testing affine spaces to testing linearity. - Alexander A. Sherstov:
Compressing interactive communication under product distributions. - Benny Applebaum, Pavel Raykov:
Fast Pseudorandom Functions Based on Expander Graphs. - Nader H. Bshouty:
Derandomizing Chernoff Bound with Union Bound with an Application to k-wise Independent Sets. - Shalev Ben-David:
Low-Sensitivity Functions from Unambiguous Certificates. - Shiteng Chen, Periklis A. Papakonstantinou:
Depth-reduction for composites. - Noga Alon, Klim Efremenko, Benny Sudakov:
Testing Equality in Communication Graphs. - Shalev Ben-David, Robin Kothari:
Randomized query complexity of sabotaged and composed functions. - Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Explicit two-source extractors for near-logarithmic min-entropy. - Vikraman Arvind, Partha Mukhopadhyay, Raja S:
Randomized Polynomial Time Identity Testing for Noncommutative Circuits. - Bernhard Haeupler, Ameya Velingker:
Bridging the Capacity Gap Between Interactive and One-Way Communication. - Nir Bitansky, Akshay Degwekar, Vinod Vaikuntanathan:
Structure vs Hardness through the Obfuscation Lens. - Gilad Asharov, Alon Rosen, Gil Segev:
Indistinguishability Obfuscation Does Not Reduce to Structured Languages. - Cyrus Rashtchian:
Bounded Matrix Rigidity and John's Theorem. - Guillaume Lagarde, Guillaume Malod, Sylvain Perifel:
Non-commutative computations: lower bounds and polynomial identity testing. - Arkadev Chattopadhyay, Nikhil S. Mande:
Small Error Versus Unbounded Error Protocols in the NOF Model. - Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V. Vinay:
The Chasm at Depth Four, and Tensor Rank : Old results, new insights. - Vivek Anand T. Kallampally, Raghunath Tewari:
Trading Determinism for Time in Space Bounded Computations. - Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. - Takayuki Sakai, Kazuhisa Seto, Suguru Tamaki, Junichi Teruyama:
Bounded Depth Circuits with Weighted Symmetric Gates: Satisfiability, Lower Bounds and Compression. - Suguru Tamaki:
A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates. - Toniann Pitassi, Iddo Tzameret:
Algebraic Proof Complexity: Progress, Frontiers and Challenges. - Ravi B. Boppana, Johan Håstad, Chin Ho Lee, Emanuele Viola:
Bounded independence vs. moduli. - Jaikumar Radhakrishnan, Swagato Sanyal:
The zero-error randomized query complexity of the pointer function. - Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-Interactive Simulation of Joint Distributions. - Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. - Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma:
Low-error two-source extractors for polynomial min-entropy. - Nathanaël Fijalkow:
Lower Bounds for Alternating Online Space Complexity. - Michael Rudow:
Discrete Logarithm and Minimum Circuit Size. - Scott Aaronson:
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. - Alexander Golovnev, Oded Regev, Omri Weinstein:
The Minrank of Random Graphs. - Amit Chakrabarti, Sagar Kale:
Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics. - Mohammad Taghi Hajiaghayi, Amey Bhangale, Rajiv Gandhi, Rohit Khandekar, Guy Kortsarz:
Bicovering: Covering edges with two small subsets of vertices. - Gillat Kol, Ran Raz, Avishay Tal:
Time-Space Hardness of Learning Sparse Parities. - Gil Cohen:
Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols. - Xin Li:
Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors. - Subhash Khot, Rishi Saket:
Approximating CSPs using LP Relaxation. - Mrinalkanti Ghosh, Madhur Tulsiani:
From Weak to Strong LP Gaps for all CSPs. - Shachar Lovett, Jiapeng Zhang:
On the impossibility of entropy reversal, and its application to zero-knowledge proofs. - Alexander Golovnev, Edward A. Hirsch, Alexander Knop, Alexander S. Kulikov:
On the Limits of Gate Elimination. - Dean Doron, Amir Sarid, Amnon Ta-Shma:
On approximating the eigenvalues of stochastic matrices in probabilistic logspace. - Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. - Sivakanth Gopi, Swastik Kopparty, Rafael Mendes de Oliveira, Noga Ron-Zewi, Shubhangi Saraf:
Locally testable and Locally correctable Codes Approaching the Gilbert-Varshamov Bound. - Stasys Jukna:
Tropical Complexity, Sidon Sets, and Dynamic Programming. - Subhash Khot, Dor Minzer, Muli Safra:
On Independent Sets, 2-to-2 Games and Grassmann Graphs. - Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu:
Local Testing for Membership in Lattices. - Subhash Khot, Igor Shinkar:
An Õ(n) Queries Adaptive Tester for Unateness. - Timothy Gowers, Emanuele Viola:
The multiparty communication complexity of interleaved group products. - Irit Dinur:
Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. - Emanuele Viola, Avi Wigderson:
Local Expanders. - Arkadev Chattopadhyay, Michael Langberg, Shi Li, Atri Rudra:
Tight Network Topology Dependent Bounds on Rounds of Communication. - Andrej Bogdanov, Siyao Guo, Ilan Komargodski:
Threshold Secret Sharing Requires a Linear Size Alphabet. - Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker:
On the Sensitivity Conjecture for Read-k Formulas. - Deeparnab Chakrabarty, C. Seshadhri:
A Õ(n) Non-Adaptive Tester for Unateness. - Ronen Shaltiel, Jad Silbak:
Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. - Christoph Berkholz, Jakob Nordström:
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps. - Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer:
Testing k-Monotonicity. - Mrinal Kumar, Ramprasad Saptharishi:
Finer separations between shallow arithmetic circuits. - Alexander A. Sherstov:
On multiparty communication with large versus unbounded error. - Ludwig Staiger:
Exact constructive and computable dimensions. - Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On SZK and PP. - Ryan O'Donnell:
SOS is not obviously automatizable, even approximately. - Jason Li, Ryan O'Donnell:
Bounding laconic proof systems by solving CSPs in parallel. - Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan:
An Almost Cubic Lower Bound for ΣΠΣ Circuits Computing a Polynomial in VP. - Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucký:
Expander Construction in VNC1. - Markus Bläser, Gorav Jindal, Anurag Pandey:
Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces. - Scott Aaronson, Mohammad Bavarian, Giulio G. Giusteri:
Computability Theory of Closed Timelike Curves. - Ryan O'Donnell, A. C. Cem Say:
The weakness of CTC qubits and the power of approximate counting. - Thomas Watson:
Communication Complexity with Small Advantage. - Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Michael Riabzev:
A security analysis of Probabilistically Checkable Proofs. - Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez:
Streaming Communication Protocols. - Amir Yehudayoff:
Pointer chasing via triangular discrimination. - Oded Goldreich:
Deconstructing 1-local expanders. - Christian Engels, B. V. Raghavendra Rao, Karteek Sreenivasaiah:
Lower Bounds and Identity Testing for Projections of Power Symmetric Polynomials. - Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor:
Logical Induction. - Vaibhav Krishan, Nutan Limaye:
Isolation Lemma for Directed Reachability and NL vs. L. - Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner:
On Probabilistic Checking in Perfect Zero Knowledge. - Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, Jacobo Torán:
Parameterized Complexity of Small Weight Automorphisms. - Alexander S. Kulikov, Vladimir V. Podolskii:
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates. - Daniel Grier, Luke Schaeffer:
New Hardness Results for the Permanent Using Linear Optics. - Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen:
Multiplayer parallel repetition for expander games. - Shachar Lovett, Jiapeng Zhang:
Robust sensitivity. - Joshua A. Grochow:
NP-hard sets are not sparse unless P=NP: An exposition of a simple proof of Mahaney's Theorem, with applications. - Matthew B. Hastings:
Local Maxima and Improved Exact Algorithm for MAX-2-SAT. - Andreas Krebs, Meena Mahajan, Anil Shukla:
Relating two width measures for resolution proofs. - Arkadev Chattopadhyay, Pavel Dvorák, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Lower Bounds for Elimination via Weak Regularity. - Mark Braverman, Ran Gelles, Michael A. Yitayew:
Optimal Resilience for Short-Circuit Noise in Formulas. - Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao:
New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity. - Eric Blais, Clément Louis Canonne, Tom Gur:
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.). - Elad Haramaty, Chin Ho Lee, Emanuele Viola:
Bounded independence plus noise fools products. - Thomas Watson:
Communication Complexity of Statistical Distance. - Daniel Minahan, Ilya Volkovich:
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. - William M. Hoza, Adam R. Klivans:
Preserving Randomness for Adaptive Algorithms. - Egor Klenin, Alexander Kozachinsky:
One-sided error communication complexity of Gap Hamming Distance. - Elchanan Mossel, Sampath Kannan, Grigory Yaroslavtsev:
Linear Sketching over 𝔽2. - Pavel Pudlák, Neil Thapen:
Random resolution refutations. - Venkata Gandikota, Badih Ghazi, Elena Grigorescu:
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem. - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures. - Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price:
Collision-based Testers are Optimal for Uniformity and Closeness. - Avishay Tal:
Computing Requires Larger Formulas than Approximating. - Eshan Chattopadhyay, Xin Li:
Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions. - Avishay Tal:
The Bipartite Formula Complexity of Inner-Product is Quadratic. - Rohit Gurjar, Thomas Thierauf:
Linear Matroid Intersection is in quasi-NC. - Joshua Brakensiek, Venkatesan Guruswami:
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. - Alexander A. Razborov:
On Space and Depth in Resolution. - Vijay V. S. P. Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Multiplicative Approximations for Polynomial Optimization Over the Unit Sphere. - Jayadev Acharya, Hirakendu Das, Alon Orlitsky, Ananda Theertha Suresh:
A Unified Maximum Likelihood Approach for Optimal Distribution Property Estimation. - Morris Yau:
Almost Cubic Bound for Depth Three Circuits in VP. - Toniann Pitassi, Robert Robere:
Strongly Exponential Lower Bounds for Monotone Computation. - Arnab Bhattacharyya, Sivakanth Gopi:
Lower bounds for 2-query LCCs over large alphabet. - Yuval Dagan, Yuval Filmus, Hamed Hatami, Yaqiao Li:
Trading information complexity for error. - Roei Tell:
Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. - Oded Goldreich, Tom Gur:
Universal Locally Verifiable Codes and 3-Round Interactive Proofs of Proximity for CSP. - Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, Raja S:
Identity Testing for +-Regular Noncommutative Arithmetic Circuits. - Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, Ronald L. Rivest, Madhu Sudan:
The Optimality of Correlated Sampling. - Pasin Manurangsi:
Almost-Polynomial Ratio ETH-Hardness of Approximating Densest k-Subgraph. - Igor Carboni Oliveira, Rahul Santhanam:
Pseudodeterministic Constructions in Subexponential Time. - Igor Carboni Oliveira, Rahul Santhanam:
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. - Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
Towards a Proof of the 2-to-1 Games Conjecture? - Pavel Hubácek, Moni Naor, Eylon Yogev:
The Journey from NP to TFNP Hardness. - Scott Aaronson, Lijie Chen:
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. - Eric Blais, Yuichi Yoshida:
A Characterization of Constant-Sample Testable Properties. - Dmitry Sokolov:
Dag-like Communication and Its Applications. - Christoph Berkholz, Jakob Nordström:
Supercritical Space-Width Trade-offs for Resolution. - Prahladh Harsha, Srikanth Srinivasan:
Robust Multiplication-based Tests for Reed-Muller Codes. - Amey Bhangale, Irit Dinur, Inbal Livni Navon:
Cube vs. Cube Low Degree Test. - Benjamin Rossman:
An Improved Homomorphism Preservation Theorem From Lower Bounds in Circuit Complexity.
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-13 19:01 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:
