default search action
Electronic Colloquium on Computational Complexity, 2009
Volume TR09, 2009
- Venkatesan Guruswami:
Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes. - Eli Ben-Sasson, Jakob Nordström:
Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. - Alexander Hertel, Alasdair Urquhart:
Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete. - Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan:
Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers. - Emanuele Viola:
Bit-Probe Lower Bounds for Succinct Data Structures. - David Xiao:
On basing ZK != BPP on the hardness of PAC learning. - Eli Ben-Sasson, Michael Viderman:
Tensor Products of Weakly Smooth Codes are Robust. - Stasys Jukna, Georg Schnitger:
Min-Rank Conjecture for Log-Depth Circuits. - T. C. Vijayaraghavan:
Checking Equality of Matroid Linear Representations and the Cycle Matching Problem. - Nikos Leonardos, Michael E. Saks:
Lower bounds on the randomized communication complexity of read-once functions. - Mark Braverman:
Poly-logarithmic independence fools AC0 circuits. - Noga Alon, Shai Gutner:
Balanced Hashing, Color Coding and Approximate Counting. - Atri Rudra:
Limits to List Decoding Random Codes. - Søren Riis:
On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity. - Joshua Brody, Amit Chakrabarti:
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. - Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola:
Bounded Independence Fools Halfspaces. - Joshua Brody:
The Maximum Communication Complexity of Multi-party Pointer Jumping. - Yoav Tzur:
GF(2n)-Linear Tests versus GF(2)-Linear Tests. - Manindra Agrawal, Osamu Watanabe:
One-Way Functions and the Isomorphism Conjecture. - Venkatesan Guruswami, Prasad Raghavendra:
Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers. - Konstantin Makarychev, Yury Makarychev:
How to Play Unique Games on Expanders. - Jack H. Lutz, Elvira Mayordomo:
Inseparability and Strong Hypotheses for Disjoint NP Pairs. - Akinori Kawachi, Osamu Watanabe:
Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems. - Raghav Kulkarni:
On the Power of Isolation in Planar Structures. - Arnaldo Moura, Igor Carboni Oliveira:
A New Look at Some Classical Results in Computational Complexity. - Vikraman Arvind, Pushkar S. Joglekar:
Arithmetic Circuit Size, Identity Testing, and Finite Automata. - Iftach Haitner:
A Parallel Repetition Theorem for Any Interactive Argument. - Oded Goldreich:
A Candidate Counterexample to the Easy Cylinders Conjecture. - Fabian Wagner, Thomas Thierauf:
Reachability in K3,3-free Graphs and K5-free Graphs is in Unambiguous Log-Space. - Shachar Lovett:
The density of weights of Generalized Reed-Muller codes. - Zvika Brakerski, Oded Goldreich:
From absolute distinguishability to positive distinguishability. - Neeraj Kayal, Shubhangi Saraf:
Blackbox Polynomial Identity Testing for Depth 3 Circuits. - Phokion G. Kolaitis, Swastik Kopparty:
Random Graphs and the Parity Quantifier. - Eli Ben-Sasson, Jakob Nordström:
Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs. - Nicola Galesi, Massimo Lauria:
On the Automatizability of Polynomial Calculus. - Chandan Saha, Ramprasad Saptharishi, Nitin Saxena:
The Power of Depth 2 Circuits over Algebras. - Parikshit Gopalan:
A Fourier-analytic approach to Reed-Muller decoding. - Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen:
Toward a Model for Backtracking and Dynamic Programming. - Matei David, Periklis A. Papakonstantinou, Anastasios Sidiropoulos:
Polynomial Time with Restricted Use of Randomness. - Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák:
On convex complexity measures. - Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng:
Reducibility Among Fractional Stability Problems. - Irit Dinur, Prahladh Harsha:
Composition of low-error 2-query PCPs using decodable PCPs. - Elena Grigorescu, Tali Kaufman, Madhu Sudan:
Succinct Representation of Codes with Applications to Testing. - Boaz Barak, Mark Braverman, Xi Chen, Anup Rao:
Direct Sums in Randomized Communication Complexity. - Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee:
Inaccessible Entropy. - Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners of the Hypercube and the Hypergrid. - Eli Ben-Sasson, Jakob Nordström:
A Space Hierarchy for k-DNF Resolution. - Parikshit Gopalan, Shachar Lovett, Amir Shpilka:
On the Complexity of Boolean Functions in Different Characteristics. - Derrick Stolee, Chris Bourke, N. V. Vinodchandran:
A log-space algorithm for reachability in planar DAGs with few sources. - Jan Kyncl, Tomás Vyskocil:
Logspace reduction of directed reachability for bounded genus graphs to the planar case. - Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy:
The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory. - Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf:
Planar Graph Isomorphism is in Log-space. - Johannes Köbler, Sebastian Kuhnert:
The Isomorphism Problem for k-Trees is Complete for Logspace. - Emanuele Viola:
Cell-Probe Lower Bounds for Prefix Sums. - Venkatesan T. Chakaravarthy, Sambuddha Roy:
Arthur and Merlin as Oracles. - Hunter Monroe:
Speedup for Natural Problems and coNP?=NP. - Yonatan Bilu, Nathan Linial:
Are stable instances easy? - Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. - Gábor Kun, Mario Szegedy:
A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE. - Harry Buhrman, David García-Soriano, Arie Matsliah:
Learning parities in the mistake-bound model. - Konstantinos Georgiou, Avner Magen, Madhur Tulsiani:
Optimal Sherali-Adams Gaps from Pairwise Independence. - Daniele Venturi:
Lecture Notes on Algorithmic Number Theory. - Matt DeVos, Ariel Gabizon:
Simple Affine Extractors using Dimension Expansion. - Harry Buhrman, Lance Fortnow, Rahul Santhanam:
Unconditional Lower Bounds against Advice. - Panagiotis Voulgaris, Daniele Micciancio:
Faster exponential time algorithms for the shortest vector problem. - Arnab Bhattacharyya, Ning Xie:
Lower Bounds for Testing Triangle-freeness in Boolean Functions. - Hanna Mazzawi, Nader H. Bshouty:
On Parity Check (0, 1)-Matrix over Zp. - David Buchfuhrer, Christopher Umans:
Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms. - Parikshit Gopalan:
A note on Efremenko's Locally Decodable Codes. - Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff:
Pseudorandomness for Width 2 Branching Programs. - John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran:
Kolmogorov Complexity in Randomness Extraction. - Paul Beame, Trinh Huynh:
Hardness Amplification in Proof Complexity. - Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan:
On Lower Bounds for Constant Width Arithmetic Circuits. - Suguru Tamaki, Yuichi Yoshida:
A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness. - Oded Goldreich, Brendan Juba, Madhu Sudan:
A Theory of Goal-Oriented Communication. - Christian Glaßer, Christian Reitwießner, Maximilian Witek:
Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman. - Zeev Dvir:
From Randomness Extraction to Rotating Needles. - Falk Unger:
A Probabilistic Inequality with Applications to Threshold Direct-product Theorems. - Victor Chen, Elena Grigorescu, Ronald de Wolf:
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation. - Elad Haramaty, Amir Shpilka:
On the Structure of Cubic and Quartic Polynomials. - Olaf Beyersdorff, Zenon Sadowski:
Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes. - T. C. Vijayaraghavan:
Characterization of ModL using Prime Modulus. - Dana Ron, Mira Gonen, Yuval Shavitt:
Counting Stars and Other Small Subgraphs in Sublinear Time. - Arkadev Chattopadhyay, Avi Wigderson:
Linear systems over composite moduli. - Christoph Behle, Andreas Krebs, Stephanie Reifferscheid:
An Approach to characterize the Regular Languages in TC0 with Linear Wires. - Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman:
Optimal testing of Reed-Muller codes. - Olga Tveretina, Carsten Sinz, Hans Zantema:
Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond. - Shachar Lovett, Yoav Tzur:
Explicit lower bound for fooling polynomials by the sum of small-bias generators. - Guy N. Rothblum, Salil P. Vadhan:
Are PCPs Inherent in Efficient Arguments? - Russell Impagliazzo, Valentine Kabanets, Avi Wigderson:
New Direct-Product Testers and 2-Query PCPs. - Thanh Minh Hoang:
On the Matching Problem for Special Graph Classes. - Olaf Beyersdorff, Johannes Köbler, Sebastian Müller:
Proof Systems that Take Advice. - Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda:
Colored Hypergraph Isomorphism is Fixed Parameter Tractable. - Bireswar Das, Jacobo Torán, Fabian Wagner:
Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. - Swapnoneel Roy:
STRIP EXCHANGING IS HARD. - Haralampos Tsaknakis, Paul G. Spirakis:
A Graph Spectral Approach for Computing Approximate Nash Equilibria. - Rakesh Mohanty, N. S. Narayanaswamy:
Online Algorithms for Self-Organizing Sequential Search - A Survey. - Alexander A. Sherstov:
The intersection of two halfspaces has high threshold degree. - Venkatesan Guruswami, Ali Kemal Sinop:
Improved Inapproximability Results for Maximum k-Colorable Subgraph. - Jakob Nordström, Alexander A. Razborov:
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. - Nitin Saxena:
Progress on Polynomial Identity Testing. - Andrew Drucker, Ronald de Wolf:
Quantum Proofs for Classical Theorems. - Vikraman Arvind, Srikanth Srinivasan:
On the Hardness of the Noncommutative Determinant. - Scott Aaronson:
BQP and the Polynomial Hierarchy. - Vikraman Arvind, Srikanth Srinivasan:
The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets. - Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma:
Using Elimination Theory to construct Rigid Matrices. - Kevin Dick, Christopher Umans:
Improved inapproximability factors for some Sigma2p minimization problems. - Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky:
Equivalence of Uniform Key Agreement and Composition Insecurity. - Kai-Min Chung, Feng-Hao Liu:
Tight Parallel Repetition Theorems for Public-coin Arguments. - Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. - Walid Gomaa:
Model-Theoretic Characterization of Complexity Classes. - Davide Bilò, Luciano Gualà, Guido Proietti:
Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game. - Anindya De, Luca Trevisan, Madhur Tulsiani:
Non-uniform attacks against one-way functions and PRGs. - Emanuele Viola:
Are all distributions easy? - Swastik Kopparty, Shubhangi Saraf:
Local list-decoding and testing of random linear codes from high-error. - Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich:
Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. - Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson:
Bounded Independence Fools Degree-2 Threshold Functions. - Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin:
Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness. - Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing well-parenthesized expressions in the streaming model. - Charanjit S. Jutla:
Almost Optimal Bounds for Direct Product Threshold Theorem. - Zohar Shay Karnin, Yuval Rabani, Amir Shpilka:
Explicit Dimension Reduction and Its Applications. - Vikraman Arvind, Srikanth Srinivasan:
Circuit Lower Bounds, Help Functions, and the Remote Point Problem. - Hemanta K. Maji, Manoj Prabhakaran, Mike Rosulek:
Cryptographic Complexity Classes and Computational Intractability Assumptions. - Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi:
On the Optimality of a Class of LP-based Algorithms. - David Steurer, Nisheeth K. Vishnoi:
Connections Between Unique Games and Multicut. - Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman:
Locally Testable Codes Require Redundant Testers. - Brett Hemenway, Rafail Ostrovsky:
Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems. - Gillat Kol, Ran Raz:
Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist. - Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer:
Subsampling Semidefinite Programs and Max-Cut on the Sphere. - Ryan O'Donnell, Yi Wu, Yuan Zhou:
Optimal lower bounds for locality sensitive hashing (except when q is tiny). - Stephan Kreutzer, Anuj Dawar:
Parameterized Complexity of First-Order Logic. - Lior Malka:
How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-Knowledge. - Anindya De, Thomas Vidick:
Near-optimal extractors against quantum storage. - Zeev Dvir:
On matrix rigidity and locally self-correctable codes. - Zeev Dvir, Avi Wigderson:
Monotone expanders - constructions and applications. - Michael A. Burr, Felix Krahmer, Chee Yap:
Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique. - Massimo Lauria:
Random CNFs require spacious Polynomial Calculus refutations. - Gillat Kol, Ran Raz:
Bounds on 2-Query Locally Testable Codes with Affine Tests. - Mohammad Mahmoody, David Xiao:
On the Power of Randomized Reductions and the Checkability of SAT. - Saugata Basu:
A complex analogue of Toda's Theorem. - Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani:
Improved Pseudorandom Generators for Depth 2 Circuits. - Aaron Potechin:
Bounds on Monotone Switching Networks for Directed Connectivity. - Noam Livne:
On the Construction of One-Way Functions from Average Case Hardness. - Prahladh Harsha, Adam R. Klivans, Raghu Meka:
An Invariance Principle for Polytopes. - Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Network Formation. - Dan Gutfreund, Akinori Kawachi:
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. - Stephan Kreutzer:
Algorithmic Meta-Theorems.
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-22 19:33 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: