default search action
Electronic Colloquium on Computational Complexity, 2014
Volume TR14, 2014
- Swastik Kopparty, Shubhangi Saraf, Amir Shpilka:
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. - Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. - Zeev Dvir, Rafael Oliveira, Amir Shpilka:
Testing Equivalence of Polynomials under Shifts. - Hasan Abasi, Nader H. Bshouty, Ariel Gabizon, Elad Haramaty:
On r-Simple k-Path. - Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan:
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. - Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of Feedback Vertex Set for Bounded Length Cycles. - Mark Braverman, Klim Efremenko:
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. - N. Variyam Vinodchandran:
Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs. - Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. - Jean Bourgain, Zeev Dvir, Ethan Leeman:
Affine extractors over large fields with exponential error. - Dmitry Gavinsky, Pavel Pudlák:
Partition Expanders. - Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. - Mark Braverman, Kanika Pasricha:
The computational hardness of pricing compound options. - Olaf Beyersdorff, Leroy Chew:
The Complexity of Theorem Proving in Circumscription and Minimal Entailment. - Jack H. Lutz, Neil Lutz:
Lines Missing Every Random Point. - H. Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz:
The Complexity of Debate Checking. - Eli Ben-Sasson, Emanuele Viola:
Short PCPs with projection queries. - Arnab Bhattacharyya:
Polynomial decompositions in polynomial time. - Parikshit Gopalan, Amir Yehudayoff:
Inequalities and tail bounds for elementary symmetric polynomials. - Pavel Hrubes, Anup Rao:
Circuits with Medium Fan-In. - Clément L. Canonne, Ronitt Rubinfeld:
Testing probability distributions underlying aggregated data. - Shay Moran, Makrand Sinha, Amir Yehudayoff:
Fooling Pairs in Randomized Communication Complexity. - Gil Cohen, Anat Ganor, Ran Raz:
Two Sides of the Coin Problem. - Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. - Oded Goldreich, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. - Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf:
Lower Bounds for Approximate LDCs. - Andris Ambainis, Krisjanis Prusis:
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. - Vikraman Arvind, S. Raja:
The Complexity of Two Register and Skew Arithmetic Computation. - Oded Goldreich, Dana Ron:
On Learning and Testing Dynamic Environments. - Dana Moshkovitz:
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing. - João Marques-Silva, Mikolás Janota:
On the Query Complexity of Selecting Few Minimal Sets. - Olaf Beyersdorff, Leroy Chew:
Tableau vs. Sequent Calculi for Minimal Entailment. - Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen:
Candidate weak pseudorandom functions in AC0 ○ MOD2. - Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram:
On the complexity of trial and error for constraint satisfaction problems. - Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. Variyam Vinodchandran, Lin F. Yang
:
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. - Mikolas Janota, Leroy Chew, Olaf Beyersdorff:
On Unification of QBF Resolution-Based Calculi. - Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Succinct and explicit circuits for sorting and connectivity. - Ilario Bonacina, Nicola Galesi, Neil Thapen:
Total space in resolution. - Andrzej Lingas:
Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps : -). - Hamed Hatami, Pooya Hatami, Shachar Lovett:
General systems of linear forms: equidistribution and true complexity. - Shachar Lovett:
Recent advances on the log-rank conjecture in communication complexity. - Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. - Venkatesan Guruswami, Euiwoong Lee:
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. - Daniel Dewey:
Additively efficient universal computers. - Mrinal Kumar, Shubhangi Saraf:
On the power of homogeneous depth 4 arithmetic circuits. - Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. - Mark Braverman, Omri Weinstein:
An Interactive Information Odometer with Applications. - Avishay Tal:
Shrinkage of De Morgan Formulae from Quantum Query Complexity. - Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication. - Edward A. Hirsch, Dmitry Sokolov:
On the probabilistic closure of the loose unambiguous hierarchy. - Subhash Khot, Rishi Saket:
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors. - Joshua A. Grochow, Toniann Pitassi:
Circuit complexity, proof complexity, and polynomial identity testing. - Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: Catalytic space. - Dana Moshkovitz:
Parallel Repetition of Fortified Games. - Mika Göös, Thomas Watson:
Communication Complexity of Set-Disjointness for All Probabilities. - Zeev Dvir, Rafael Oliveira:
Factors of Sparse Polynomials are Sparse. - Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar:
Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness. - Ilya Volkovich:
On Learning, Lower Bounds and (un)Keeping Promises. - Boaz Barak, David Steurer
Sum-of-squares proofs and the quest toward optimal algorithms. - Anup Rao, Amir Yehudayoff:
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. - Raghav Kulkarni, Youming Qiao, Xiaoming Sun:
Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive. - Alexander Kozachinsky:
On the role of private coins in unbounded-round Information Complexity. - Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems into Gaussian Space. - Arkadev Chattopadhyay, Michael E. Saks:
The Power of Super-logarithmic Number of Players. - Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska:
Approximate Counting of Matchings in (3,3)-Hypergraphs. - Suguru Tamaki, Yuichi Yoshida:
Robust Approximation of Temporal CSP. - Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. - Eric Allender, Bireswar Das:
Zero Knowledge and Circuit Minimization. - Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, Manoj Prabhakaran:
Explicit Non-Malleable Codes Resistant to Permutations. - Vikraman Arvind, Gaurav Rattan
The Complexity of Geometric Graph Isomorphism. - Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. - Sajin Koroth, Jayalal Sarma:
Depth Lower Bounds against Circuits with Sparse Orientation. - Shachar Lovett, Cristopher Moore, Alexander Russell:
Group representations that resist random sampling. - Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra:
Topology matters in communication. - Holger Dell:
A simple proof that AND-compression of NP-complete problems is hard. - Thomas Steinke:
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs. - Andris Ambainis, Jevgenijs Vihrovs:
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. - Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. - Simon Straub, Thomas Thierauf, Fabian Wagner:
Counting the Number of Perfect Matchings in K5-free Graphs. - Stasys Jukna:
Lower Bounds for Tropical Circuits and Dynamic Programs. - Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals:
From Small Space to Small Width in Resolution. - Yu Yu, Dawu Gu, Xiangxue Li:
The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions. - Irit Dinur, Shafi Goldwasser, Huijia Lin:
The Computational Benefit of Correlated Instances. - Luke Schaeffer:
A Physically Universal Cellular Automaton. - Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Hitting-sets for ROABP and Sum of Set-Multilinear circuits. - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. - Abhishek Bhowmick, Shachar Lovett:
List decoding Reed-Muller codes over small fields. - Swagato Sanyal:
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity. - Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. - Justin Thaler:
Semi-Streaming Algorithms for Annotated Graph Streams. - Ryan O'Donnell, A. C. Cem Say:
One time-travelling bit is as good as logarithmically many. - Mark Braverman, Young Kun-Ko, Omri Weinstein:
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. - Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov:
Resolution complexity of perfect mathcing principles for sparse graphs. - Zeev Dvir, Sivakanth Gopi:
2-Server PIR with sub-polynomial communication. - Mark Braverman, Ankit Garg:
Small value parallel repetition for general games. - Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. - Oded Goldreich, Liav Teichner:
Super-Perfect Zero-Knowledge Proofs. - Amey Bhangale, Swastik Kopparty, Sushant Sachdeva:
Simultaneous Approximation of Constraint Satisfaction Problems. - Gil Cohen, Igor Shinkar:
The Complexity of DNF of Parities. - Salman Beigi, Omid Etesami, Amin Gohari:
The Value of Help Bits in Randomized and Average-Case Complexity. - Balthazar Bauer, Shay Moran, Amir Yehudayoff:
Internal compression of protocols to entropy. - Eshan Chattopadhyay, David Zuckerman:
Non-Malleable Codes Against Constant Split-State Tampering. - Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis:
A Unifying Hierarchy of Valuations with Complements and Substitutes. - Atri Rudra, Mary Wootters:
It'll probably work out: improved list-decoding through random operations. - Craig Gentry:
Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington's Theorem. - Craig Gentry:
Computing on the edge of chaos: Structure and randomness in encrypted computation. - Or Meir:
Locally Correctable and Testable Codes Approaching the Singleton Bound. - Andrej Bogdanov, Christina Brzuska:
On Basing Size-Verifiable One-Way Functions on NP-Hardness. - Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. - Uriel Feige, Shlomo Jozeph:
Separation between Estimation and Approximation. - Vikraman Arvind, Gaurav Rattan
Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity. - Louay Bazzi:
Entropy of weight distributions of small-bias spaces and pseudobinomiality. - Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication for Boolean Functions. - Roei Tell:
An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions. - Roei Tell:
Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees. - Rahul Mehta:
2048 is (PSPACE) Hard, but Sometimes Easy. - Shiva Manne, Manjish Pal:
Fast Approximate Matrix Multiplication by Solving Linear Systems. - Albert Atserias, Massimo Lauria, Jakob Nordström:
Narrow Proofs May Be Maximally Long. - Mark Braverman, Jieming Mao:
Simulating Noisy Channel Interaction. - Olaf Beyersdorff, Leroy Chew, Mikolas Janota:
Proof Complexity of Resolution-based QBF Calculi. - Sebastian Müller:
Graph Structure and Parity Games. - Eric Allender, Anna Gál, Ian Mertz:
Dual VP Classes. - Shachar Lovett, Jiapeng Zhang:
Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions. - Periklis A. Papakonstantinou:
The Depth Irreducibility Hypothesis. - Anindya De:
Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums. - Debasis Mandal, Aduri Pavan, Rajeswari Venugopalan:
Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis. - Alexandros G. Dimakis, Anna Gál, Ankit Singh Rawat, Zhao Song:
Batch Codes through Dense Graphs without Short Cycles. - Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski:
Non-malleable Reductions and Applications. - Divesh Aggarwal, Stefan Dziembowski
Leakage-resilient non-malleable codes. - Ankit Gupta:
Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties. - Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah:
A game characterisation of tree-like Q-Resolution size. - Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Information Complexity for Multiparty Communication. - Adam Case, Jack H. Lutz:
Mutual Dimension. - Martin Lück, Arne Meier, Irina Schindler:
Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies. - Noga Alon, Shay Moran, Amir Yehudayoff:
Sign rank, VC dimension and spectral gaps. - Viliam Geffert, Abuzer Yakaryilmaz:
Classical Automata on Promise Problems. - Neil Thapen:
A trade-off between length and width in resolution. - Nicola Galesi, Pavel Pudlák, Neil Thapen:
The space complexity of cutting planes refutations. - Hong Van Le:
Lower bounds for the circuit size of partially homogeneous polynomials. - Hong Van Le:
Constructing elusive functions with help of evaluation mappings. - Shachar Lovett:
Linear codes cannot approximate the network capacity within any constant factor. - Subhash Khot, Dana Moshkovitz:
Candidate Lasserre Integrality Gap For Unique Games. - Ronald de Haan, Stefan Szeider:
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy. - Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. - Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. - Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan:
Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem. - Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. - Vitaly Feldman, Will Perkins, Santosh S. Vempala:
On the Complexity of Random Satisfiability Problems with Planted Solutions. - Kai-Min Chung, Xin Li, Xiaodi Wu:
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications. - Justin Thaler:
Lower Bounds for the Approximate Degree of Block-Composed Functions. - Debajyoti Bera:
Quantum One-Sided Exact Error Algorithms. - Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
Tighter Relations Between Sensitivity and Other Complexity Measures. - Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. - Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Laser Method. - Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. - Jayadev Acharya, Clément L. Canonne, Gautam Kamath:
A Chasm Between Identity and Equivalence Testing with Conditional Queries. - Rafael Oliveira, Amir Shpilka, Ben Lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. - Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf:
Deterministic Identity Testing for Sum of Read Once ABPs. - A. C. Cem Say, Abuzer Yakaryilmaz:
Magic coins are useful for small-space quantum machines. - Gil Cohen, Igor Shinkar:
Zero-Fixing Extractors for Sub-Logarithmic Entropy. - Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari:
Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs. - Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. - Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh:
Homomorphism polynomials complete for VP. - Cody Murray, Ryan Williams:
On the (Non) NP-Hardness of Computing Circuit Complexity. - Venkatesan Guruswami, Ameya Velingker:
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. - Mark Bun, Thomas Steinke:
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. - Beate Bollig:
On the Minimization of (Complete) Ordered Binary Decision Diagrams. - Ilya Volkovich:
Deterministically Factoring Sparse Polynomials into Multilinear Factors. - Stasys Jukna:
Lower Bounds for Monotone Counting Circuits. - Yael Tauman Kalai, Ran Raz:
On the Space Complexity of Linear Programming with Preprocessing. - Lance Fortnow, Rahul Santhanam:
Hierarchies Against Sublinear Advice. - Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin:
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. - Igor Carboni Oliveira, Rahul Santhanam:
Majority is incompressible by AC0[p] circuits. - Avishay Tal:
Tight bounds on The Fourier Spectrum of AC0. - Abhishek Bhowmick, Shachar Lovett:
Nonclassical polynomials as a barrier to polynomial lower bounds. - Eric Allender, Dhiraj Holden, Valentine Kabanets:
The Minimum Oracle Circuit Size Problem. - Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig:
Visibly Counter Languages and Constant Depth Circuits. - Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Heuristic time hierarchies via hierarchies for sampling distributions. - Salman Beigi, Omid Etesami, Amin Gohari:
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. - Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
Space-Efficient Approximations for Subset Sum. - Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee:
The space "just above" BQP. - Dana Moshkovitz:
Direct Product Testing With Nearly Identical Sets. - Nikhil Balaji, Andreas Krebs, Nutan Limaye:
Skew Circuits of Small Width. - Ruiwen Chen, Valentine Kabanets:
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits.
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-11-15 19:40 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: