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