default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic 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, Tomasz Kazana, Maciej Obremski:
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.