default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2020
Volume TR20, 2020
- Or Meir, Jakob Nordström, Robert Robere, Susanna F. de Rezende:
Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. Article TR20-001 - Sophie Laplante, Reza Naserasr, Anupa Sunny:
Sensitivity lower bounds from linear dependencies. Article TR20-002 - Giuseppe Persiano, Kevin Yeo:
Tight Static Lower Bounds for Non-Adaptive Data Structures. Article TR20-003 - Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný:
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Article TR20-004 - Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan:
Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution. Article TR20-005 - Anup Rao, Amir Yehudayoff:
The Communication Complexity of the Exact Gap-Hamming Problem. Article TR20-006 - Claude Crépeau, Arnaud Massenet, Louis Salvail, Lucas Stinchcombe, Nan Yang:
Practical Relativistic Zero-Knowledge for NP. Article TR20-007 - Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter:
Better Secret-Sharing via Robust Conditional Disclosure of Secrets. Article TR20-008 - Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra
:
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. Article TR20-009 - Lijie Chen, Hanlin Ren:
Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization. Article TR20-010 - Dominik Scheder, Navid Talebanfard:
Super Strong ETH is true for strong PPSZ. Article TR20-011 - Dmitry Sokolov:
(Semi)Algebraic Proofs over ±1 Variables. Article TR20-012 - Noga Ron-Zewi, Mary Wootters, Gilles Zémor:
Linear-time Erasure List-decoding of Expander Codes. Article TR20-013 - Gil Cohen, Shahar Samocha:
Palette-Alternating Tree Codes. Article TR20-014 - Emanuele Viola:
New lower bounds for probabilistic degree and AC0 with parity gates. Article TR20-015 - Kuan Cheng, William Hoza:
Hitting Sets Give Two-Sided Derandomization of Small Space. Article TR20-016 - Alexander Kozachinskiy, Vladimir V. Podolskii:
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Article TR20-017 - Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira:
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. Article TR20-018 - Siddharth Bhandari, Prahladh Harsha:
A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet. Article TR20-019 - Nikhil S. Mande, Justin Thaler, Shuchen Zhu:
Improved Approximate Degree Bounds For $k$-distinctness. Article TR20-020 - Rahul Ilango, Bruno Loff, Igor Carboni Oliveira:
NP-Hardness of Circuit Minimization for Multi-Output Functions. Article TR20-021 - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive Error Resilience Beyond 2/7. Article TR20-022 - Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan:
Non-Malleability against Polynomial Tampering. Article TR20-023 - Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari:
Randomized and Symmetric Catalytic Computation. Article TR20-024 - Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari:
Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs. Article TR20-025 - Dean Doron, Jack Murtagh, Salil P. Vadhan, David Zuckerman:
Spectral Sparsification via Bounded-Independence Sampling. Article TR20-026 - Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, Li-Yang Tan:
The Power of Many Samples in Query Complexity. Article TR20-027 - Nikhil Gupta, Chandan Saha, Bhargav Thankey:
A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. Article TR20-028 - Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam:
Geometric Rank of Tensors and Subrank of Matrix Multiplication. Article TR20-029 - Matthias Christandl, François Le Gall, Vladimir Lysikov, Jeroen Zuiddam:
Barriers for Rectangular Matrix Multiplication. Article TR20-030 - Markus Bläser, Christian Ikenmeyer, Meena Mahajan, Anurag Pandey, Nitin Saurabh:
Algebraic Branching Programs, Border Complexity, and Tangent Spaces. Article TR20-031 - Suryajith Chillara:
On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits. Article TR20-032 - Suryajith Chillara:
New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree. Article TR20-033 - Erfan Khaniki:
On Proof complexity of Resolution over Polynomial Calculus. Article TR20-034 - Justin Holmgren:
No-Signaling MIPs and Faster-Than-Light Communication, Revisited. Article TR20-035 - Olaf Beyersdorff, Joshua Blinkhorn, Tomás Peitl:
Strong (D)QBF Dependency Schemes via Tautology-free Resolution Paths. Article TR20-036 - Michal Garlík:
Failure of Feasible Disjunction Property for $k$-DNF Resolution and NP-hardness of Automating It. Article TR20-037 - Ofer Grossman, Justin Holmgren:
Error Correcting Codes for Uncompressed Messages. Article TR20-038 - Pranjal Dutta, Nitin Saxena, Thomas Thierauf:
Lower bounds on the sum of 25th-powers of univariates lead to complete derandomization of PIT. Article TR20-039 - Andrei A. Krokhin, Jakub Oprsal, Marcin Wrochna, Stanislav Zivný:
Topology and adjunction in promise constraint satisfaction. Article TR20-040 - Mrinal Kumar, Ben Lee Volk:
A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits. Article TR20-041 - Pranav Bisht, Nitin Saxena:
Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs. Article TR20-042 - Dorit Aharonov, Alex Bredariol Grilo:
A combinatorial MA-complete problem. Article TR20-043 - Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Nalini Vasudevan:
Cryptography from Information Loss. Article TR20-044 - Ankit Garg, Neeraj Kayal, Chandan Saha:
Learning sums of powers of low-degree polynomials in the non-degenerate case. Article TR20-045 - Srikanth Srinivasan:
A Robust Version of Hegedűs's Lemma, with Applications. Article TR20-046 - Ronen Shaltiel, Jad Silbak:
Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity. Article TR20-047 - Shachar Lovett, Raghu Meka, Jiapeng Zhang:
Improved lifting theorems via robust sunflowers. Article TR20-048 - Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi:
Automating Cutting Planes is NP-Hard. Article TR20-049 - Shuichi Hirahara:
Unexpected Hardness Results for Kolmogorov Complexity Under Uniform Reductions. Article TR20-050 - Rafael Pass, Muthuramakrishnan Venkitasubramaniam:
Is it Easier to Prove Theorems that are Guaranteed to be True? Article TR20-051 - Yanyi Liu, Rafael Pass:
On One-way Functions and Kolmogorov Complexity. Article TR20-052 - Olaf Beyersdorff, Benjamin Böhm:
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution. Article TR20-053 - Marshall Ball, Oded Goldreich, Tal Malkin:
Communication Complexity with Defective Randomness. Article TR20-054 - Ashutosh Kumar, Raghu Meka, David Zuckerman:
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing. Article TR20-055 - James Cook, Ian Mertz:
Catalytic Approaches to the Tree Evaluation Problem. Article TR20-056 - Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein:
Polynomial Data Structure Lower Bounds in the Group Model. Article TR20-057 - Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff:
Interactive Proofs for Verifying Machine Learning. Article TR20-058 - Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma:
Pr-ZSUBEXP is not contained in Pr-RP. Article TR20-059 - Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li:
Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols. Article TR20-060 - Deepanshu Kush, Benjamin Rossman:
Tree-depth and the Formula Complexity of Subgraph Isomorphism. Article TR20-061 - Clément L. Canonne, Karl Wimmer:
Testing Data Binnings. Article TR20-062 - Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse:
On the Existence of Algebraically Natural Proofs. Article TR20-063 - Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende:
Automating Algebraic Proof Systems is NP-Hard. Article TR20-064 - Lijie Chen, Ce Jin, R. Ryan Williams:
Sharp Threshold Results for Computational Complexity. Article TR20-065 - Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal:
Quantum Implications of Huang's Sensitivity Theorem. Article TR20-066 - Dmitry Itsykson, Alexander Okhotin, Vsevolod Oparin:
Computational and proof complexity of partial string avoidability. Article TR20-067 - Oded Goldreich, Dana Ron:
One-Sided Error Testing of Monomials and Affine Subspaces. Article TR20-068 - Eshan Chattopadhyay, Jyun-Jie Liao:
Optimal Error Pseudodistributions for Read-Once Branching Programs. Article TR20-069 - Ben Lund, Aditya Potukuchi:
On the list recoverability of randomly punctured codes. Article TR20-070 - Iftach Haitner, Yonatan Karidi-Heller:
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. Article TR20-071 - Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi:
Locally testable codes via high-dimensional expanders. Article TR20-072 - Sam Buss, Dmitry Itsykson, Alexander Knop, Artur Riazanov, Dmitry Sokolov:
Lower Bounds on OBDD Proofs with Several Orders. Article TR20-073 - Eric Allender, Archit Chauhan, Samir Datta:
Depth-First Search in Directed Graphs, Revisited. Article TR20-074 - Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal:
Rigid Matrices From Rectangular PCPs. Article TR20-075 - Benny Applebaum, Eliran Kachlon, Arpita Patra:
The Round Complexity of Perfect MPC with Active Security and Optimal Resiliency. Article TR20-076 - Amit Sinhababu, Thomas Thierauf:
Factorization of Polynomials Given by Arithmetic Branching Programs. Article TR20-077 - Eric Allender:
The New Complexity Landscape around Circuit Minimization. Article TR20-078 - Hermann Gruber, Markus Holzer, Simon Wolfsteiner:
On Minimizing Regular Expressions Without Kleene Star. Article TR20-079 - Joan Bruna, Oded Regev, Min Jae Song, Yi Tang:
Continuous LWE. Article TR20-080 - Robert Andrews:
Algebraic Hardness versus Randomness in Low Characteristic. Article TR20-081 - Yuval Filmus, Meena Mahajan, Gaurav Sood, Marc Vinyals:
MaxSAT Resolution and Subcube Sums. Article TR20-082 - Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf:
Proximity Gaps for Reed-Solomon Codes. Article TR20-083 - Gil Cohen, Tal Yankovitz:
Rate Amplification and Query-Efficient Distance Amplification for Locally Decodable Codes. Article TR20-084 - Gal Vardi, Ohad Shamir:
Neural Networks with Small Weights and Depth-Separation Barriers. Article TR20-085 - Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Article TR20-086 - Uma Girish, Ran Raz, Wei Zhan:
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. Article TR20-087 - Bill Fefferman, Zachary Remscrim:
Eliminating Intermediate Measurements in Space-Bounded Quantum Computation. Article TR20-088 - Dror Chawin, Iftach Haitner, Noam Mazor:
Lower Bounds on the Time/Memory Tradeoff of Function Inversion. Article TR20-089 - Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian:
Tight Quantum Time-Space Tradeoffs for Function Inversion. Article TR20-090 - Janaky Murthy, Vineet Nair, Chandan Saha:
Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests. Article TR20-091 - Ashish Dwivedi, Nitin Saxena:
Computing Igusa's local zeta function of univariates in deterministic polynomial-time. Article TR20-092 - Ronen Eldan, Dana Moshkovitz:
Reduction From Non-Unique Games To Boolean Unique Games. Article TR20-093 - Ronen Shaltiel:
Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? Article TR20-094 - Mikito Nanashima:
On Basing Auxiliary-Input Cryptography on NP-hardness via Nonadaptive Black-Box Reductions. Article TR20-095 - Igor Sergeev:
On the asymptotic complexity of sorting. Article TR20-096 - Md Lutfar Rahman, Thomas Watson:
6-Uniform Maker-Breaker Game Is PSPACE-Complete. Article TR20-097 - Manindra Agrawal, Rohit Gurjar, Thomas Thierauf:
Impossibility of Derandomizing the Isolation Lemma for all Families. Article TR20-098 - Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. Article TR20-099 - Amit Chakrabarti, Prantar Ghosh, Justin Thaler:
Streaming Verification for Graph Problems: Optimal Tradeoffs and Nonlinear Sketches. Article TR20-100 - Uma Girish, Ran Raz, Wei Zhan:
Lower Bounds for XOR of Forrelations. Article TR20-101 - Stasys Jukna:
Notes on Hazard-Free Circuits. Article TR20-102 - Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida:
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. Article TR20-103 - Oded Goldreich:
On Counting $t$-Cliques Mod 2. Article TR20-104 - Zoë Bell:
Automating Regular or Ordered Resolution is NP-Hard. Article TR20-105 - Eshan Chattopadhyay, Jesse Goodman:
Explicit Extremal Designs and Applications to Extractors. Article TR20-106 - Lior Gishboliner, Asaf Shapira, Henrique Stagni:
Testing linear inequalities of subgraph statistics. Article TR20-107 - Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar:
Query Complexity of Global Minimum Cut. Article TR20-108 - Oded Goldreich:
On Testing Hamiltonicity in the Bounded Degree Graph Model. Article TR20-109 - Leonid Gurvits, Jonathan Leake:
Capacity Lower Bounds via Productization. Article TR20-110 - Ian Mertz, Toniann Pitassi:
Lifting: As Easy As 1, 2, 3. Article TR20-111 - Joshua Blinkhorn:
Simulating DQBF Preprocessing Techniques with Resolution Asymmetric Tautologies. Article TR20-112 - Alessandro Chiesa, Tom Gur, Igor Shinkar:
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity. Article TR20-113 - Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar:
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond. Article TR20-114 - Scott Aaronson:
The Busy Beaver Frontier. Article TR20-115 - Ivan Mihajlin, Alexander Smal:
Toward better depth lower bounds: the XOR-KRW conjecture. Article TR20-116 - Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov:
New bounds on the half-duplex communication complexity. Article TR20-117 - Oded Goldreich:
On Testing Asymmetry in the Bounded Degree Graph Model. Article TR20-118 - Nikhil S. Mande, Swagato Sanyal:
On parity decision trees for Fourier-sparse Boolean functions. Article TR20-119 - Justin Holmgren, Ran Raz:
A Parallel Repetition Theorem for the GHZ Game. Article TR20-120 - Eshan Chattopadhyay, Jason Gaitonde, Abhishek Shetty:
Fractional Pseudorandom Generators from the $k$th Fourier Level. Article TR20-121 - Joshua Cook:
Size Bounds on Low Depth Circuits for Promise Majority. Article TR20-122 - Nader H. Bshouty:
An Optimal Tester for k-Linear. Article TR20-123 - Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu:
A Strong XOR Lemma for Randomized Query Complexity. Article TR20-124 - Gaurav Sinha:
Efficient reconstruction of depth three circuits with top fan-in two. Article TR20-125 - Aayush Jain, Huijia Lin, Amit Sahai:
Indistinguishability Obfuscation from Well-Founded Assumptions. Article TR20-126 - Nikhil Bansal, Makrand Sinha:
$k$-Forrelation Optimally Separates Quantum and Classical Query Complexity. Article TR20-127 - Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu:
An Optimal Separation of Randomized and Quantum Query Complexity. Article TR20-128 - Mrinal Kumar, Ben Lee Volk:
A Lower Bound on Determinantal Complexity. Article TR20-129 - Amey Bhangale, Subhash Khot:
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups. Article TR20-130 - Rahul Jain, Srijita Kundu:
A Direct Product Theorem for One-Way Quantum Communication. Article TR20-131 - Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif:
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture. Article TR20-132 - Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma:
Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists). Article TR20-133 - Siddhesh Chaubal, Anna Gál:
Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions. Article TR20-134 - Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen:
Estimation of Graph Isomorphism Distance in the Query World. Article TR20-135 - Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani:
Explicit and structured sum of squares lower bounds from high dimensional expanders. Article TR20-136 - Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena:
Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes. Article TR20-137 - William Hoza, Edward Pyne, Salil P. Vadhan:
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. Article TR20-138 - Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. Article TR20-139 - Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, Eric Price:
Optimal Testing of Discrete Distributions with High Probability. Article TR20-140 - Inbar Ben Yaacov, Gil Cohen, Anand Kumar Narayanan:
Candidate Tree Codes via Pascal Determinant Cubes. Article TR20-141 - Vahid R. Asadi, Igor Shinkar:
Relaxed Locally Correctable Codes with Improved Parameters. Article TR20-142 - Shuichi Hirahara:
Characterizing Average-Case Complexity of PH by Worst-Case Meta-Complexity. Article TR20-143 - Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar:
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality. Article TR20-144 - Andrew Drucker:
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature. Article TR20-145 - Scott Aaronson, Yosi Atia, Leonard Susskind:
On the Hardness of Detecting Macroscopic Superpositions. Article TR20-146 - Inbar Kaslasi, Prashant Nalini Vasudevan, Guy N. Rothblum, Ron Rothblum, Adam Sealfon:
Batch Verification for Statistical Zero Knowledge Proofs. Article TR20-147 - Lijie Chen, Roei Tell:
Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost. Article TR20-148 - Oded Goldreich, Avi Wigderson:
Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. Article TR20-149 - Lijie Chen, Xin Lyu, Ryan Williams:
Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. Article TR20-150 - Venkatesan Guruswami, Vinayak M. Kumar:
Pseudobinomiality of the Sticky Random Walk. Article TR20-151 - Prasad Chaugule, Nutan Limaye, Shourya Pandey:
Variants of the Determinant polynomial and VP-completeness. Article TR20-152 - Robert Kleinberg, Daniel Mitropolsky, Christos H. Papadimitriou:
Total Functions in the Polynomial Hierarchy. Article TR20-153 - Marcel de Sena Dall'Agnol, Tom Gur, Oded Lachish:
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy. Article TR20-154 - Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan:
Log-rank and lifting for AND-functions. Article TR20-155 - Sankeerth Rao Karingula, Shachar Lovett:
Codes over integers, and the singularity of random matrices with large entries. Article TR20-156 - Guy N. Rothblum, Ron Rothblum:
Batch Verification and Proofs of Proximity with Polylog Overhead. Article TR20-157 - Eric Allender, Azucena Garvía Bosshard, Amulya Musipatla:
A Note on Hardness under Projections for Graph Isomorphism and Time-Bounded Kolmogorov Complexity. Article TR20-158 - Leroy Chew:
Relating existing powerful proof systems for QBF. Article TR20-159 - Oded Goldreich, Avi Wigderson:
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. Article TR20-160 - Gil Cohen, Dean Doron, Shahar Samocha:
Seed Protecting Extractors. Article TR20-161 - Dean Doron, Mary Wootters:
High-Probability List-Recovery, and Applications to Heavy Hitters. Article TR20-162 - Gil Cohen, Noam Peri, Amnon Ta-Shma:
Expander Random Walks: A Fourier-Analytic Approach. Article TR20-163 - Andrej Bogdanov, Gautam Prakriya:
Direct Sum and Partitionability Testing over General Groups. Article TR20-164 - Sarah Bordage, Jade Nardi:
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes. Article TR20-165 - Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay:
Lower Bounds for Monotone Arithmetic Circuits Via Communication Complexity. Article TR20-166 - Venkatesan Guruswami, Sai Sandeep:
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture. Article TR20-167 - Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters:
Improved List-Decodability of Reed-Solomon Codes via Tree Packings. Article TR20-168 - Zeyu Guo, Noga Ron-Zewi:
Efficient List-Decoding with Constant Alphabet and List Sizes. Article TR20-169 - Max Hopkins, Tali Kaufman, Shachar Lovett:
High Dimensional Expanders: Random Walks, Pseudorandomness, and Unique Games. Article TR20-170 - Russell Impagliazzo, Sam McGuire:
Comparing computational entropies below majority (or: When is the dense model theorem false?). Article TR20-171 - Venkatesan Guruswami, Chaoping Xing:
Optimal rate list decoding over bounded alphabets using algebraic-geometric codes. Article TR20-172 - Kunal Mittal, Ran Raz:
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines. Article TR20-173 - Hadley Black, Iden Kalemaj, Sofya Raskhodnikova:
Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing. Article TR20-174 - Emanuele Viola:
Fourier conjectures, correlation bounds, and Majority. Article TR20-175 - Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona:
Outcome Indistinguishability. Article TR20-176 - Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira:
Counting Subgraphs in Degenerate Graphs. Article TR20-177 - Stasys Jukna, Hannes Seiwert, Igor Sergeev:
Reciprocal Inputs in Arithmetic and Tropical Circuits. Article TR20-178 - Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan:
Decoding Multivariate Multiplicity Codes on Product Sets. Article TR20-179 - Yuval Filmus, Or Meir, Avishay Tal:
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. Article TR20-180 - Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman:
Monotone Circuit Lower Bounds from Robust Sunflowers. Article TR20-181 - Zander Kelley:
An Improved Derandomization of the Switching Lemma. Article TR20-182 - Rahul Ilango:
Constant Depth Formula and Partial Function Versions of MCSP are Hard. Article TR20-183 - Dmitry Itsykson, Artur Riazanov:
Proof complexity of natural formulas via communication arguments. Article TR20-184 - Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram:
Quantum learning algorithms imply circuit lower bounds. Article TR20-185 - Benjamin Rossman:
Shrinkage of Decision Lists and DNF Formulas. Article TR20-186 - Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse:
If VNP is hard, then so are equations for it. Article TR20-187 - Olaf Beyersdorff, Joshua Blinkhorn, Meena Mahajan, Tomás Peitl, Gaurav Sood:
Hard QBFs for Merge Resolution. Article TR20-188 - Pavel Hrubes, Amir Yehudayoff:
Shadows of Newton polytopes. Article TR20-189 - Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Erasure-Resilient Sublinear-Time Graph Algorithms. Article TR20-190 - Arkadev Chattopadhyay, Rajit Datta, Partha Mukhopadhyay:
Negations Provide Strongly Exponential Savings. Article TR20-191 - Oded Goldreich, Avi Wigderson:
Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network. Article TR20-192 - Xuangui Huang, Emanuele Viola:
Average-case rigidity lower bounds. Article TR20-193
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 2026-10-17 00:59 CEST 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, funded, and maintained by:
Schloss Dagstuhl - Leibniz Center for Informatics is a member of the Leibniz Association and is funded by the federal government of Germany and the states of Germany, especially Saarland and Rhineland‑Palatinate.
