default search action
Electronic Colloquium on Computational Complexity, 2019
Volume TR19, 2019
- Dmitry Itsykson, Alexander Knop, Andrei E. Romashchenko, Dmitry Sokolov:
On OBDD-based algorithms and proof systems that dynamically change order of variables. - Alexander S. Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir V. Podolskii:
Complexity of Linear Operators. - Alexander A. Sherstov, Pei Wu:
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. - Amey Bhangale, Subhash Khot:
UG-hardness to NP-hardness by Losing Half. - Omar Alrabiah, Venkatesan Guruswami:
An Exponential Lower Bound on the Sub-Packetization of MSR Codes. - Anna Gál, Ridwan Syed:
Upper Bounds on Communication in terms of Approximate Rank. - Arkadev Chattopadhyay, Meena Mahajan, Nikhil S. Mande, Nitin Saurabh:
Lower Bounds for Linear Decision Lists. - Ashish Dwivedi, Rajat Mittal, Nitin Saxena:
Efficiently factoring polynomials modulo $p^4$. - Jiawei Gao, Russell Impagliazzo:
The Fine-Grained Complexity of Strengthenings of First-Order Logic. - Dorit Aharonov, Alex Bredariol Grilo:
Stoquastic PCP vs. Randomness. - Benny Applebaum, Eliran Kachlon:
Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders. - Oded Goldreich:
Multi-pseudodeterministic algorithms. - Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami:
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. - Himanshu Tyagi, Shun Watanabe:
A New Proof of Nonsignalling Multiprover Parallel Repetition Theorem. - William Kretschmer:
QMA Lower Bounds for Approximate Counting. - Alexander A. Sherstov:
The hardest halfspace. - Chin Ho Lee:
Fourier bounds and pseudorandom generators for product tests. - Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal:
AC0[p] Lower Bounds against MCSP via the Coin Problem. - Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi:
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. - Ludmila Glinskih, Dmitry Itsykson:
On Tseitin formulas, read-once branching programs and treewidth. - Rahul Ilango:
$AC^0[p]$ Lower Bounds and NP-Hardness for Variants of MCSP. - Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis:
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. - Orr Paradise:
Smooth and Strong PCPs. - Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. - Shuichi Hirahara, Osamu Watanabe:
On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets. - Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff:
Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. - Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. - Shachar Lovett, Noam Solomon, Jiapeng Zhang:
From DNF compression to sunflower theorems via regularity. - Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami, David Zuckerman:
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions. - Claude Crépeau, Nan Yang:
Non-Locality in Interactive Proofs. - Lijie Chen:
Non-deterministic Quasi-Polynomial Time is Average-case Hard for ACC Circuits. - Srikanth Srinivasan:
Strongly Exponential Separation Between Monotone VP and Monotone VNP. - Ashish Dwivedi, Rajat Mittal, Nitin Saxena:
Counting basic-irreducible factors mod $p^k$ in deterministic poly-time and $p$-adic applications. - Pavel Hrubes:
On $\epsilon$-sensitive monotone computations. - Alexey Milovanov:
PIT for depth-4 circuits and Sylvester-Gallai theorem for polynomials. - Pavel Hrubes:
On the complexity of computing a random Boolean function over the reals. - Chi-Ning Chou, Mrinal Kumar, Noam Solomon:
Closure of VP under taking factors: a short and simple proof. - Itay Berman, Akshay Degwekar, Ron D. Rothblum, Prashant Nalini Vasudevan:
Statistical Difference Beyond the Polarizing Regime. - Eric Allender, Archit Chauhan, Samir Datta, Anish Mukherjee:
Planarity, Exclusivity, and Unambiguity. - Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis:
The Complexity of Finding S-factors in Regular Graphs. - Srinivasan Arunachalam, Alex Bredariol Grilo, Aarthi Sundaram:
Quantum hardness of learning shallow classical circuits. - Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha:
Determinant equivalence test over finite fields and over ℚ. - Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. - Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf:
DEEP-FRI: Sampling Outside the Box Improves Soundness. - Jiawei Gao:
On the Fine-grained Complexity of Least Weight Subsequence in Graphs. - Akash Kumar, C. Seshadhri, Andrew Stolman:
andom walks and forbidden minors II: A poly(dε-1)$-query tester for minor-closed properties of bounded degree graphs. - Mrinal Kumar, Ben Lee Volk:
Lower Bounds for Matrix Factorization. - Per Austrin, Amey Bhangale, Aditya Potukuchi:
Simplified inpproximability of hypergraph coloring via t-agreeing families. - Itay Berman, Iftach Haitner, Eliad Tsfadia:
A Tight Parallel-Repetition Theorem for Random-Terminating Interactive Arguments. - Titus Dose, Christian Glaßer:
NP-Completeness, Proof Systems, and Disjoint NP-Pairs. - Emanuele Viola:
Pseudorandom bits and lower bounds for randomized Turing machines. - Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen:
Polynomial calculus space and resolution width. - Andrei A. Krokhin, Jakub Oprsal:
The complexity of 3-colouring H-colourable graphs. - Joshua Brakensiek, Venkatesan Guruswami:
Bridging between 0/1 and Linear Programming via Random Walks. - Kasper Green Larsen, Tal Malkin, Omri Weinstein, Kevin Yeo:
Lower Bounds for Oblivious Near-Neighbor Search. - Tom Gur, Oded Lachish:
A Lower Bound for Relaxed Locally Decodable Codes. - Olaf Beyersdorff, Joshua Blinkhorn:
Proof Complexity of Symmetry Learning in QBF. - Pavel Pudlák, Vojtech Rödl:
Extractors for small zero-fixing sources. - Rohit Agrawal:
Samplers and extractors for unbounded functions. - Scott Aaronson, Guy N. Rothblum:
Gentle Measurement of Quantum States and Differential Privacy. - Scott Aaronson, Daniel Grier, Luke Schaeffer:
A Quantum Query Complexity Trichotomy for Regular Languages. - Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. - Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay:
Efficient Black-Box Identity Testing for Free Group Algebra. - Igor Carboni Oliveira:
Randomness and Intractability in Kolmogorov Complexity. - Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon:
Derandomization from Algebraic Hardness: Treading the Borders. - Thomas Watson:
A Lower Bound for Sampling Disjoint Sets. - Hamed Hatami, Kaave Hosseini, Shachar Lovett:
Sign rank vs Discrepancy. - Shuo Pang:
Large Clique is Hard on Average for Resolution. - Nicola Galesi, Dmitry Itsykson, Artur Riazanov, Anastasia Sofronova:
Bounded-depth Frege complexity of Tseitin formulas for all graphs. - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Local Testability in the Non-Signaling Setting. - Sumegha Garg, Ran Raz, Avishay Tal:
Time-Space Lower Bounds for Two-Pass Learning. - Lijie Chen, Ofer Grossman:
Broadcast Congested Clique: Planted Cliques and Pseudorandom Generators. - Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan:
Parity helps to compute Majority. - Arka Rai Choudhuri, Pavel Hubácek, Chethan Kamath, Krzysztof Pietrzak, Alon Rosen, Guy N. Rothblum:
Finding a Nash Equilibrium Is No Easier Than Breaking Fiat-Shamir. - Lijie Chen, Dylan M. McKay, Cody Murray, R. Ryan Williams:
Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems. - Leroy Chew, Judith Clymo:
The Equivalences of Refutational QRAT. - Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek:
Consistency of circuit lower bounds with bounded theories. - Itai Benjamini, Oded Goldreich:
Pseudo-Mixing Time of Random Walks. - Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka:
Average Bias and Polynomial Sources. - Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, Shashwat Silas:
On List Recovery of High-Rate Tensor Codes. - Iftach Haitner, Noam Mazor, Ronen Shaltiel, Jad Silbak:
Channels of Small Log-Ratio Leakage and Characterization of Two-Party Differentially Private Computation. - Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, Christopher Williamson:
Approximate degree, secret sharing, and concentration phenomena. - Lior Gishboliner, Asaf Shapira:
Testing Graphs against an Unknown Distribution. - Michal Garlík:
Resolution Lower Bounds for Refutation Statements. - Xuangui Huang, Emanuele Viola:
Approximate Degree-Weight and Indistinguishability. - Alex Bredariol Grilo, William Slofstra, Henry Yuen:
Perfect zero knowledge for quantum multiprover interactive proofs. - Rohit Agrawal:
Coin Theorems and the Fourier Expansion. - Oded Goldreich:
On the Complexity of Estimating the Effective Support Size. - Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal:
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. - Ronen Shaltiel, Swastik Kopparty, Jad Silbak:
Quasilinear time list-decodable codes for space bounded channels. - Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, N. V. Vinodchandran, Osamu Watanabe:
A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs. - Venkatesan Guruswami, Jakub Oprsal, Sai Sandeep:
Revisiting Alphabet Reduction in Dinur's PCP. - Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari:
Improved 3LIN Hardness via Linear Label Cover. - Venkatesan Guruswami, Sai Sandeep:
Rainbow coloring hardness via low sensitivity polymorphisms. - Chetan Gupta, Rahul Jain, Vimal Raj Sharma, Raghunath Tewari:
Unambiguous Catalytic Computation. - Aditya Potukuchi:
On the AC0[⊕] complexity of Andreev's Problem. - Jacobo Torán, Florian Wörz
:
Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space. - Jayadev Acharya, Clément L. Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi:
Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit. - Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman:
Nearly Optimal Pseudorandomness From Hardness. - Hervé Fournier, Guillaume Malod, Maud Szusterman, Sébastien Tavenas:
Nonnegative rank measures and monotone algebraic branching programs. - Amit Chakrabarti, Prantar Ghosh:
Streaming Verification of Graph Computations via Graph Structure. - Oded Goldreich:
Testing Isomorphism in the Bounded-Degree Graph Model. - Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. - Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich:
Reconstruction of Depth-$4$ Multilinear Circuits. - Ragesh Jaiswal:
A note on the relation between XOR and Selective XOR Lemmas. - Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. - Zachary Remscrim:
The Power of a Single Qubit: Two-way Quantum/Classical Finite Automata and the Word Problem for Linear Groups. - Chaoping Xing, Chen Yuan:
Beating the probabilistic lower bound on perfect hashing. - Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh:
Decoding Downset codes over a finite grid. - Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Improved bounds for the sunflower lemma. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Noisy Beeps. - Yotam Dikstein, Irit Dinur:
Agreement testing theorems on layered set systems. - Tomer Grossman, Ilan Komargodski, Moni Naor:
Instance Complexity and Unlabeled Certificates in the Decision Tree Model. - Visu Makam, Avi Wigderson:
Singular tuples of matrices is not a null cone (and, the symmetries of algebraic varieties). - Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx:
Parameterized Intractability of Even Set and Shortest Vector Problem. - Venkatesan Guruswami, Sai Sandeep:
$d$-to-$1$ Hardness of Coloring $4$-colorable Graphs with $O(1)$ colors. - Silas Richelson
Locally Testable Non-Malleable Codes. - Lijie Chen, Ce Jin, Ryan Williams:
Hardness Magnification for all Sparse NP Languages. - Dean Doron, Amnon Ta-Shma, Roei Tell:
On Hitting-Set Generators for Polynomials that Vanish Rarely. - Or Meir:
Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation. - Alexander A. Sherstov, Justin Thaler:
Vanishing-Error Approximate Degree and QMA Complexity. - Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters:
LDPC Codes Achieve List-Decoding Capacity. - Pascale Gourdeau, Varun Kanade, Marta Kwiatkowska, James Worrell:
On the Hardness of Robust Classification. - Roy Gotlib, Tali Kaufman:
Testing Odd Direct Sums Using High Dimensional Expanders. - Elazar Goldenberg, Karthik C. S.:
Hardness Amplification of Optimization Problems. - Irit Dinur, Roy Meshulam:
Near Coverings and Cosystolic Expansion - an example of topological property testing. - Noga Ron-Zewi, Ron Rothblum:
Local Proofs Approaching the Witness Length. - Anna Gál, Robert Robere:
Lower Bounds for (Non-monotone) Comparator Circuits. - Zeev Dvir, Allen Liu:
Fourier and Circulant Matrices are Not Rigid. - Naomi Kirshner, Alex Samorodnitsky:
A moment ratio bound for polynomials and some extremal properties of Krawchouk polynomials and Hamming spheres. - Lieuwe Vinkhuijzen, André H. Deutz:
A Simple Proof of Vyalyi's Theorem and some Generalizations. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Radio Network Coding Requires Logarithmic Overhead. - Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi:
More on $AC^0[\oplus]$ and Variants of the Majority Function. - Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten:
Finding monotone patterns in sublinear time. - Michel X. Goemans, Shafi Goldwasser, Dhiraj Holden:
Doubly-Efficient Pseudo-Deterministic Proofs. - Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande, Manaswi Paraashar:
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead. - Shachar Lovett, Kewen Wu, Jiapeng Zhang:
Decision list compression by mild random restrictions. - Srikanth Srinivasan, Utkarsh Tripathi, S. Venkitesh:
On the Probabilistic Degrees of Symmetric Boolean functions. - Irit Dinur, Konstantin Golubev:
Direct sum testing - the general case. - Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson:
Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings. - Mark Braverman, Subhash Khot, Dor Minzer:
On Rich $2$-to-$1$ Games. - Yaroslav Alekseev, Dima Grigoriev, Edward A. Hirsch, Iddo Tzameret:
Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative? - Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian:
Equivalence of Systematic Linear Data Structures and Matrix Rigidity. - Young Ko, Omri Weinstein:
An Adaptive Step Toward the Multiphase Conjecture. - Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman:
XOR Lemmas for Resilient Functions Against Polynomials. - Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau:
Dynamic Kernels for Hitting Sets and Set Packing. - Gil Cohen, Shahar Samocha:
Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors. - Amey Bhangale, Subhash Khot:
Simultaneous Max-Cut is harder to approximate than Max-Cut. - Dean Doron, Pooya Hatami, William Hoza:
Log-Seed Pseudorandom Generators via Iterated Restrictions. - Stanislav Zák:
A Logical Characteristic of Read-Once Branching Programs. - Per Austrin, Jonah Brown-Cohen, Johan Håstad:
Optimal Inapproximability with Universal Factor Graphs. - Uma Girish, Ran Raz, Avishay Tal:
Quantum versus Randomized Communication Complexity, with Efficient Players. - Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi:
Optimally Resilient Codes for List-Decoding from Insertions and Deletions. - Venkatesan Guruswami, Andrii Riazanov, Min Ye:
Ar?kan meets Shannon: Polar codes with near-optimal convergence to channel capacity. - Rahul Santhanam:
Pseudorandomness and the Minimum Circuit Size Problem. - Nader H. Bshouty:
Almost Optimal Testers for Concise Representations. - Leroy Chew, Judith Clymo:
How QBF Expansion Makes Strategy Extraction Hard. - Stasys Jukna, Hannes Seiwert:
Sorting Can Exponentially Speed Up Pure Dynamic Programming. - Noah Stephens-Davidowitz, Vinod Vaikuntanathan:
SETH-hardness of Coding Problems. - Md Lutfar Rahman, Thomas Watson:
Tractable Unordered 3-CNF Games. - Suprovat Ghoshal, Rishi Saket:
Hardness of Learning DNFs using Halfspaces. - Ran Raz, Wei Zhan:
The Random-Query Model and the Memory-Bounded Coupon Collector. - Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten:
Approximating the Distance to Monotonicity of Boolean Functions. - Siddharth Bhandari, Sayantan Chakraborty:
Improved bounds for perfect sampling of $k$-colorings in graphs. - Clément L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten:
Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning. - Guy Blanc, Jane Lange, Li-Yang Tan:
Top-down induction of decision trees: rigorous guarantees and inherent limitations. - Anant Dhayal, Russell Impagliazzo:
UTIME Easy-witness Lemma & Some Consequences. - Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam:
Beyond Natural Proofs: Hardness Magnification and Locality. - Lijie Chen, Ron Rothblum, Roei Tell, Eylon Yogev:
On Exponential-Time Hypotheses, Derandomization, and Circuit Lower Bounds. - Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk:
A Quadratic Lower Bound for Algebraic Branching Programs. - Oded Goldreich:
Improved bounds on the AN-complexity of multilinear functions. - Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan:
Schur Polynomials do not have small formulas if the Determinant doesn't! - Divesh Aggarwal, Siyao Guo, Maciej Obremski, João Ribeiro, Noah Stephens-Davidowitz:
Extractor Lower Bounds, Revisited. - Susanna F. de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov:
Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs. - Emanuele Viola:
Matching Smolensky's correlation bound with majority. - Gal Arnon
On Prover-Efficient Public-Coin Emulation of Interactive Proofs. - Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-deterministic Streaming. - Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov:
Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs. - Avishay Tal:
Towards Optimal Separations between Quantum and Randomized Query Complexities. - Andreas Lenz, Cyrus Rashtchian, Paul H. Siegel, Eitan Yaakobi:
Covering Codes for Insertions and Deletions. - Michal Koucký, Vojtech Rödl, Navid Talebanfard:
A Separator Theorem for Hypergraphs and a CSP-SAT Algorithm. - Zachary Remscrim:
The Limitations of Few Qubits: One-way and Two-way Quantum Finite Automata and the Group Word Problem. - Marshall Ball
Randomness Extraction from Somewhat Dependent Sources. - Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li:
Extractors for Adversarial Sources via Extremal Hypergraphs. - Greg Bodwin, Ofer Grossman:
Strategy-Stealing is Non-Constructive. - Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende:
Lifting with Simple Gadgets and Applications to Circuit and Proof 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-09-30 20:48 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: