Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMPUTATIONAL COMPLEXITY:
Reports tagged with Computational Complexity:
TR94-022 | 12th December 1994
Christoph Meinel, Stephan Waack

#### The Möbius Function, Variations Ranks, and Theta(n)--Bounds on the Modular Communication Complexity of the Undirected Graph Connectivity Problem

We prove that the modular communication complexity of the
undirected graph connectivity problem UCONN equals Theta(n),
in contrast to the well-known Theta(n*log n) bound in the
deterministic case, and to the Omega(n*loglog n) lower bound
in the nondeterministic case, recently proved by ... more >>>

TR94-021 | 12th December 1994
Lance Fortnow

#### My Favorite Ten Complexity Theorems of the Past Decade

We review the past ten years in computational complexity theory by
focusing on ten theorems that the author enjoyed the most. We use
each of the theorems as a springboard to discuss work done in
various areas of complexity theory.

more >>>

TR95-027 | 30th May 1995
Frederic Green

#### Lower Bounds for Circuits with Mod Gates and One Exact Threshold Gate

We say an integer polynomial $p$, on Boolean inputs, weakly
$m$-represents a Boolean function $f$ if $p$ is non-constant and is zero (mod
$m$), whenever $f$ is zero. In this paper we prove that if a polynomial
weakly $m$-represents the Mod$_q$ function on $n$ inputs, where $q$ and $m$
more >>>

TR95-034 | 30th June 1995
Christoph Meinel, Stephan Waack

#### Lower Bounds for the Majority Communication Complexity of Various Graph Accessibility Problems

We investigate the probabilistic communication complexity
(more exactly, the majority communication complexity,)
of the graph accessibility problem GAP and
its counting versions MOD_k-GAP, k > 1.
Due to arguments concerning matrix variation ranks
and certain projection reductions, we prove
that, for any partition of the input variables,
more >>>

TR95-040 | 26th July 1995
Uri Zwick, Michael S. Paterson

#### The complexity of mean payoff games on graphs

We study the complexity of finding the values and optimal strategies of
MEAN PAYOFF GAMES on graphs, a family of perfect information games
introduced by Ehrenfeucht and Mycielski and considered by Gurvich,
Karzanov and Khachiyan. We describe a pseudo-polynomial time algorithm
for the solution of such games, the decision ... more >>>

TR96-005 | 9th January 1996
Hans-Joerg Burtschick, Heribert Vollmer

#### Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1

We show that examinations of the expressive power of logical formulae
enriched by Lindstroem quantifiers over ordered finite structures
have a well-studied complexity-theoretic counterpart: the leaf
language approach to define complexity classes. Model classes of
formulae with Lindstroem quantifiers are nothing else than leaf
language definable sets. Along the ... more >>>

TR96-006 | 24th January 1996
Bernd Borchert, Antoni Lozano

#### Succinct Circuit Representations and Leaf Language Classes are Basically the same Concept

This note connects two topics of Complexity Theory: The
topic of succinct circuit representations initiated by
Galperin and Wigderson and the topic of leaf languages
initiated by Bovet, Crescenzi, and Silvestri. It will be
shown for any language that its succinct version is
more >>>

TR96-011 | 29th January 1996
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith

#### Sharply Bounded Alternation within P

We define the sharply bounded hierarchy, SBHQL, a hierarchy of
classes within P, using quasilinear-time computation and
quantification over values of length log n. It generalizes the
limited nondeterminism hierarchy introduced by Buss and Goldsmith,
while retaining the invariance properties. The new hierarchy has
several alternative characterizations.

We define ... more >>>

TR96-015 | 12th December 1995
Edoardo Amaldi, Viggo Kann

#### On the approximability of some NP-hard minimization problems for linear systems

We investigate the computational complexity of two classes of
combinatorial optimization problems related to linear systems
and study the relationship between their approximability properties.
In the first class (MIN ULR) one wishes, given a possibly infeasible
system of linear relations, to find ... more >>>

TR96-021 | 13th February 1996
Yongge Wang

#### NP-hard Sets Are Superterse unless NP Is Small

We show that the class of sets which can be polynomial
time truth table reduced to some $p$-superterse sets has
$p$-measure 0. Hence, no $P$-selective set is $\le_{tt}^p$-hard
for $E$. Also we give a partial affirmative answer to
the conjecture by Beigel, Kummer and ... more >>>

TR96-027 | 20th February 1996
Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

#### Computing Solutions Uniquely Collapses the Polynomial Hierarchy

Is there an NP function that, when given a satisfiable formula
as input, outputs one satisfying assignment uniquely? That is, can a
nondeterministic function cull just one satisfying assignment from a
possibly exponentially large collection of assignments? We show that if
there is such a nondeterministic function, then the polynomial ... more >>>

TR96-031 | 30th April 1996

#### Networks of Spiking Neurons: The Third Generation of Neural Network Models

The computational power of formal models for
networks of spiking neurons is compared with
that of other neural network models based on
McCulloch Pitts neurons (i.e. threshold gates)
respectively sigmoidal gates. In particular it
is shown that networks of spiking neurons are
... more >>>

TR96-043 | 16th August 1996
Edmund Ihler

#### On polynomial time approximation schemes and approximation preserving reductions

We show that a fully polynomial time approximation scheme given
for an optimization problem can always be simply modified to a
polynomial time algorithm solving the problem optimally if the
computation model is the deterministic Turing Machine or the
logarithmic cost RAM and ... more >>>

TR96-045 | 28th August 1996
Bernd Borchert, Lane A. Hemaspaandra, Jörg Rothe

#### Powers-of-Two Acceptance Suffices for Equivalence and Bounded Ambiguity Problems

We study EP, the subclass of NP consisting of those
languages accepted by NP machines that when they accept always have a
number of accepting paths that is a power of two. We show that the
negation equivalence problem for OBDDs (ordered binary decision
diagrams) ... more >>>

TR96-062 | 3rd December 1996
Sanjeev Khanna, Madhu Sudan, David P. Williamson

#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier ... more >>>

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

#### Constraint satisfaction: The approximability of minimization problems.

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

#### On the Efficiency of Polynomial Time Approximation Schemes

A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ... more >>> TR97-004 | 19th February 1997 Marek Karpinski, Alexander Zelikovsky #### Approximating Dense Cases of Covering Problems Comments: 1 We study dense instances of several covering problems. An instance of the set cover problem with$m$sets is dense if there is$\epsilon>0$such that any element belongs to at least$\epsilon m$sets. We show that the dense set cover problem can be approximated with ... more >>> TR97-006 | 31st January 1997 Marco Cesati, Miriam Di Ianni #### Parameterized Parallel Complexity Comments: 1 We consider the framework of Parameterized Complexity, and we investigate the issue of which problems do admit efficient fixed parameter parallel algorithms by introducing two different degrees of efficiently parallelizable parameterized problems, PNC and FPP. We sketch both some FPP-algorithms solving natural parameterized problems and ... more >>> TR97-009 | 12th March 1997 Jonathan F. Buss, Gudmund Skovbjerg Frandsen, Jeffrey O. Shallit #### The Computational Complexity of Some Problems of Linear Algebra We consider the computational complexity of some problems dealing with matrix rank. Let E,S be subsets of a commutative ring R. Let x_1, x_2, ..., x_t be variables. Given a matrix M = M(x_1, x_2, ..., x_t) with entries chosen from E union {x_1, x_2, ..., ... more >>> TR97-024 | 9th June 1997 Marek Karpinski #### Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard optimization problems. We indicate further some inherent limits for existence of such schemes for some other dense instances of the optimization problems. more >>> TR98-014 | 6th February 1998 Gunter Blache, Marek Karpinski, Juergen Wirtgen #### On Approximation Intractability of the Bandwidth Problem The bandwidth problem is the problem of enumerating the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications. There was not ... more >>> TR98-022 | 14th April 1998 Steffen Reith, Heribert Vollmer #### The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns out that for each class from our framework, the above problem is either polynomial time solvable or complete for ... more >>> TR98-029 | 27th May 1998 Piotr Berman, Marek Karpinski #### On Some Tighter Inapproximability Results We prove a number of improved inaproximability results, including the best up to date explicit approximation thresholds for MIS problem of bounded degree, bounded occurrences MAX-2SAT, and bounded degree Node Cover. We prove also for the first time inapproximability of the problem of Sorting by ... more >>> TR98-038 | 9th July 1998 Marek Karpinski #### On the Computational Power of Randomized Branching Programs We survey some upper and lower bounds established recently on the sizes of randomized branching programs computing explicit boolean functions. In particular, we display boolean functions on which randomized read-once ordered branching programs are exponentially more powerful than deterministic or nondeterministic read-$k$-times branching programs for ... more >>> TR98-058 | 2nd August 1998 H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar #### A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem We introduce "resource-bounded betting games", and propose a generalization of Lutz's resource-bounded measure in which the choice of next string to bet on is fully adaptive. Lutz's martingales are equivalent to betting games constrained to bet on strings in lexicographic order. We show that if strong pseudo-random number generators exist, more >>> TR98-059 | 15th September 1998 C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer #### The Descriptive Complexity Approach to LOGCFL Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC^1 and its subclasses. In the ... more >>> TR98-064 | 6th November 1998 Wenceslas Fernandez de la Vega, Marek Karpinski #### Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT We give the first polynomial time approximability characterization of dense weighted instances of MAX-CUT, and some other dense weighted NP-hard problems in terms of their empirical weight distributions. This gives also the first almost sharp characterization of inapproximability of unweighted 0,1 MAX-BISECTION instances ... more >>> TR98-067 | 12th November 1998 Paul Beame #### Propositional Proof Complexity: Past, Present and Future Proof complexity, the study of the lengths of proofs in propositional logic, is an area of study that is fundamentally connected both to major open questions of computational complexity theory and to practical properties of automated theorem provers. In the last decade, there have been a number of significant advances ... more >>> TR00-002 | 23rd December 1999 Michael Schmitt #### Lower Bounds on the Complexity of Approximating Continuous Functions by Sigmoidal Neural Networks We calculate lower bounds on the size of sigmoidal neural networks that approximate continuous functions. In particular, we show that for the approximation of polynomials the network size has to grow as$\Omega((\log k)^{1/4})$where$k$is the degree of the polynomials. This bound is ... more >>> TR00-010 | 12th January 2000 Amitabha Roy, Christopher Wilson #### Supermodels and Closed Sets A {\em supermodel} is a satisfying assignment of a boolean formula for which any small alteration, such as a single bit flip, can be repaired by another small alteration, yielding a nearby satisfying assignment. We study computational problems associated with super models and some generalizations thereof. For general formulas, ... more >>> TR00-048 | 3rd July 2000 Beate Bollig #### Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Branching programs are a well established computation model for Boolean functions, especially read-once branching programs have been studied intensively. In this paper the expressive power of nondeterministic read-once branching programs, i.e., the class of functions representable in polynomial size, is investigated. For that reason two restricted models of nondeterministic read-once more >>> TR00-061 | 14th August 2000 Prahladh Harsha, Madhu Sudan #### Small PCPs with low query complexity Most known constructions of probabilistically checkable proofs (PCPs) either blow up the proof size by a large polynomial, or have a high (though constant) query complexity. In this paper we give a transformation with slightly-super-cubic blowup in proof size, with a low query complexity. Specifically, the verifier probes the proof ... more >>> TR00-075 | 7th September 2000 Andreas Klein, Martin Kutrib #### Deterministic Turing Machines in the Range between Real-Time and Linear-Time Deterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n+r(n) where r in o(n) is a sublinear function. It is shown that there ... more >>> TR00-081 | 5th September 2000 Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe #### On the difference between polynomial-time many-one and truth-table reducibilities on distributional problems In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P neq NP. As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT using a version of the standard distribution ... more >>> TR01-066 | 28th September 2001 Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger #### On Multipartition Communication Complexity We study k-partition communication protocols, an extension of the standard two-party best-partition model to k input partitions. The main results are as follows. 1. A strong explicit hierarchy on the degree of non-obliviousness is established by proving that, using k+1 partitions instead of k may decrease the communication complexity from ... more >>> TR01-073 | 24th October 2001 Beate Bollig, Philipp Woelfel, Stephan Waack #### Parity Graph-driven Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication Revisions: 1 Branching programs are a well-established computation model for Boolean functions, especially read-once branching programs have been studied intensively. Exponential lower bounds for deterministic and nondeterministic read-once branching programs are known for a long time. On the other hand, the problem of proving superpolynomial lower bounds ... more >>> TR01-076 | 24th October 2001 Robert Albin Legenstein #### On the Complexity of Knock-knee Channel-Routing with 3-Terminal Nets In this article we consider a basic problem in the layout of VLSI-circuits, the channel-routing problem in the knock-knee mode. We show that knock-knee channel routing with 3-terminal nets is NP-complete and thereby settling a problem that was open for more than a decade. In 1987, Sarrafzadeh showed that knock-knee ... more >>> TR01-103 | 14th December 2001 Dima Grigoriev, Edward Hirsch, Dmitrii V. Pasechnik #### Complexity of semi-algebraic proofs Revisions: 3 It is a known approach to translate propositional formulas into systems of polynomial inequalities and to consider proof systems for the latter ones. The well-studied proof systems of this kind are the Cutting Planes proof system (CP) utilizing linear inequalities and the Lovasz-Schrijver calculi (LS) utilizing quadratic ... more >>> TR02-014 | 10th December 2001 Klaus Weihrauch #### Computational Complexity on Computable Metric Spaces Revisions: 1 We introduce a new Turing machine based concept of time complexity for functions on computable metric spaces. It generalizes the ordinary complexity of word functions and the complexity of real functions studied by Ko \cite{Ko91} et al. Although this definition of${\rm TIME}$as the maximum of a generally infinite ... more >>> TR02-068 | 10th December 2002 Tobias Riege, Jörg Rothe #### Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem Revisions: 2 We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number ... more >>> TR03-059 | 18th May 2003 Harumichi Nishimura, Tomoyuki Yamakami #### Polynomial time quantum computation with advice Revisions: 2 Advice is supplementary information that enhances the computational power of an underlying computation. This paper focuses on advice that is given in the form of a pure quantum state. The notion of advised quantum computation has a direct connection to non-uniform quantum circuits and tally languages. The paper examines the ... more >>> TR03-067 | 14th August 2003 Ran Raz #### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear. We prove that any multi-linear arithmetic formula for the permanent or the determinant of an$n \times n$matrix is of size super-polynomial in$n$. more >>> TR03-068 | 30th July 2003 Matthias Homeister #### Lower Bounds for the Sum of Graph--driven Read--Once Parity Branching Programs We prove the first lower bound for restricted read-once parity branching programs with unlimited parity nondeterminism where for each input the variables may be tested according to several orderings. Proving a superpolynomial lower bound for read-once parity branching programs is still a challenging open problem. The following variant ... more >>> TR04-029 | 7th April 2004 John Hitchcock, Maria Lopez-Valdes, Elvira Mayordomo #### Scaled dimension and the Kolmogorov complexity of Turing hard sets Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE. more >>> TR04-042 | 21st May 2004 Ran Raz #### Multilinear-$NC_1\ne$Multilinear-$NC_2$An arithmetic circuit or formula is multilinear if the polynomial computed at each of its wires is multilinear. We give an explicit example for a polynomial$f(x_1,...,x_n)$, with coefficients in$\{0,1\}$, such that over any field: 1)$f$can be computed by a polynomial-size multilinear circuit of depth$O(\log^2 ... more >>>

TR04-047 | 22nd April 2004
Xiaoyang Gu

#### A note on dimensions of polynomial size circuits

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension $0$. We also show that $\Ppoly^\io$ has $\pthree$-dimension $1/2$, $\pthree$-strong dimension $1$. Our results improve previous measure results of Lutz (1992) and dimension ... more >>>

TR04-055 | 27th May 2004
Kousha Etessami, Andreas Lochbihler

#### The computational complexity of Evolutionarily Stable Strategies

Game theory has been used for a long time to study phenomena in evolutionary biology, beginning systematically with the seminal work of John Maynard Smith. A central concept in this connection has been the notion of an evolutionarily stable strategy (ESS) in a symmetric two-player strategic form game. A regular ... more >>>

TR04-059 | 21st June 2004
Beatrice List, Markus Maucher, Uwe Schöning, Rainer Schuler

#### Randomized Quicksort and the Entropy of the Random Number Generator

The worst-case complexity of an implementation of Quicksort depends
on the random number generator that is used to select the pivot
elements. In this paper we estimate the expected number of
comparisons of Quicksort as a function in the entropy of the random
source. We give upper and lower bounds ... more >>>

TR04-111 | 30th November 2004
Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

#### Computational Complexity of Some Restricted Instances of 3SAT

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>

TR04-119 | 8th December 2004
Uriel Feige, Daniel Reichman

#### On The Hardness of Approximating Max-Satisfy

Max-Satisfy is the problem of finding an assignment that satisfies
the maximum number of equations in a system of linear equations
over $\mathbb{Q}$. We prove that unless NP$\subseteq$BPP there is no
polynomial time algorithm for the problem achieving an
approximation ratio of $1/n^{1-\epsilon}$, where $n$ is the number
of ... more >>>

TR05-008 | 11th December 2004
Neeraj Kayal

#### Recognizing permutation functions in polynomial time.

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.
The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on
the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map
n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their reductions are based on norm embeddings. However, ... more >>> TR06-060 | 4th May 2006 Ran Raz, Amir Shpilka, Amir Yehudayoff #### A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits We construct an explicit polynomial$f(x_1,...,x_n)$, with coefficients in${0,1}$, such that the size of any syntactically multilinear arithmetic circuit computing$f$is at least$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field. more >>> TR06-091 | 29th May 2006 Felix Brandt, Felix Fischer, Markus Holzer #### Symmetries and the Complexity of Pure Nash Equilibrium Strategic games may exhibit symmetries in a variety of ways. A common aspect of symmetry, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering ... more >>> TR06-133 | 14th October 2006 Alex Hertel, Alasdair Urquhart #### The Resolution Width Problem is EXPTIME-Complete The importance of {\em width} as a resource in resolution theorem proving has been emphasized in work of Ben-Sasson and Wigderson. Their results show that lower bounds on the size of resolution refutations can be proved in a uniform manner by demonstrating lower bounds on the width ... more >>> TR06-153 | 19th October 2006 Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer #### The Complexity of Generalized Satisfiability for Linear Temporal Logic Revisions: 1 In a seminal paper from 1985, Sistla and Clarke showed that satisfiability for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used If, in contrast, the set of propositional operators is restricted, the complexity may ... more >>> TR07-023 | 26th February 2007 Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor #### The Complexity of Problems for Quantified Constraints In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>> TR07-045 | 24th April 2007 Heribert Vollmer #### The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis We study the complexity of the following algorithmic problem: Given a Boolean function$f$and a finite set of Boolean functions$B$, decide if there is a circuit with basis$B$that computes$f$. We show that if both$f$and all functions in$B$are given by their truth-table, ... more >>> TR07-049 | 1st June 2007 Beate Bollig, Niko Range, Ingo Wegener #### Exact OBDD Bounds for some Fundamental Functions Ordered binary decision diagrams (OBDDs) are nowadays the most common dynamic data structure or representation type for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many even exponential lower bounds on the OBDD size of Boolean ... more >>> TR07-084 | 4th September 2007 Brendan Juba, Madhu Sudan #### Universal Semantic Communication I Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly ... more >>> TR07-110 | 24th October 2007 Beate Bollig #### The Optimal Read-Once Branching Program Complexity for the Direct Storage Access Function Branching programs are computation models measuring the space of (Turing machine) computations. Read-once branching programs (BP1s) are the most general model where each graph-theoretical path is the computation path for some input. Exponential lower bounds on the size of read-once branching programs are known since a long time. Nevertheless, there ... more >>> TR07-129 | 25th October 2007 Jeffrey C. Jackson, Homin Lee, Rocco Servedio, Andrew Wan #### Learning Random Monotone DNF We give an algorithm that with high probability properly learns random monotone t(n)-term DNF under the uniform distribution on the Boolean cube {0, 1}^n. For any polynomially bounded function t(n) <= poly(n) the algorithm runs in time poly(n, 1/eps) and with high probability outputs an eps accurate monotone DNF ... more >>> TR07-136 | 28th November 2007 Felix Brandt, Felix Fischer, Markus Holzer #### Equilibria of Graphical Games with Symmetries We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>> TR08-028 | 5th December 2007 Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer #### The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments In a seminal paper from 1985, Sistla and Clarke showed that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete, depending on the set of temporal operators used. If, in contrast, the set of propositional operators is restricted, the complexity may decrease. ... more >>> TR08-029 | 7th January 2008 Christian Glaßer, Christian Reitwießner, Victor Selivanov #### The Shrinking Property for NP and coNP We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results. 1. NP ... more >>> TR08-031 | 14th January 2008 James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, Scott M. Summers #### Computability and Complexity in Self-Assembly This paper explores the impact of geometry on computability = and complexity in Winfree's model of nanoscale self-assembly. We work in the = two-dimensional tile assembly model, i.e., in the discrete Euclidean plane Z x Z. Our = first main theorem says that there is a roughly quadratic function f ... more >>> TR08-077 | 23rd May 2008 Felix Brandt, Felix Fischer, Markus Holzer #### On Iterated Dominance, Matrix Elimination, and Matched Paths We study computational problems that arise in the context of iterated dominance in anonymous games, and show that deciding whether a game can be solved by means of iterated weak dominance is NP-hard for anonymous games with three actions. For the case of two actions, this problem can be reformulated ... more >>> TR08-086 | 9th July 2008 Vikraman Arvind, Partha Mukhopadhyay #### Quantum Query Complexity of Multilinear Identity Testing Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring$R=\angle{r_1,\cdots,r_k}$where$\{r_1,r_2,\cdots,r_k\}$is an additive generating set for$R$and a multilinear polynomial$f(x_1,\cdots,x_m)$over$R$also accessed as a ... more >>> TR08-095 | 31st October 2008 Brendan Juba, Madhu Sudan #### Universal Semantic Communication II: A Theory of Goal-Oriented Communication Revisions: 1 We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>> TR09-022 | 16th February 2009 Jack H. Lutz, Elvira Mayordomo #### Inseparability and Strong Hypotheses for Disjoint NP Pairs Revisions: 1 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 >>> TR09-045 | 20th May 2009 Iftach Haitner, Omer Reingold, Salil Vadhan, Hoeteck Wee #### Inaccessible Entropy 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 >>> TR09-057 | 23rd June 2009 Yonatan Bilu, Nathan Linial #### Are stable instances easy? 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 >>> 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 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 >>> TR09-108 | 31st October 2009 Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky #### Equivalence of Uniform Key Agreement and Composition Insecurity Revisions: 1 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 >>> TR10-160 | 28th October 2010 Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan #### On Approximating the Entropy of Polynomial Mappings We investigate the complexity of the following computational problem: Polynomial Entropy Approximation (PEA): Given a low-degree polynomial mapping$p : F^n\rightarrow F^m$, where$F$is a finite field, approximate the output entropy$H(p(U_n))$, where$U_n$is the uniform distribution on$F^n$and$H$may be any of several entropy measures. ... more >>> TR10-163 | 3rd November 2010 Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolay Vereshchagin #### Sparse Selfreducible Sets and Nonuniform Lower Bounds It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in$EXP^{NP}$, or even ... more >>> TR11-015 | 8th December 2010 Marcel R. Ackermann, Johannes Blömer, Christoph Scholz #### Hardness and Non-Approximability of Bregman Clustering Problems We prove the computational hardness of three k-clustering problems using an (almost) arbitrary Bregman divergence as dissimilarity measure: (a) The Bregman k-center problem, where the objective is to find a set of centers that minimizes the maximum dissimilarity of any input point towards its closest center, and (b) the Bregman ... more >>> TR11-025 | 19th February 2011 Yang Li #### Monotone Rank and Separations in Computational Complexity Revisions: 1 , Comments: 1 In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity. \begin{itemize} \item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>> TR11-141 | 2nd November 2011 Salil Vadhan, Colin Jia Zheng #### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions Revisions: 3 We provide a characterization of pseudoentropy in terms of hardness of sampling: Let$(X,B)$be jointly distributed random variables such that$B$takes values in a polynomial-sized set. We show that$B$is computationally indistinguishable from a random variable of higher Shannon entropy given$X$if and only if there ... more >>> TR12-009 | 28th November 2011 Prabhu Manyem, Julien Ugon #### Computational Complexity, NP Completeness and Optimization Duality: A Survey We survey research that studies the connection between the computational complexity of optimization problems on the one hand, and the duality gap between the primal and dual optimization problems on the other. To our knowledge, this is the first survey that connects the two very important areas. We further look ... more >>> TR12-067 | 6th May 2012 Xiaohui Bei, Ning Chen, Shengyu Zhang #### On the Complexity of Trial and Error Revisions: 1 Motivated by certain applications from physics, biochemistry, economics, and computer science in which the objects under investigation are unknown or not directly accessible because of various limitations, we propose a trial-and-error model to examine search problems with unknown inputs. Given a search problem with a hidden input, we are asked ... more >>> TR12-176 | 14th December 2012 Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu #### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>> TR14-065 | 2nd May 2014 Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska #### Approximate Counting of Matchings in$(3,3)$-Hypergraphs We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as$(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>> TR14-077 | 2nd June 2014 Andris Ambainis, Jevgenijs Vihrovs #### Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma Revisions: 2 We study the structure of sets$S\subseteq\{0, 1\}^n$with small sensitivity. The well-known Simon's lemma says that any$S\subseteq\{0, 1\}^n$of sensitivity$s$must be of size at least$2^{n-s}$. This result has been useful for proving lower bounds on sensitivity of Boolean functions, with applications to the theory of ... more >>> TR14-116 | 6th September 2014 Rahul Mehta #### 2048 is (PSPACE) Hard, but Sometimes Easy We prove that a variant of 2048, a popular online puzzle game, is PSPACE-Complete. Our hardness result holds for a version of the problem where the player has oracle access to the computer player's moves. Specifically, we show that for an$n \times n$game board$G$, computing a more >>> TR14-167 | 11th November 2014 Beate Bollig #### On the Minimization of (Complete) Ordered Binary Decision Diagrams Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions. Some applications work with a restricted variant called complete OBDDs which is strongly related to nonuniform deterministic finite automata. One of its complexity measures is the width which has been investigated in several areas in computer science ... more >>> TR15-021 | 5th February 2015 Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf #### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>> TR15-076 | 28th April 2015 Mahdi Cheraghchi, Piotr Indyk #### Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform For every fixed constant$\alpha > 0$, we design an algorithm for computing the$k$-sparse Walsh-Hadamard transform of an$N$-dimensional vector$x \in \mathbb{R}^N$in time$k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to$x$and computes a$k$-sparse$\tilde{x} \in \mathbb{R}^N$satisfying$\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>

TR15-148 | 9th September 2015
Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

#### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

We introduce the Nondeterministic Strong Exponential Time Hypothesis
(NSETH) as a natural extension of the Strong Exponential Time
Hypothesis (SETH). We show that both refuting and proving
NSETH would have interesting consequences.

In particular we show that disproving NSETH would ... more >>>

TR16-031 | 7th March 2016
Titus Dose

#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Revisions: 5

We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>>

TR16-067 | 20th April 2016
Balagopal Komarath, Jayalal Sarma, Saurabh Sawlani

#### Pebbling Meets Coloring : Reversible Pebble Game On Trees

The reversible pebble game is a combinatorial game played on rooted DAGs. This game was introduced by Bennett (1989) motivated by applications in designing space efficient reversible algorithms. Recently, Chan (2013) showed that the reversible pebble game number of any DAG is the same as its Dymond-Tompa pebble number and ... more >>>

TR16-108 | 16th July 2016
Michael Rudow

#### Discrete Logarithm and Minimum Circuit Size

This paper shows that the Discrete Logarithm Problem is in ZPP^(MCSP) (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPP^(MCSP) Allender et al. (2006). In doing so, this paper helps classify the relative difficulty of the Minimum ... more >>>

TR17-086 | 9th May 2017
C Ramya, Raghavendra Rao B V

#### Linear Projections of the Vandermonde Polynomial

Revisions: 1

An n-variate Vandermonde polynomial is the determinant of the n × n matrix where the ith column is the vector (1, x_i , x_i^2 , . . . , x_i^{n-1})^T. Vandermonde polynomials play a crucial role in the in the theory of alternating polynomials and occur in Lagrangian polynomial interpolation ... more >>>

TR18-055 | 26th March 2018
Titus Dose

#### Balance Problems for Integer Circuits

Revisions: 5

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits
computing finite sets of natural numbers. These problems naturally build on problems for integer
expressions and integer circuits studied by Stockmeyer and Meyer (1973),
McKenzie and Wagner (2007),
and Glaßer et al (2010).

Our work shows that the ... more >>>

TR21-132 | 11th September 2021
Eric Binnendyk

#### Pseudo-random functions and uniform learnability

Revisions: 1

Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate ... more >>>

ISSN 1433-8092 | Imprint