All reports in year 2009:

__
TR09-001
| 26th November 2008
__

Venkatesan Guruswami#### Artin automorphisms, Cyclotomic function fields, and Folded list-decodable codes

__
TR09-002
| 23rd November 2008
__

Eli Ben-Sasson, Jakob Nordström#### Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution

__
TR09-003
| 6th January 2009
__

Alex Hertel, Alasdair Urquhart#### Comments on ECCC Report TR06-133: The Resolution Width Problem is EXPTIME-Complete

__
TR09-004
| 15th January 2009
__

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan#### Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

__
TR09-005
| 7th December 2008
__

Emanuele Viola#### Bit-Probe Lower Bounds for Succinct Data Structures

__
TR09-006
| 19th January 2009
__

David Xiao#### On basing ZK != BPP on the hardness of PAC learning

__
TR09-007
| 9th January 2009
__

Eli Ben-Sasson, Michael Viderman#### Tensor Products of Weakly Smooth Codes are Robust

__
TR09-008
| 15th January 2009
__

Stasys Jukna, Georg Schnitger#### Min-Rank Conjecture for Log-Depth Circuits

__
TR09-009
| 18th December 2008
__

T.C. Vijayaraghavan#### Checking Equality of Matroid Linear Representations and the Cycle Matching Problem

Revisions: 2

__
TR09-010
| 29th January 2009
__

Nikos Leonardos, Michael Saks#### Lower bounds on the randomized communication complexity of read-once functions

__
TR09-011
| 31st January 2009
__

Mark Braverman#### Poly-logarithmic independence fools AC0 circuits

__
TR09-012
| 4th February 2009
__

Noga Alon, Shai Gutner#### Balanced Hashing, Color Coding and Approximate Counting

__
TR09-013
| 4th February 2009
__

Atri Rudra#### Limits to List Decoding Random Codes

__
TR09-014
| 7th February 2009
__

Soren Riis#### On the asymptotic Nullstellensatz and Polynomial Calculus proof complexity

__
TR09-015
| 19th February 2009
__

Joshua Brody, Amit Chakrabarti#### A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

__
TR09-016
| 21st February 2009
__

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola#### Bounded Independence Fools Halfspaces

__
TR09-017
| 20th February 2009
__

Joshua Brody#### The Maximum Communication Complexity of Multi-party Pointer Jumping.

__
TR09-018
| 8th March 2009
__

Yoav Tzur#### $GF(2^n)$-Linear Tests versus $GF(2)$-Linear Tests

Comments: 1

__
TR09-019
| 10th March 2009
__

Agrawal Manindra, Osamu Watanabe#### One-Way Functions and the Isomorphism Conjecture

__
TR09-020
| 2nd March 2009
__

Venkatesan Guruswami, Prasad Raghavendra#### Hardness of Solving Sparse Overdetermined Linear Systems: A 3-Query PCP over Integers.

__
TR09-021
| 2nd March 2009
__

Konstantin Makarychev, Yury Makarychev#### How to Play Unique Games on Expanders

__
TR09-022
| 16th February 2009
__

Jack H. Lutz, Elvira Mayordomo#### Inseparability and Strong Hypotheses for Disjoint NP Pairs

Revisions: 1

__
TR09-023
| 12th March 2009
__

Akinori Kawachi, Osamu Watanabe#### Strong Hardness Preserving Reduction from a P-Samplable Distribution to the Uniform Distribution for NP-Search Problems

__
TR09-024
| 26th February 2009
__

Raghav Kulkarni#### On the Power of Isolation in Planar Structures

__
TR09-025
| 11th March 2009
__

Arnaldo Moura, Igor Carboni Oliveira#### A New Look at Some Classical Results in Computational Complexity

__
TR09-026
| 17th February 2009
__

Vikraman Arvind, Pushkar Joglekar#### Arithmetic Circuit Size, Identity Testing, and Finite Automata

__
TR09-027
| 2nd April 2009
__

Iftach Haitner#### A Parallel Repetition Theorem for Any Interactive Argument

Revisions: 1

__
TR09-028
| 2nd April 2009
__

Oded Goldreich#### A Candidate Counterexample to the Easy Cylinders Conjecture

__
TR09-029
| 3rd April 2009
__

Fabian Wagner, Thomas Thierauf#### Reachability in K_{3,3}-free Graphs and K_5-free Graphs is in Unambiguous Log-Space

Revisions: 1

__
TR09-030
| 5th April 2009
__

Shachar Lovett#### The density of weights of Generalized Reed-Muller codes

__
TR09-031
| 6th April 2009
__

Zvika Brakerski, Oded Goldreich#### From absolute distinguishability to positive distinguishability

__
TR09-032
| 16th April 2009
__

Neeraj Kayal, Shubhangi Saraf#### Blackbox Polynomial Identity Testing for Depth 3 Circuits

__
TR09-033
| 16th April 2009
__

Phokion G. Kolaitis, Swastik Kopparty#### Random Graphs and the Parity Quantifier

__
TR09-034
| 25th March 2009
__

Eli Ben-Sasson, Jakob Nordström#### Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs

Comments: 1

__
TR09-035
| 26th March 2009
__

Nicola Galesi, Massimo Lauria#### On the Automatizability of Polynomial Calculus

__
TR09-036
| 14th April 2009
__

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena#### The Power of Depth 2 Circuits over Algebras

__
TR09-037
| 10th April 2009
__

Parikshit Gopalan#### A Fourier-analytic approach to Reed-Muller decoding

__
TR09-038
| 14th April 2009
__

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen#### Toward a Model for Backtracking and Dynamic Programming

__
TR09-039
| 6th April 2009
__

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos#### Polynomial Time with Restricted Use of Randomness

__
TR09-040
| 20th April 2009
__

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak#### On convex complexity measures

__
TR09-041
| 9th April 2009
__

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng#### Reducibility Among Fractional Stability Problems

__
TR09-042
| 5th May 2009
__

Irit Dinur, Prahladh Harsha#### Composition of low-error 2-query PCPs using decodable PCPs

__
TR09-043
| 18th May 2009
__

Elena Grigorescu, Tali Kaufman, Madhu Sudan#### Succinct Representation of Codes with Applications to Testing

__
TR09-044
| 6th May 2009
__

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao#### Direct Sums in Randomized Communication Complexity

__
TR09-045
| 20th May 2009
__

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee#### Inaccessible Entropy

__
TR09-046
| 9th May 2009
__

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff#### Transitive-Closure Spanners of the Hypercube and the Hypergrid

__
TR09-047
| 20th April 2009
__

Eli Ben-Sasson, Jakob Nordström#### A Space Hierarchy for k-DNF Resolution

Comments: 1

__
TR09-048
| 29th May 2009
__

Parikshit Gopalan, Shachar Lovett, Amir Shpilka#### On the Complexity of Boolean Functions in Different Characteristics

__
TR09-049
| 5th May 2009
__

Derrick Stolee, Chris Bourke, N. V. Vinodchandran#### A log-space algorithm for reachability in planar DAGs with few sources

__
TR09-050
| 28th May 2009
__

Jan Kyncl, Tomas Vyskocil#### Logspace reduction of directed reachability for bounded genus graphs to the planar case

__
TR09-051
| 2nd July 2009
__

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy#### The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Complexity Theory

__
TR09-052
| 2nd May 2009
__

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf#### Planar Graph Isomorphism is in Log-space

__
TR09-053
| 20th May 2009
__

Johannes Köbler, Sebastian Kuhnert#### The Isomorphism Problem for k-Trees is Complete for Logspace

Revisions: 1

__
TR09-054
| 7th June 2009
__

Emanuele Viola, Emanuele Viola#### Cell-Probe Lower Bounds for Prefix Sums

__
TR09-055
| 10th June 2009
__

Venkatesan Chakaravarthy, Sambuddha Roy#### Arthur and Merlin as Oracles

__
TR09-056
| 20th June 2009
__

Hunter Monroe#### Speedup for Natural Problems and coNP?=NP

Revisions: 2

__
TR09-057
| 23rd June 2009
__

Yonatan Bilu, Nathan Linial#### Are stable instances easy?

__
TR09-058
| 4th July 2009
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Time Algorithms for Matrix Completion Problems

__
TR09-059
| 2nd July 2009
__

Gábor Kun, Mario Szegedy#### A NEW LINE OF ATTACK ON THE DICHOTOMY CONJECTURE

__
TR09-060
| 4th June 2009
__

Harry Buhrman, David García Soriano, Arie Matsliah#### Learning parities in the mistake-bound model.

__
TR09-061
| 2nd July 2009
__

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani#### Optimal Sherali-Adams Gaps from Pairwise Independence

__
TR09-062
| 28th July 2009
__

Daniele Venturi#### Lecture Notes on Algorithmic Number Theory

__
TR09-063
| 29th July 2009
__

Matt DeVos, Ariel Gabizon#### Simple Affine Extractors using Dimension Expansion

Revisions: 2

__
TR09-064
| 3rd August 2009
__

Harry Buhrman, Lance Fortnow, Rahul Santhanam#### Unconditional Lower Bounds against Advice

__
TR09-065
| 31st July 2009
__

Panagiotis Voulgaris, Daniele Micciancio#### Faster exponential time algorithms for the shortest vector problem

__
TR09-066
| 13th August 2009
__

Arnab Bhattacharyya, Ning Xie#### Lower Bounds for Testing Triangle-freeness in Boolean Functions

__
TR09-067
| 18th August 2009
__

Hanna Mazzawi, Nader Bshouty#### On Parity Check $(0,1)$-Matrix over $Z_p$

Revisions: 1

__
TR09-068
| 1st September 2009
__

Dave Buchfuhrer, Chris Umans#### Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms

__
TR09-069
| 2nd September 2009
__

Parikshit Gopalan#### A note on Efremenko's Locally Decodable Codes

Revisions: 1

__
TR09-070
| 1st September 2009
__

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff#### Pseudorandomness for Width 2 Branching Programs

__
TR09-071
| 1st September 2009
__

John Hitchcock, A. Pavan, N. V. Vinodchandran#### Kolmogorov Complexity in Randomness Extraction

__
TR09-072
| 3rd September 2009
__

Paul Beame, Trinh Huynh#### Hardness Amplification in Proof Complexity

Revisions: 2
,
Comments: 2

__
TR09-073
| 6th September 2009
__

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan#### On Lower Bounds for Constant Width Arithmetic Circuits

__
TR09-074
| 10th September 2009
__

Suguru Tamaki, Yuichi Yoshida#### A Query Efficient Non-Adaptive Long Code Test with Perfect Completeness

__
TR09-075
| 17th September 2009
__

Oded Goldreich, Brendan Juba, Madhu Sudan#### A Theory of Goal-Oriented Communication

Revisions: 1
,
Comments: 1

__
TR09-076
| 19th August 2009
__

Christian Glaßer, Christian Reitwießner, Maximilian Witek#### Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman

Revisions: 1

__
TR09-077
| 16th September 2009
__

Zeev Dvir#### From Randomness Extraction to Rotating Needles

__
TR09-078
| 16th September 2009
__

Falk Unger#### A Probabilistic Inequality with Applications to Threshold Direct-product Theorems

__
TR09-079
| 21st September 2009
__

Victor Chen, Elena Grigorescu, Ronald de Wolf#### Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

__
TR09-080
| 19th September 2009
__

Elad Haramaty, Amir Shpilka#### On the Structure of Cubic and Quartic Polynomials

Revisions: 1

__
TR09-081
| 27th August 2009
__

Olaf Beyersdorff, Zenon Sadowski#### Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

__
TR09-082
| 20th September 2009
__

T.C. Vijayaraghavan#### Characterization of ModL using Prime Modulus.

Revisions: 1

__
TR09-083
| 24th September 2009
__

Dana Ron, Mira Gonen, Yuval Shavitt#### Counting Stars and Other Small Subgraphs in Sublinear Time

__
TR09-084
| 24th September 2009
__

Arkadev Chattopadhyay, Avi Wigderson#### Linear systems over composite moduli

__
TR09-085
| 14th September 2009
__

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid#### An Approach to characterize the Regular Languages in TC0 with Linear Wires

Revisions: 1

__
TR09-086
| 2nd October 2009
__

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman#### Optimal testing of Reed-Muller codes

Revisions: 1

__
TR09-087
| 1st October 2009
__

Olga Tveretina, Carsten Sinz, Hans Zantema#### Ordered Binary Decision Diagrams, Pigeonhole Formulas and Beyond

__
TR09-088
| 29th September 2009
__

Shachar Lovett, Yoav Tzur#### Explicit lower bound for fooling polynomials by the sum of small-bias generators

__
TR09-089
| 26th September 2009
__

Guy Rothblum, Salil Vadhan#### Are PCPs Inherent in Efficient Arguments?

__
TR09-090
| 6th October 2009
__

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson#### New Direct-Product Testers and 2-Query PCPs

__
TR09-091
| 23rd September 2009
__

Thanh Minh Hoang#### On the Matching Problem for Special Graph Classes

Revisions: 1

__
TR09-092
| 8th October 2009
__

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller#### Proof Systems that Take Advice

__
TR09-093
| 8th October 2009
__

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda#### Colored Hypergraph Isomorphism is Fixed Parameter Tractable

Revisions: 1

__
TR09-094
| 7th October 2009
__

Bireswar Das, Jacobo Toran, Fabian Wagner#### Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs

__
TR09-095
| 25th September 2009
__

Swapnoneel Roy#### STRIP EXCHANGING IS HARD

Revisions: 1

__
TR09-096
| 7th October 2009
__

Haralampos Tsaknakis, Paul Spirakis#### A Graph Spectral Approach for Computing Approximate Nash Equilibria

__
TR09-097
| 2nd September 2009
__

Rakesh Mohanty, N. S. Narayanaswamy#### Online Algorithms for Self-Organizing Sequential Search - A Survey

__
TR09-098
| 9th October 2009
__

Alexander A. Sherstov#### The intersection of two halfspaces has high threshold degree

Revisions: 1

__
TR09-099
| 16th October 2009
__

Venkatesan Guruswami, Ali Kemal Sinop#### Improved Inapproximability Results for Maximum k-Colorable Subgraph

Revisions: 1

__
TR09-100
| 16th October 2009
__

Jakob Nordström, Alexander Razborov#### On Minimal Unsatisfiability and Time-Space Trade-offs for $k$-DNF Resolution

__
TR09-101
| 20th October 2009
__

Nitin Saxena#### Progress on Polynomial Identity Testing

__
TR09-102
| 21st October 2009
__

Andrew Drucker, Ronald de Wolf#### Quantum Proofs for Classical Theorems

__
TR09-103
| 26th October 2009
__

Vikraman Arvind, Srikanth Srinivasan#### On the Hardness of the Noncommutative Determinant

__
TR09-104
| 26th October 2009
__

Scott Aaronson#### BQP and the Polynomial Hierarchy

__
TR09-105
| 27th October 2009
__

Vikraman Arvind, Srikanth Srinivasan#### The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

__
TR09-106
| 28th October 2009
__

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma#### Using Elimination Theory to construct Rigid Matrices

__
TR09-107
| 28th October 2009
__

Kevin Dick, Chris Umans#### Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

__
TR09-108
| 31st October 2009
__

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky#### Equivalence of Uniform Key Agreement and Composition Insecurity

Revisions: 1

__
TR09-109
| 3rd November 2009
__

Kai-Min Chung, Feng-Hao Liu#### Tight Parallel Repetition Theorems for Public-coin Arguments

__
TR09-110
| 5th November 2009
__

Scott Aaronson, Andris Ambainis#### The Need for Structure in Quantum Speedups

Revisions: 1

__
TR09-111
| 5th November 2009
__

Walid Gomaa#### Model-Theoretic Characterization of Complexity Classes

__
TR09-112
| 3rd November 2009
__

Davide Bilò, Luciano Gualà, Guido Proietti#### Hardness of an Asymmetric 2-player Stackelberg Network Pricing Game

__
TR09-113
| 9th November 2009
__

Anindya De, Luca Trevisan, Madhur Tulsiani#### Non-uniform attacks against one-way functions and PRGs

__
TR09-114
| 13th November 2009
__

Emanuele Viola#### Are all distributions easy?

__
TR09-115
| 13th November 2009
__

Swastik Kopparty, Shubhangi Saraf#### Local list-decoding and testing of random linear codes from high-error

__
TR09-116
| 15th November 2009
__

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich#### Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in

__
TR09-117
| 18th November 2009
__

Ilias Diakonikolas, Daniel Kane, Jelani Nelson#### Bounded Independence Fools Degree-2 Threshold Functions

Revisions: 1

__
TR09-118
| 18th November 2009
__

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin#### Title: Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness

Revisions: 1

__
TR09-119
| 17th November 2009
__

Frederic Magniez, Claire Mathieu, Ashwin Nayak#### Recognizing well-parenthesized expressions in the streaming model

__
TR09-120
| 18th November 2009
__

Charanjit Jutla#### Almost Optimal Bounds for Direct Product Threshold Theorem

Revisions: 2

__
TR09-121
| 22nd November 2009
__

Zohar Karnin, Yuval Rabani, Amir Shpilka#### Explicit Dimension Reduction and Its Applications

__
TR09-122
| 23rd November 2009
__

Vikraman Arvind, Srikanth Srinivasan#### Circuit Lower Bounds, Help Functions, and the Remote Point Problem

__
TR09-123
| 23rd November 2009
__

Hemanta Maji, Manoj Prabhakaran, Mike Rosulek#### Cryptographic Complexity Classes and Computational Intractability Assumptions

__
TR09-124
| 24th November 2009
__

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi#### On the Optimality of a Class of LP-based Algorithms

Revisions: 1

__
TR09-125
| 24th November 2009
__

David Steurer, Nisheeth Vishnoi#### Connections Between Unique Games and Multicut

__
TR09-126
| 26th November 2009
__

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman#### Locally Testable Codes Require Redundant Testers

Revisions: 3

__
TR09-127
| 25th November 2009
__

Brett Hemenway, Rafail Ostrovsky#### Lossy Trapdoor Functions from Smooth Homomorphic Hash Proof Systems

Revisions: 2

__
TR09-128
| 29th November 2009
__

Gillat Kol, Ran Raz#### Locally Testable Codes Analogues to the Unique Games Conjecture Do Not Exist

__
TR09-129
| 30th November 2009
__

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer#### Subsampling Semidefinite Programs and Max-Cut on the Sphere

Revisions: 1

__
TR09-130
| 1st December 2009
__

Ryan O'Donnell, YI WU, Yuan Zhou#### Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

__
TR09-131
| 2nd December 2009
__

Stephan Kreutzer, Anuj Dawar#### Parameterized Complexity of First-Order Logic

Revisions: 2

__
TR09-132
| 8th December 2009
__

Lior Malka#### How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-Knowledge

__
TR09-133
| 9th December 2009
__

Anindya De, Thomas Vidick#### Near-optimal extractors against quantum storage

__
TR09-134
| 10th December 2009
__

Zeev Dvir#### On matrix rigidity and locally self-correctable codes

Revisions: 1

__
TR09-135
| 10th December 2009
__

Zeev Dvir, Avi Wigderson#### Monotone expanders - constructions and applications

__
TR09-136
| 9th December 2009
__

Michael Burr, Felix Krahmer, Chee Yap#### Continuous Amortization: A Non-Probabilistic Adaptive Analysis Technique

__
TR09-137
| 14th December 2009
__

Massimo Lauria#### Random CNFs require spacious Polynomial Calculus refutations

Comments: 1

__
TR09-138
| 14th December 2009
__

Gillat Kol, Ran Raz#### Bounds on 2-Query Locally Testable Codes with Affine Tests

__
TR09-139
| 17th December 2009
__

Mohammad Mahmoody, David Xiao#### On the Power of Randomized Reductions and the Checkability of SAT

Revisions: 3

__
TR09-140
| 18th December 2009
__

Saugata Basu#### A complex analogue of Toda's Theorem

Revisions: 1

__
TR09-141
| 19th December 2009
__

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani#### Improved Pseudorandom Generators for Depth 2 Circuits

__
TR09-142
| 17th December 2009
__

Aaron Potechin#### Bounds on Monotone Switching Networks for Directed Connectivity

Revisions: 1

__
TR09-143
| 22nd December 2009
__

Noam Livne#### On the Construction of One-Way Functions from Average Case Hardness

__
TR09-144
| 24th December 2009
__

Prahladh Harsha, Adam Klivans, Raghu Meka#### An Invariance Principle for Polytopes

__
TR09-145
| 20th December 2009
__

Shankar Kalyanaraman, Chris Umans#### The Complexity of Rationalizing Network Formation

__
TR09-146
| 29th December 2009
__

Dan Gutfreund, Akinori Kawachi#### Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

__
TR09-147
| 30th December 2009
__

Stephan Kreutzer#### Algorithmic Meta-Theorems

Venkatesan Guruswami

Algebraic codes that achieve list decoding capacity were recently

constructed by a careful ``folding'' of the Reed-Solomon code. The

``low-degree'' nature of this folding operation was crucial to the list

decoding algorithm. We show how such folding schemes conducive to list

decoding arise out of the Artin-Frobenius automorphism at primes ...
more >>>

Eli Ben-Sasson, Jakob Nordström

A number of works have looked at the relationship between length and space of resolution proofs. A notorious question has been whether the existence of a short proof implies the existence of a proof that can be verified using limited space.

In this paper we resolve the question by answering ... more >>>

Alex Hertel, Alasdair Urquhart

We discovered a serious error in one of our previous submissions to ECCC and wish to make sure that this mistake is publicly known.

The main argument of the report TR06-133 is in error. The paper claims to prove the result of the title by reduction from the (Exists,k)-pebble game, ... more >>>

Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.

\begin{enumerate}

\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ...
more >>>

Emanuele Viola

We prove lower bounds on the redundancy necessary to

represent a set $S$ of objects using a number of bits

close to the information-theoretic minimum $\log_2 |S|$,

while answering various queries by probing few bits. Our

main results are:

\begin{itemize}

\item To represent $n$ ternary values $t \in

\zot^n$ in ...
more >>>

David Xiao

Learning is a central task in computer science, and there are various

formalisms for capturing the notion. One important model studied in

computational learning theory is the PAC model of Valiant (CACM 1984).

On the other hand, in cryptography the notion of ``learning nothing''

is often modelled by the simulation ...
more >>>

Eli Ben-Sasson, Michael Viderman

We continue the study of {\em robust} tensor codes and expand the

class of base codes that can be used as a starting point for the

construction of locally testable codes via robust two-wise tensor

products. In particular, we show that all unique-neighbor expander

codes and all locally correctable codes, ...
more >>>

Stasys Jukna, Georg Schnitger

A completion of an m-by-n matrix A with entries in {0,1,*} is obtained

by setting all *-entries to constants 0 or 1. A system of semi-linear

equations over GF(2) has the form Mx=f(x), where M is a completion of

A and f:{0,1}^n --> {0,1}^m is an operator, the i-th coordinate ...
more >>>

T.C. Vijayaraghavan

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given ... more >>>

Nikos Leonardos, Michael Saks

We prove lower bounds on the randomized two-party communication complexity of functions that arise from read-once boolean formulae.

A read-once boolean formula is a formula in propositional logic with the property that every variable appears exactly once. Such a formula can be represented by a tree, where the leaves correspond ... more >>>

Mark Braverman

We prove that poly-sized AC0 circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^2 n)-independent distributions fool poly-size DNF formulas. Razborov [Raz08] has ... more >>>

Noga Alon, Shai Gutner

Color Coding is an algorithmic technique for deciding efficiently

if a given input graph contains a path of a given length (or

another small subgraph of constant tree-width). Applications of the

method in computational biology motivate the study of similar

algorithms for counting the number of copies of a ...
more >>>

Atri Rudra

It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... more >>>

Soren Riis

We show that the asymptotic complexity of uniformly generated (expressible in First-Order (FO) logic) propositional tautologies for the Nullstellensatz proof system (NS) as well as for Polynomial Calculus, (PC) has four distinct types of asymptotic behavior over fields of finite characteristic. More precisely, based on some highly non-trivial work by ... more >>>

Joshua Brody, Amit Chakrabarti

The Gap-Hamming-Distance problem arose in the context of proving space

lower bounds for a number of key problems in the data stream model. In

this problem, Alice and Bob have to decide whether the Hamming distance

between their $n$-bit input strings is large (i.e., at least $n/2 +

\sqrt n$) ...
more >>>

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps)/\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise ... more >>>

Joshua Brody

We study the one-way number-on-the-forhead (NOF) communication

complexity of the k-layer pointer jumping problem. Strong lower

bounds for this problem would have important implications in circuit

complexity. All of our results apply to myopic protocols (where

players see only one layer ahead, but can still ...
more >>>

Yoav Tzur

A small-biased distribution of bit sequences is defined as one withstanding $GF(2)$-linear tests for randomness, which are linear combinations of the bits themselves. We consider linear combinations over larger fields, specifically, $GF(2^n)$ for $n$ that divides the length of the bit sequence. Indeed, this means that we partition the bits ... more >>>

Agrawal Manindra, Osamu Watanabe

We study the Isomorphism Conjecture proposed by Berman and Hartmanis.

It states that all sets complete for NP under polynomial-time many-one

reductions are P-isomorphic to each other. From previous research

it has been widely believed that all NP-complete sets are reducible

each other by one-to-one and length-increasing polynomial-time

reductions, but ...
more >>>

Venkatesan Guruswami, Prasad Raghavendra

A classic result due to Hastad established that for every constant \eps > 0, given an overdetermined system of linear equations over a finite field \F_q where each equation depends on exactly 3 variables and at least a fraction (1-\eps) of the equations can be satisfied, it is NP-hard to ... more >>>

Konstantin Makarychev, Yury Makarychev

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders.

Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>

Jack H. Lutz, Elvira Mayordomo

This paper investigates the existence of inseparable disjoint

pairs of NP languages and related strong hypotheses in

computational complexity. Our main theorem says that, if NP does

not have measure 0 in EXP, then there exist disjoint pairs of NP

languages that are P-inseparable, in fact TIME(2^(n^k)-inseparable.

We also relate ...
more >>>

Akinori Kawachi, Osamu Watanabe

Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; ... more >>>

Raghav Kulkarni

The purpose of this paper is to study the deterministic

{\em isolation} for certain structures in directed and undirected

planar graphs.

The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and

\cite{dkr08} isolate a perfect matching in ...
more >>>

Arnaldo Moura, Igor Carboni Oliveira

We propose a generalization of the traditional algorithmic space and

time complexities. Using the concept introduced, we derive an

unified proof for the deterministic time and space hierarchy

theorems, now stated in a much more general setting. This opens the

possibility for the unification and generalization of other results

that ...
more >>>

Vikraman Arvind, Pushkar Joglekar

Let $\F\{x_1,x_2,\cdots,x_n\}$ be the noncommutative polynomial

ring over a field $\F$, where the $x_i$'s are free noncommuting

formal variables. Given a finite automaton $\A$ with the $x_i$'s as

alphabet, we can define polynomials $\f( mod A)$ and $\f(div A)$

obtained by natural operations that we ...
more >>>

Iftach Haitner

The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, ... more >>>

Oded Goldreich

We present a candidate counterexample to the

easy cylinders conjecture, which was recently suggested

by Manindra Agrawal and Osamu Watanabe (ECCC, TR09-019).

Loosely speaking, the conjecture asserts that any 1-1 function

in $P/poly$ can be decomposed into ``cylinders'' of sub-exponential

size that can each be inverted by some polynomial-size circuit.

more >>>

Fabian Wagner, Thomas Thierauf

We show that the reachability problem for directed graphs

that are either K_{3,3}-free or K_5-free

is in unambiguous log-space, UL \cap coUL.

This significantly extends the result of Bourke, Tewari, and Vinodchandran

that the reachability problem for directed planar graphs

is in UL \cap coUL.

Our algorithm decomposes ... more >>>

Shachar Lovett

We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We ... more >>>

Zvika Brakerski, Oded Goldreich

We study methods of converting algorithms that distinguish pairs

of distributions with a gap that has an absolute value that is noticeable

into corresponding algorithms in which the gap is always positive.

Our focus is on designing algorithms that, in addition to the tested string,

obtain a ...
more >>>

Neeraj Kayal, Shubhangi Saraf

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>

Phokion G. Kolaitis, Swastik Kopparty

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

Eli Ben-Sasson, Jakob Nordström

For current state-of-the-art satisfiability algorithms based on the

DPLL procedure and clause learning, the two main bottlenecks are the

amounts of time and memory used. Understanding time and memory

consumption, and how they are related to one another, is therefore a

question of considerable practical importance. In the field of ...
more >>>

Nicola Galesi, Massimo Lauria

We prove that Polynomial Calculus and Polynomial Calculus with Resolution are not automatizable, unless W[P]-hard problems are fixed parameter tractable by one-side error randomized algorithms. This extends to Polynomial Calculus the analogous result obtained for Resolution by Alekhnovich and Razborov (SIAM J. Computing, 38(4), 2008).

more >>>Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

We study the problem of polynomial identity testing (PIT) for depth

2 arithmetic circuits over matrix algebra. We show that identity

testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field

F is polynomial time equivalent to identity testing of depth 2

(Pi-Sigma) arithmetic circuits over U_2(F), the ...
more >>>

Parikshit Gopalan

We present a Fourier-analytic approach to list-decoding Reed-Muller codes over arbitrary finite fields. We prove that the list-decoding radius for quadratic polynomials equals $1 - 2/q$ over any field $F_q$ where $q > 2$. This confirms a conjecture due to Gopalan, Klivans and Zuckerman for degree $2$. Previously, tight bounds ... more >>>

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

We propose a model called priority branching trees (pBT ) for backtracking and dynamic

programming algorithms. Our model generalizes both the priority model of Borodin, Nielson

and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence

spans a wide spectrum of algorithms. After witnessing the ...
more >>>

Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>

Pavel Hrubes, Stasys Jukna, Alexander Kulikov, Pavel Pudlak

Khrapchenko's classical lower bound $n^2$ on the formula size of the

parity function~$f$ can be interpreted as designing a suitable

measure of subrectangles of the combinatorial rectangle

$f^{-1}(0)\times f^{-1}(1)$. Trying to generalize this approach we

arrived at the concept of \emph{convex measures}. We prove the

more >>>

Shiva Kintali, Laura J Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng

"As has often been the case with NP-completeness proofs, PPAD-completeness proofs will be eventually refined to cover simpler and more realistic looking classes of games. And then researchers will strive to identify even simpler classes." --Papadimitriou (chapter 2 of Algorithmic Game Theory book)

In a landmark paper, Papadimitriou introduced a ... more >>>

Irit Dinur, Prahladh Harsha

The main result of this paper is a simple, yet generic, composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i.e., very much tailored ... more >>>

Elena Grigorescu, Tali Kaufman, Madhu Sudan

Motivated by questions in property testing, we search for linear

error-correcting codes that have the ``single local orbit'' property:

i.e., they are specified by a single local

constraint and its translations under the symmetry group of the

code. We show that the dual of every ``sparse'' binary code

whose coordinates

more >>>

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>

Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee

We put forth a new computational notion of entropy, which measures the

(in)feasibility of sampling high entropy strings that are consistent

with a given protocol. Specifically, we say that the i'th round of a

protocol (A, B) has _accessible entropy_ at most k, if no

polynomial-time strategy A^* can generate ...
more >>>

Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>

Eli Ben-Sasson, Jakob Nordström

The k-DNF resolution proof systems are a family of systems indexed by

the integer k, where the kth member is restricted to operating with

formulas in disjunctive normal form with all terms of bounded arity k

(k-DNF formulas). This family was introduced in [Krajicek 2001] as an

extension of the ...
more >>>

Parikshit Gopalan, Shachar Lovett, Amir Shpilka

Every Boolean function on $n$ variables can be expressed as a unique multivariate polynomial modulo $p$ for every prime $p$. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree ... more >>>

Derrick Stolee, Chris Bourke, N. V. Vinodchandran

Designing algorithms that use logarithmic space for graph reachability problems is fundamental to complexity theory. It is well known that for general directed graphs this problem is equivalent to the NL vs L problem. For planar graphs, the question is not settled. Showing that the planar reachability problem is NL-complete ... more >>>

Jan Kyncl, Tomas Vyskocil

Directed reachability (or briefly reachability) is the following decision problem: given a directed graph G and two of its vertices s,t, determine whether there is a directed path from s to t in G. Directed reachability is a standard complete problem for the complexity class NL. Planar reachability is an ... more >>>

Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity.

The Kolmogorov measures that have been ...
more >>>

Fabian Wagner, Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and ... more >>>

Johannes Köbler, Sebastian Kuhnert

We show that k-tree isomorphism can be decided in logarithmic

space by giving a logspace canonical labeling algorithm. This improves

over the previous StUL upper bound and matches the lower bound. As a

consequence, the isomorphism, the automorphism, as well as the

canonization problem for k-trees ...
more >>>

Emanuele Viola, Emanuele Viola

We prove that to store n bits x so that each

prefix-sum query Sum(i) := sum_{k < i} x_k can be answered

by non-adaptively probing q cells of log n bits, one needs

memory > n + n/log^{O(q)} n.

Our bound matches a recent upper bound of n +

n/log^{Omega(q)} ...
more >>>

Venkatesan Chakaravarthy, Sambuddha Roy

We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) the Arthur-Merlin class.

Our main results are the following: (i) $BPP^{NP}_{||} \subseteq P^{prAM}_{||}$; (ii) $S_2^p \subseteq P^{prAM}$. In addition to providing new upperbounds for the classes $S_2^p$ and $BPP^{NP}_{||}$, these results are interesting ...
more >>>

Hunter Monroe

Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a ... more >>>

Yonatan Bilu, Nathan Linial

We introduce the notion of a stable instance for a discrete

optimization problem, and argue that in many practical situations

only sufficiently stable instances are of interest. The question

then arises whether stable instances of NP--hard problems are

easier to solve. In particular, whether there exist algorithms

that solve correctly ...
more >>>

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

We present new deterministic algorithms for several cases of the maximum rank matrix completion

problem (for short matrix completion), i.e. the problem of assigning values to the variables in

a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to

the fundamental problems in computational complexity ...
more >>>

Gábor Kun, Mario Szegedy

The well known dichotomy conjecture of Feder and

Vardi states that for every ﬁnite family Γ of constraints CSP(Γ) is

either polynomially solvable or NP-hard. Bulatov and Jeavons re-

formulated this conjecture in terms of the properties of the algebra

P ol(Γ), where the latter is ...
more >>>

Harry Buhrman, David García Soriano, Arie Matsliah

We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model.

We design simple, deterministic, polynomial-time algorithms for learning $k$-parities with mistake bound $O(n^{1-\frac{c}{k}})$, for any constant $c > 0$. These are the first polynomial-time algorithms that learn $\omega(1)$-parities in ...
more >>>

Konstantinos Georgiou, Avner Magen, Madhur Tulsiani

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)). We show that if the set of assignments accepted by $P$ contains the support of a balanced pairwise independent distribution over the domain of the inputs, then such a problem on $n$ variables cannot be approximated ... more >>>

Daniele Venturi

The principal aim of this notes is to give a survey on the state of the art of algorithmic number theory, with particular focus on the theory of elliptic curves.

Computational security is the goal of modern cryptographic constructions: the security of modern criptographic schemes stems from the assumption ...
more >>>

Matt DeVos, Ariel Gabizon

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$

such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased

bit when $x$ is chosen uniformly from $X$.

Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ...
more >>>

Harry Buhrman, Lance Fortnow, Rahul Santhanam

We show several unconditional lower bounds for exponential time classes

against polynomial time classes with advice, including:

\begin{enumerate}

\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$

\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$

\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$

\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>

Panagiotis Voulgaris, Daniele Micciancio

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$.

This improves the best previously known algorithm by Ajtai, Kumar ...
more >>>

Arnab Bhattacharyya, Ning Xie

Let $f_{1},f_{2}, f_{3}:\mathbb{F}_{2}^{n} \to \{0,1\}$ be three Boolean functions.

We say a triple $(x,y,x+y)$ is a \emph{triangle} in the function-triple $(f_{1}, f_{2}, f_{3})$ if $f_{1}(x)=f_{2}(y)=f_{3}(x+y)=1$.

$(f_{1}, f_{2}, f_{3})$ is said to be \emph{triangle-free} if there is no triangle in the triple. The distance between a function-triple

and ...
more >>>

Hanna Mazzawi, Nader Bshouty

We prove that for every prime $p$ there exists a $(0,1)$-matrix

$M$ of size $t_p(n,m)\times n$ where

$$t_p(n,m)=O\left(m+\frac{m\log \frac{n}{m}}{\log \min({m,p})}\right)$$ such that every

$m$ columns of $M$ are linearly independent over $\Z_p$, the field

of integers modulo $p$ (and therefore over any field of

characteristic $p$ and over the real ...
more >>>

Dave Buchfuhrer, Chris Umans

Many commonly-used auction mechanisms are ``maximal-in-range''. We show that any maximal-in-range mechanism for $n$ bidders and $m$ items cannot both approximate the social welfare with a ratio better than $\min(n, m^\eta)$ for any constant $\eta < 1/2$ and run in polynomial time, unless $NP \subseteq P/poly$. This significantly improves upon ... more >>>

Parikshit Gopalan

Building on work of Yekhanin and Raghavendra, Efremenko recently gave an elegant construction of 3-query LDCs which achieve sub-exponential length unconditionally.In this note, we observe that this construction can be viewed in the framework of Reed-Muller codes.

more >>>Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom

generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary

constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a

time. This ...
more >>>

John Hitchcock, A. Pavan, N. V. Vinodchandran

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity

extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction

more >>>

Paul Beame, Trinh Huynh

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>

Vikraman Arvind, Pushkar Joglekar, Srikanth Srinivasan

The motivation for this paper is to study the complexity of constant-width arithmetic circuits. Our main results are the following.

1. For every k > 1, we provide an explicit polynomial that can be computed by a linear-sized monotone circuit of width 2k but has no subexponential-sized monotone circuit ...
more >>>

Suguru Tamaki, Yuichi Yoshida

Long Code testing is a fundamental problem in the area of property

testing and hardness of approximation.

Long Code is a function of the form $f(x)=x_i$ for some index $i$.

In the Long Code testing, the problem is, given oracle access to a

collection of Boolean functions, to decide whether ...
more >>>

Oded Goldreich, Brendan Juba, Madhu Sudan

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

Christian Glaßer, Christian Reitwießner, Maximilian Witek

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

Zeev Dvir

The finite field Kakeya problem deals with the way lines in different directions can overlap in a vector space over a finite field. This problem came up in the study of certain Euclidean problems and, independently, in the search for explicit randomness extractors. We survey recent progress on this problem ... more >>>

Falk Unger

We prove a simple concentration inequality, which is an extension of the Chernoff bound and Hoeffding's inequality for binary random variables. Instead of assuming independence of the variables we use a slightly weaker condition, namely bounds on the co-moments.

This inequality allows us to simplify and strengthen several known ... more >>>

Victor Chen, Elena Grigorescu, Ronald de Wolf

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the

decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ...
more >>>

Elad Haramaty, Amir Shpilka

In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias ... more >>>

Olaf Beyersdorff, Zenon Sadowski

In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?

Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>>

T.C. Vijayaraghavan

The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that ... more >>>

Dana Ron, Mira Gonen, Yuval Shavitt

Detecting and counting the number of copies of certain subgraphs (also known as {\em network motifs\/} or {\em graphlets\/}), is motivated by applications in a variety of areas ranging from Biology to the study of the World-Wide-Web. Several polynomial-time algorithms have been suggested for counting or detecting the number of ... more >>>

Arkadev Chattopadhyay, Avi Wigderson

We study solution sets to systems of generalized linear equations of the following form:

$\ell_i (x_1, x_2, \cdots , x_n)\, \in \,A_i \,\, (\text{mod } m)$,

where $\ell_1, \ldots ,\ell_t$ are linear forms in $n$ Boolean variables, each $A_i$ is an arbitrary subset of $\mathbb{Z}_m$, and $m$ is a composite ...
more >>>

Christoph Behle, Andreas Krebs, Stephanie Reifferscheid

We consider the regular languages recognized by weighted threshold circuits with a linear number of wires.

We present a simple proof to show that parity cannot be computed by such circuits.

Our proofs are based on an explicit construction to restrict the input of the circuit such that the value ...
more >>>

Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman

We consider the problem of testing if a given function

$f : \F_2^n \rightarrow \F_2$ is close to any degree $d$ polynomial

in $n$ variables, also known as the Reed-Muller testing problem.

Alon et al.~\cite{AKKLR} proposed and analyzed a natural

$2^{d+1}$-query test for this property and showed that it accepts

more >>>

Olga Tveretina, Carsten Sinz, Hans Zantema

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula has an exponential

size and that limited OBDD derivations cannot simulate resolution polynomially. Here we show that any arbitrary OBDD Apply refutation of the pigeonhole formula has an exponential

size: we prove that the size of one ...
more >>>

Shachar Lovett, Yoav Tzur

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>

Guy Rothblum, Salil Vadhan

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs ... more >>>

Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).

This basic construct underlies “hardness amplification” in cryptography, circuit complexity and

PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent

result by Dinur and ...
more >>>

Thanh Minh Hoang

In the present paper we show some new complexity bounds for

the matching problem for special graph classes.

We show that for graphs with a polynomially bounded number

of nice cycles, the decision perfect matching problem is in

$SPL$, it is hard for $FewL$, and the construction ...
more >>>

Olaf Beyersdorff, Johannes Köbler, Sebastian Müller

One of the starting points of propositional proof complexity is the seminal paper by Cook and Reckhow (JSL 79), where they defined

propositional proof systems as poly-time computable functions which have all propositional tautologies as their range. Motivated by provability consequences in bounded arithmetic, Cook and Krajicek (JSL 07) have ...
more >>>

Vikraman Arvind, Bireswar Das, Johannes Köbler, Seinosuke Toda

We describe a fixed parameter tractable (fpt) algorithm for Colored Hypergraph Isomorphism} which has running time $b!2^{O(b)}N^{O(1)}$, where the parameter $b$ is the maximum size of the color classes of the given hypergraphs and $N$ is the input size. We also describe fpt algorithms for certain permutation group problems that ... more >>>

Bireswar Das, Jacobo Toran, Fabian Wagner

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width

are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}.

We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete ... more >>>

Swapnoneel Roy

The sorting by strip exchanges (aka strip exchanging) problem is motivated by applications in optical character recognition and genome rearrangement analysis. While a couple of approximation algorithms have been designed for the problem, nothing has been known about its computational hardness till date. In this work, we show that the ... more >>>

Haralampos Tsaknakis, Paul Spirakis

We present a new methodology for computing approximate Nash equilibria for two-person non-cooperative games based

upon certain extensions and specializations of an existing optimization approach previously used for the derivation of fixed approximations for this problem. In particular, the general two-person problem is reduced to an indefinite quadratic programming problem ...
more >>>

Rakesh Mohanty, N. S. Narayanaswamy

The main objective of this survey is to present the important theoretical and experimental results contributed till date in the area of online algorithms for the self organizing sequential search problem, also popularly known as the List Update Problem(LUP) in a chronological way. The survey includes competitiveness results of deterministic ... more >>>

Alexander A. Sherstov

The threshold degree of a Boolean function

$f\colon\{0,1\}\to\{-1,+1\}$ is the least degree of a real

polynomial $p$ such $f(x)\equiv\mathrm{sgn}\; p(x).$ We

construct two halfspaces on $\{0,1\}^n$ whose intersection has

threshold degree $\Theta(\sqrt n),$ an exponential improvement on

previous lower bounds. This solves an open problem due to Klivans

(2002) and ...
more >>>

Venkatesan Guruswami, Ali Kemal Sinop

We study the maximization version of the fundamental graph coloring problem. Here the goal is to color the vertices of a $k$-colorable graph with $k$ colors so that a maximum fraction of edges are properly colored (i.e., their endpoints receive different colors). A random $k$-coloring properly colors an expected fraction ... more >>>

Jakob Nordström, Alexander Razborov

In the context of proving lower bounds on proof space in $k$-DNF

resolution, [Ben-Sasson and Nordström 2009] introduced the concept of

minimally unsatisfiable sets of $k$-DNF formulas and proved that a

minimally unsatisfiable $k$-DNF set with $m$ formulas can have at most

$O((mk)^{k+1})$ variables. They also gave an example of ...
more >>>

Nitin Saxena

Polynomial identity testing (PIT) is the problem of checking whether a given

arithmetic circuit is the zero circuit. PIT ranks as one of the most important

open problems in the intersection of algebra and computational complexity. In the last

few years, there has been an impressive progress on this ...
more >>>

Andrew Drucker, Ronald de Wolf

Alongside the development of quantum algorithms and quantum complexity theory in recent years, quantum techniques have also proved instrumental in obtaining results in classical (non-quantum) areas. In this paper we survey these results and the quantum toolbox they use.

more >>>Vikraman Arvind, Srikanth Srinivasan

In this paper we study the computational complexity of computing the noncommutative determinant. We first consider the arithmetic circuit complexity of computing the noncommutative determinant polynomial. Then, more generally, we also examine the complexity of computing the determinant (as a function) over noncommutative domains. Our hardness results are summarized below:

... more >>>Scott Aaronson

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier analysis.

First, we show that there ... more >>>

Vikraman Arvind, Srikanth Srinivasan

Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma

The rigidity of a matrix A for target rank r is the minimum number of entries

of A that must be changed to ensure that the rank of the altered matrix is at

most r. Since its introduction by Valiant (1977), rigidity and similar

rank-robustness functions of matrices have found ...
more >>>

Kevin Dick, Chris Umans

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are $\Sigma_2^p$-hard to approximate to within factors of $n^{1/3-\epsilon}$ and $n^{1/2-\epsilon}$ (where the previous results achieved $n^{1/4 - \epsilon}$), ... more >>>

Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two ... more >>>

Kai-Min Chung, Feng-Hao Liu

Following Hastad, Pass, Pietrzak, and Wikstrom (2008), we study parallel repetition theorems for public-coin interactive arguments and their generalization. We obtain the following results:

1. We show that the reduction of Hastad et al. actually gives a tight direct product theorem for public-coin interactive arguments. That is, $n$-fold parallel repetition ... more >>>

Scott Aaronson, Andris Ambainis

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that ... more >>>

Walid Gomaa

Model theory is a branch of mathematical logic that investigates the

logical properties of mathematical structures. It has been quite

successfully applied to computational complexity resulting in an

area of research called descriptive complexity theory. Descriptive

complexity is essentially a syntactical characterization of

complexity classes using logical formalisms. However, there ...
more >>>

Davide Bilò, Luciano Gualà, Guido Proietti

Consider a communication network represented by a directed graph $G=(V,E)$ of $n$ nodes and $m$ edges. Assume that edges in $E$ are

partitioned into two sets: a set $C$ of edges with a fixed

non-negative real cost, and a set $P$ of edges whose \emph{price} should instead be set by ...
more >>>

Anindya De, Luca Trevisan, Madhur Tulsiani

We study the power of non-uniform attacks against one-way

functions and pseudorandom generators.

Fiat and Naor show that for every function

$f: [N]\to [N]$

there is an algorithm that inverts $f$ everywhere using

(ignoring lower order factors)

time, space and advice at most $N^{3/4}$.

We show that ... more >>>

Emanuele Viola

Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.

Our main results are:

\begin{itemize}

\item There are explicit $AC^0$ circuits of ...
more >>>

Swastik Kopparty, Shubhangi Saraf

In this paper, we give surprisingly efficient algorithms for list-decoding and testing

{\em random} linear codes. Our main result is that random sparse linear codes are locally testable and locally list-decodable

in the {\em high-error} regime with only a {\em constant} number of queries.

More precisely, we show that ...
more >>>

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

We give the first sub-exponential time deterministic polynomial

identity testing algorithm for depth-$4$ multilinear circuits with

a small top fan-in. More accurately, our algorithm works for

depth-$4$ circuits with a plus gate at the top (also known as

$\Spsp$ circuits) and has a running time of

$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ...
more >>>

Ilias Diakonikolas, Daniel Kane, Jelani Nelson

Let x be a random vector coming from any k-wise independent distribution over {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is determined up to an additive epsilon for k = poly(1/epsilon). This answers an open question of Diakonikolas et al. (FOCS 2009). Using standard constructions of ... more >>>

Shachar Lovett, Ido Ben-Eliezer, Ariel Yadin

We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power of this model.

Our first result shows that low-degree polynomial threshold functions cannot approximate any function with many influential variables. We ...
more >>>

Frederic Magniez, Claire Mathieu, Ashwin Nayak

Motivated by a concrete problem and with the goal of understanding the sense in which the complexity of streaming algorithms is related to the complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with $s$ different types of parenthesis.

We present a one-pass randomized streaming ... more >>>

Charanjit Jutla

We consider weakly-verifiable puzzles which are challenge-response puzzles such that the responder may not

be able to verify for itself whether it answered the challenge correctly. We consider $k$-wise direct product of

such puzzles, where now the responder has to solve $k$ puzzles chosen independently in parallel.

Canetti et ...
more >>>

Zohar Karnin, Yuval Rabani, Amir Shpilka

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of

any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at

least a fraction of $1 - o(1)$ of the transformations in the set.

Albeit the tradeoff between ...
more >>>

Vikraman Arvind, Srikanth Srinivasan

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving ... more >>>

Hemanta Maji, Manoj Prabhakaran, Mike Rosulek

Which computational intractability assumptions are inherent to cryptography? We present a broad framework to pose and investigate this question.

We first aim to understand the “cryptographic complexity” of various tasks, independent of any computational assumptions. In our framework the cryptographic tasks are modeled as multi- party computation functionalities. We consider ...
more >>>

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth Vishnoi

In this paper we will be concerned with a large class of packing

and covering problems which includes Vertex Cover and Independent Set.

Typically, for NP-hard problems among them, one can write an LP relaxation and

then round the solution. For instance, for Vertex Cover, one can obtain a

more >>>

David Steurer, Nisheeth Vishnoi

In this paper we demonstrate a close connection between UniqueGames and

MultiCut.

%

In MultiCut, one is given a ``network graph'' and a ``demand

graph'' on the same vertex set and the goal is to remove as few

edges from the network graph as ...
more >>>

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes

whose duals have (superlinearly) {\em many} small weight ...
more >>>

Brett Hemenway, Rafail Ostrovsky

In STOC '08, Peikert and Waters introduced a powerful new primitive called Lossy Trapdoor Functions (LTDFs). Since their introduction, lossy trapdoor functions have found many uses in cryptography. In the work of Peikert and Waters, lossy trapdoor functions were used to give an efficient construction of a chosen-ciphertext secure ... more >>>

Gillat Kol, Ran Raz

The Unique Games Conjecture (UGC) is possibly the most important open problem in the research of PCPs and hardness of approximation. The conjecture is a strengthening of the PCP Theorem, predicting the existence of a special type of PCP verifiers: 2-query verifiers that only make unique tests. Moreover, the UGC ... more >>>

Boaz Barak, Moritz Hardt, Thomas Holenstein, David Steurer

We study the question of whether the value of mathematical programs such as

linear and semidefinite programming hierarchies on a graph $G$, is preserved

when taking a small random subgraph $G'$ of $G$. We show that the value of the

Goemans-Williamson (1995) semidefinite program (SDP) for \maxcut of $G'$ is

more >>>

Ryan O'Donnell, YI WU, Yuan Zhou

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>

Stephan Kreutzer, Anuj Dawar

We show that if $\mathcal C$ is a class of graphs which is

"nowhere dense" then first-order model-checking is

fixed-parameter tractable on $\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ...
more >>>

Lior Malka

Perfect zero-knowledge (PZK) proofs have been constructed in various settings and they are

also interesting from a complexity theoretic perspective. Yet, virtually nothing is known about them. This is in contrast to statistical zero-knowledge proofs, where many general results have been proved using an array of tools, none of which ...
more >>>

Anindya De, Thomas Vidick

We give near-optimal constructions of extractors secure against quantum bounded-storage adversaries. One instantiation gives the first such extractor to achieve an output length Theta(K-b), where K is the source's entropy and b the adversary's storage, depending linearly on the adversary's amount of storage, together with a poly-logarithmic seed length. Another ... more >>>

Zeev Dvir

We describe a new approach for the problem of finding {\rm rigid} matrices, as posed by Valiant [Val77], by connecting it to the, seemingly unrelated, problem of proving lower bounds for locally self-correctable codes. This approach, if successful, could lead to a non-natural property (in the sense of Razborov and ... more >>>

Zeev Dvir, Avi Wigderson

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:

(1) Constant degree dimension expanders in finite ...
more >>>

Michael Burr, Felix Krahmer, Chee Yap

Let $f$ be a univariate polynomial with real coefficients, $f\in\RR[X]$. Subdivision algorithms based on algebraic techniques (e.g., Sturm or Descartes methods) are widely used for isolating the roots of $f$ in a given interval. In this paper, we consider subdivision algorithms based on purely numerical primitives such as function evaluation.

more >>>

Massimo Lauria

We study the space required by Polynomial Calculus refutations of random $k$-CNFs. We are interested in how many monomials one needs to keep in memory to carry on a refutation. More precisely we show that for $k \geq 4$ a refutation of a random $k$-CNF of $\Delta n$ clauses and ... more >>>

Gillat Kol, Ran Raz

We study Locally Testable Codes (LTCs) that can be tested by making two queries to the tested word using an affine test. That is, we consider LTCs over a finite field F, with codeword testers that only use tests of the form $av_i + bv_j = c$, where v is ... more >>>

Mohammad Mahmoody, David Xiao

The closure of complexity classes is a elicate question and the answer varies depending on the type of reduction considered. The closure of most classes under many-to-one (Karp) reductions is clear, but the question becomes complicated when oracle (Cook) reductions are allowed, and even more so when the oracle reductions ... more >>>

Saugata Basu

Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy,

$\mathbf{PH}$,

is contained in the class $\mathbf{P}^{\#\mathbf{P}}$,

namely the class of languages that can be

decided by a Turing machine in polynomial time given access to an

oracle with the power to compute a function in the ...
more >>>

Anindya De, Omid Etesami, Luca Trevisan, Madhur Tulsiani

We prove the existence of a $poly(n,m)$-time computable

pseudorandom generator which ``$1/poly(n,m)$-fools'' DNFs with $n$ variables

and $m$ terms, and has seed length $O(\log^2 nm \cdot \log\log nm)$.

Previously, the best pseudorandom generator for depth-2 circuits had seed

length $O(\log^3 nm)$, and was due to Bazzi (FOCS 2007).

It ... more >>>

Aaron Potechin

We prove that any monotone switching network solving directed connectivity on $N$ vertices must have size $N^{\Omega(\log N)}$

more >>>Noam Livne

In this paper we study the possibility of proving the existence of

one-way functions based on average case hardness. It is well-known

that if there exists a polynomial-time sampler that outputs

instance-solution pairs such that the distribution on the instances

is hard on average, then one-way functions exist. We study ...
more >>>

Prahladh Harsha, Adam Klivans, Raghu Meka

Let $X$ be randomly chosen from $\{-1,1\}^n$, and let $Y$ be randomly

chosen from the standard spherical Gaussian on $\R^n$. For any (possibly unbounded) polytope $P$

formed by the intersection of $k$ halfspaces, we prove that

$$\left|\Pr\left[X \in P\right] - \Pr\left[Y \in P\right]\right| \leq \log^{8/5}k ...
more >>>

Shankar Kalyanaraman, Chris Umans

We study the complexity of {\em rationalizing} network formation. In

this problem we fix an underlying model describing how selfish

parties (the vertices) produce a graph by making individual

decisions to form or not form incident edges. The model is equipped

with a notion of stability (or equilibrium), and we ...
more >>>

Dan Gutfreund, Akinori Kawachi

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>

Stephan Kreutzer

Algorithmic meta-theorems are general algorithmic results applying to a whole range of problems, rather than just to a single problem alone. They often have a logical and a

structural component, that is they are results of the form:

"every computational problem that can be formalised in a given logic L ...
more >>>