Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > 2004:
All reports in year 2004:
TR04-001 | 11th December 2003
Lance Fortnow, Russell Impagliazzo, Chris Umans

#### On the complexity of succinct zero-sum games

We study the complexity of solving succinct zero-sum games,
i.e., the
games whose payoff matrix $M$ is given implicitly by a Boolean circuit
$C$ such that $M(i,j)=C(i,j)$. We complement the known $\EXP$-hardness
of computing the \emph{exact} value of a succinct zero-sum game by
several results on \emph{approximating} the value. (1) ... more >>>

TR04-002 | 8th January 2004
Troy Lee, Dieter van Melkebeek, Harry Buhrman

#### Language Compression and Pseudorandom Generators

The language compression problem asks for succinct descriptions of
the strings in a language A such that the strings can be efficiently
recovered from their description when given a membership oracle for
A. We study randomized and nondeterministic decompression schemes
and investigate how close we can get to the information ... more >>>

TR04-003 | 22nd December 2003
Pascal Koiran

#### Valiant's model and the cost of computing integers

Let $\tau(k)$ be the minimum number of arithmetic operations
required to build the integer $k \in \N$ from the constant 1.
A sequence $x_k$ is said to be easy to compute'' if
there exists a polynomial $p$ such that $\tau(x_k) \leq p(\log k)$
for all $k \geq ... more >>> TR04-004 | 13th January 2004 Ramamohan Paturi, Pavel Pudlak #### Circuit lower bounds and linear codes In 1977 Valiant proposed a graph theoretical method for proving lower bounds on algebraic circuits with gates computing linear functions. He used this method to reduce the problem of proving lower bounds on circuits with linear gates to to proving lower bounds on the rigidity of a matrix, a ... more >>> TR04-005 | 19th January 2004 Stasys Jukna #### On Graph Complexity Revisions: 1 , Comments: 1 A boolean circuit$f(x_1,\ldots,x_n)$\emph{represents} a graph$G$on$n$vertices if for every input vector$a\in\{0,1\}^n$with precisely two$1$'s in, say, positions$i$and$j$,$f(a)=1$precisely when$i$and$j$are adjacent in$G$; on inputs with more or less than two ... more >>> TR04-006 | 6th January 2004 Günter Hotz #### A remark on nondecidabilities of the initial value problem of ODEs We prove that it is not decidable on R-machines if for a fixed finite intervall [a,b) the solution of the initial value problems of systems of ordinary differetial equations have solutions over this interval. This result holds independly from assumptions about differentiability of the right sides of the ODEs. Futhermore ... more >>> TR04-007 | 13th January 2004 Alan L. Selman, Samik Sengupta #### Polylogarithmic-round Interactive Proofs for coNP Collapses the Exponential Hierarchy Revisions: 1 , Comments: 1 It is known \cite{BHZ87} that if every language in coNP has a constant-round interactive proof system, then the polynomial hierarchy collapses. On the other hand, Lund {\em et al}.\ \cite{LFKN92} have shown that #SAT, the #P-complete function that outputs the number of satisfying assignments of a Boolean ... more >>> TR04-008 | 27th November 2003 Vikraman Arvind, Jacobo Toran #### Solvable Group Isomorphism is (almost) in NP\cap coNP The Group Isomorphism problem consists in deciding whether two input groups$G_1$and$G_2$given by their multiplication tables are isomorphic. We first give a 2-round Arthur-Merlin protocol for the Group Non-Isomorphism problem such that on input groups$(G_1,G_2)$of size$n$, Arthur uses ... more >>> TR04-009 | 22nd January 2004 Martin Dyer, Alan Frieze, Thomas P. Hayes, Eric Vigoda #### Randomly coloring constant degree graphs We study a simple Markov chain, known as the Glauber dynamics, for generating a random <i>k</i>-coloring of a <i>n</i>-vertex graph with maximum degree &Delta;. We prove that the dynamics converges to a random coloring after <i>O</i>(<i>n</i> log <i>n</i>) steps assuming <i>k</i> &ge; <i>k</i><sub>0</sub> for some absolute constant <i>k</i><sub>0</sub>, and either: ... more >>> TR04-010 | 26th January 2004 Michal Parnas, Dana Ron, Ronitt Rubinfeld #### Tolerant Property Testing and Distance Approximation A standard property testing algorithm is required to determine with high probability whether a given object has property P or whether it is \epsilon-far from having P, for any given distance parameter \epsilon. An object is said to be \epsilon-far from having ... more >>> TR04-011 | 16th January 2004 Christian Glaßer #### Counting with Counterfree Automata We study the power of balanced regular leaf-languages. First, we investigate (i) regular languages that are polylog-time reducible to languages in dot-depth 1/2 and (ii) regular languages that are polylog-time decidable. For both classes we provide - forbidden-pattern characterizations, and - characterizations in terms of regular expressions. Both ... more >>> TR04-012 | 19th December 2003 Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore #### The Resolution Complexity of Random Graph$k$-Colorability We consider the resolution proof complexity of propositional formulas which encode random instances of graph$k$-colorability. We obtain a tradeoff between the graph density and the resolution proof complexity. For random graphs with linearly many edges we obtain linear-exponential lower bounds on the length of resolution refutations. For any$\epsilon>0$, ... more >>> TR04-013 | 10th February 2004 Oded Goldreich, Dana Ron #### On Estimating the Average Degree of a Graph. Following Feige, we consider the problem of estimating the average degree of a graph. Using neighbor queries'' as well as degree queries'', we show that the average degree can be approximated arbitrarily well in sublinear time, unless the graph is extremely sparse (e.g., unless the graph has a sublinear ... more >>> TR04-014 | 26th November 2003 Chris Pollett #### Languages to diagonalize against advice classes Variants of Kannan's Theorem are given where the circuits of the original theorem are replaced by arbitrary recursively presentable classes of languages that use advice strings and satisfy certain mild conditions. These variants imply that$\DTIME(n^{k'})^{\NE}/n^k$does not contain$\PTIME^{\NE}$,$\DTIME(2^{n^{k'}})/n^k$does not contain$\EXP$,$\SPACE(n^{k'})/n^k$does not ... more >>> TR04-015 | 24th February 2004 Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet #### Enumerations of the Kolmogorov Function A recursive enumerator for a function$h$is an algorithm$f$which enumerates for an input$x$finitely many elements including$h(x)$.$f$is an$k(n)$-enumerator if for every input$x$of length$n$,$h(x)$is among the first$k(n)$elements enumerated by$f$. If there is a$k(n)$-enumerator for ... more >>> TR04-016 | 3rd March 2004 Michael Alekhnovich, Eli Ben-Sasson #### Linear Upper Bounds for Random Walk on Small Density Random 3CNFs We analyze the efficiency of the random walk algorithm on random 3CNF instances, and prove em linear upper bounds on the running time of this algorithm for small clause density, less than 1.63. Our upper bound matches the observed running time to within a multiplicative factor. This is the ... more >>> TR04-017 | 22nd February 2004 Evgeny Dantsin, Alexander Wolpert #### Derandomization of Schuler's Algorithm for SAT Recently Schuler \cite{Sch03} presented a randomized algorithm that solves SAT in expected time at most$2^{n(1-1/\log_2(2m))}$up to a polynomial factor, where$n$and$m$are, respectively, the number of variables and the number of clauses in the input formula. This bound is the best known ... more >>> TR04-018 | 24th January 2004 Jan Krajicek #### Diagonalization in proof complexity We study the diagonalization in the context of proof complexity. We prove that at least one of the following three conjectures is true: 1. There is a boolean function computable in E that has circuit complexity$2^{\Omega(n)}$. 2. NP is not closed under the complement. 3. There is no ... more >>> TR04-019 | 15th January 2004 Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta #### Properties of NP-Complete Sets We study several properties of sets that are complete for NP. We prove that if$L$is an NP-complete set and$S \not\supseteq L$is a p-selective sparse set, then$L - S$is many-one-hard for NP. We demonstrate existence of a sparse set$S \in \mathrm{DTIME}(2^{2^{n}})$such ... more >>> TR04-020 | 8th March 2004 Emanuele Viola #### The Complexity of Constructing Pseudorandom Generators from Hard Functions We study the complexity of building pseudorandom generators (PRGs) from hard functions. We show that, starting from a function f : {0,1}^l -> {0,1} that is mildly hard on average, i.e. every circuit of size 2^Omega(l) fails to compute f on at least a 1/poly(l) fraction of inputs, we can ... more >>> TR04-021 | 23rd March 2004 Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan #### Robust PCPs of Proximity, Shorter PCPs and Applications to Coding We continue the study of the trade-off between the length of PCPs and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size$n$): We present PCPs of length$\exp(\tildeO(\log\log n)^2)\cdot n$that can be verified by making$o(\log\log n)$Boolean queries. more >>> TR04-022 | 31st March 2004 Nayantara Bhatnagar, Parikshit Gopalan #### The Degree of Threshold Mod 6 and Diophantine Equations We continue the study of the degree of polynomials representing threshold functions modulo 6 initiated by Barrington, Beigel and Rudich. We use the framework established by the authors relating representations by symmetric polynomials to simultaneous protocols. We show that proving bounds on the degree of Threshold functions is equivalent to ... more >>> TR04-023 | 21st January 2004 Yaoyun Shi #### Quantum and Classical Tradeoffs We initiate the study of quantifying the quantumness of a quantum circuit by the number of gates that do not preserve the computational basis, as a means to understand the nature of quantum algorithmic speedups. Intuitively, a reduction in the quantumness requires an increase in the amount of classical computation, ... more >>> TR04-024 | 26th March 2004 Thomas Thierauf, Thanh Minh Hoang #### On Closure Properties of GapL Revisions: 1 , Comments: 1 We show necessary and sufficient conditions that certain algebraic functions like the rank or the signature of an integer matrix can be computed in GapL. more >>> TR04-025 | 24th January 2004 John Hitchcock, A. Pavan, Vinodchandran Variyam #### Partial Bi-Immunity and NP-Completeness The Turing and many-one completeness notions for$\NP$have been previously separated under {\em measure}, {\em genericity}, and {\em bi-immunity} hypotheses on NP. The proofs of all these results rely on the existence of a language in NP with almost everywhere hardness. In this paper we separate the same NP-completeness ... more >>> TR04-026 | 17th February 2004 Scott Aaronson #### Limitations of Quantum Advice and One-Way Communication Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP/qpoly is contained in ... more >>> TR04-027 | 20th February 2004 Henning Fernau #### Parametric Duality: Kernel Sizes and Algorithmics We derive the first lower bound results on kernel sizes of parameterized problems. The same idea also allows us to sometimes "de-parameterize" parameterized algorithms. more >>> TR04-028 | 19th March 2004 Arfst Nickelsen, Till Tantau, Lorenz Weizsäcker #### Aggregates with Component Size One Characterize Polynomial Space Aggregates are a computational model similar to circuits, but the underlying graph is not necessarily acyclic. Logspace-uniform polynomial-size aggregates decide exactly the languages in PSPACE; without uniformity condition they decide the languages in PSPACE/poly. As a measure of similarity to boolean circuits we introduce the parameter component size. We ... 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-030 | 9th March 2004 Nikolay Vereshchagin #### Kolmogorov complexity of enumerating finite sets Solovay has proven that the minimal length of a program enumerating a set A is upper bounded by 3 times the absolute value of the logarithm of the probability that a random program will enumerate A. It is unknown whether one can replace the constant 3 by a smaller constant. more >>> TR04-031 | 22nd March 2004 Troy Lee, Andrei Romashchenko #### On Polynomially Time Bounded Symmetry of Information The information contained in a string$x$about a string$y$is defined as the difference between the Kolmogorov complexity of$y$and the conditional Kolmogorov complexity of$y$given$x$, i.e.,$I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that$I(x:y)$is symmetric up to a small ... more >>> TR04-032 | 5th February 2004 Ryan Williams #### A new algorithm for optimal constraint satisfaction and its implications We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per constraint (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over the trivial algorithm; more precisely, it is a constant factor improvement in the base of ... more >>> TR04-033 | 23rd January 2004 Michael Schmitt #### On the sample complexity of learning for networks of spiking neurons with nonlinear synaptic interactions We study networks of spiking neurons that use the timing of pulses to encode information. Nonlinear interactions model the spatial groupings of synapses on the dendrites and describe the computations performed at local branches. We analyze the question of how many examples these networks must ... more >>> TR04-034 | 12th April 2004 April Rasala Lehman, Eric Lehman #### Network Coding: Does the Model Need Tuning? We consider the general network information flow problem, which was introduced by Ahlswede et. al. We show a periodicity effect: for every integer m greater than 1, there exists an instance of the network information flow problem that admits a solution if and only if the alphabet size is a ... more >>> TR04-035 | 10th April 2004 Scott Contini, Ernie Croot, Igor E. Shparlinski #### Complexity of Inverting the Euler Function We present an algorithm to invert the Euler function$\varphi(m)$. The algorithm, for a given integer$n\ge 1$, in polynomial time on average'', finds theset$\Psi(n)$of all solutions$m$to the equation$\varphi(m) =n$. In fact, in the worst case the set$\Psi(n)$is exponentially large and cannot be ... more >>> TR04-036 | 27th March 2004 Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis #### Exponential Separation of Quantum and Classical One-Way Communication Complexity We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>> TR04-037 | 14th April 2004 Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner #### Generation Problems Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f. For several subclasses of operations we prove tight upper and lower bounds for the ... more >>> TR04-038 | 27th April 2004 John Case, Sanjay Jain, Rüdiger Reischuk, Frank Stephan, Thomas Zeugmann #### A Polynomial Time Learner for a Subclass of Regular Patterns Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns$\pi$of the form$x_0 \alpha_1 x_1 ... \alpha_m x_m$for unknown$m$but known$c$, more >>> TR04-039 | 21st April 2004 Andrzej Lingas, Martin Wahlén #### On approximation of the maximum clique minor containment problem and some subgraph homeomorphism problems We consider the minor'' and homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest$h$such that the input graph has a minor isomorphic to$K_h$or a subgraph homeomorphic to$K_h,$respectively.We show the former to be approximable within$O(\sqrt {n} \log^{1.5} n)$by ... more >>> TR04-040 | 4th May 2004 Venkatesan Guruswami, Alexander Vardy #### Maximum-likelihood decoding of Reed-Solomon codes is NP-hard Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum- likelihood decoding remains hard for any specific family of more >>> TR04-041 | 18th May 2004 Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson #### Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... 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-043 | 20th May 2004
Luca Trevisan

#### Some Applications of Coding Theory in Computational Complexity

Error-correcting codes and related combinatorial constructs
play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey
results on locally-testable and locally-decodable error-correcting
codes, and their applications to complexity theory and to
cryptography.

Locally decodable codes are error-correcting codes ... more >>>

TR04-044 | 1st June 2004
Eric Allender, Harry Buhrman, Michal Koucky

#### What Can be Efficiently Reduced to the Kolmogorov-Random Strings?

We investigate the question of whether one can characterize complexity
classes (such as PSPACE or NEXP) in terms of efficient
reducibility to the set of Kolmogorov-random strings R_C.
We show that this question cannot be posed without explicitly dealing
with issues raised by the choice of universal
machine in the ... more >>>

TR04-045 | 15th April 2004
Hartmut Klauck, Robert Spalek, Ronald de Wolf

#### Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs

A strong direct product theorem says that if we want to compute
k independent instances of a function, using less than k times
the resources needed for one instance, then our overall success
probability will be exponentially small in k.
We establish such theorems for the classical as well as ... more >>>

TR04-046 | 4th June 2004

#### Robust Locally Testable Codes and Products of Codes

We continue the investigation of locally testable codes, i.e.,
error-correcting codes for whom membership of a given word in the
code can be tested probabilistically by examining it in very few
locations. We give two general results on local testability:
First, motivated by the recently proposed notion of robust
probabilistically ... 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-048 | 21st April 2004
André Lanka, Andreas Goerdt

#### An approximation hardness result for bipartite Clique

Assuming 3-SAT formulas are hard to refute
on average, Feige showed some approximation hardness
results for several problems like min bisection, dense
$k$-subgraph, max bipartite clique and the 2-catalog segmentation
problem. We show a similar result for
max bipartite clique, but under the assumption, 4-SAT formulas
are hard to refute ... more >>>

TR04-049 | 15th June 2004
Piotr Berman, Marek Karpinski, Yakov Nekrich

#### Optimal Trade-Off for Merkle Tree Traversal

We prove upper and lower bounds for computing Merkle tree
traversals, and display optimal trade-offs between time
and space complexity of that problem.

more >>>

TR04-050 | 13th June 2004
Michelle Effros, Leonard Schulman

#### Deterministic clustering with data nets

We consider the $K$-clustering problem with the $\ell_2^2$
distortion measure, also known as the problem of optimal
fixed-rate vector quantizer design. We provide a deterministic
approximation algorithm which works for all dimensions $d$ and
which, given a data set of size $n$, computes in time
more >>>

TR04-051 | 10th June 2004
Zdenek Dvorák, Daniel Král, Ondrej Pangrác

#### Locally consistent constraint satisfaction problems

An instance of a constraint satisfaction problem is $l$-consistent
if any $l$ constraints of it can be simultaneously satisfied.
For a set $\Pi$ of constraint types, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the ... more >>>

TR04-052 | 14th June 2004
Michael Ben Or, Don Coppersmith, Michael Luby, Ronitt Rubinfeld

#### Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

In this paper, we study two questions related to
the problem of testing whether a function is close to a homomorphism.
For two finite groups $G,H$ (not necessarily Abelian),
an arbitrary map $f:G \rightarrow H$, and a parameter $0 < \epsilon <1$,
say that $f$ is $\epsilon$-close to a homomorphism ... more >>>

TR04-053 | 17th June 2004
A. Pavan, Vinodchandran Variyam

#### Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine
and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.

more >>>

TR04-054 | 5th June 2004
Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

#### Non-reducible descriptions for conditional Kolmogorov complexity

Let a program p on input a output b. We are looking for a
shorter program p' having the same property (p'(a)=b). In
addition, we want p' to be simple conditional to p (this
means that the conditional Kolmogorov complexity K(p'|p) is
negligible). In the present paper, we prove that ... 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-056 | 1st July 2004
Vinodchandran Variyam

#### A note on the circuit complexity of PP

In this short note we show that for any integer k, there are
languages in the complexity class PP that do not have Boolean
circuits of size $n^k$.

more >>>

TR04-057 | 16th May 2004
Monica del Pilar Canales Chacon, Michael Johannes Vielhaber

#### Structural and Computational Complexity of Isometries and their Shift Commutators

{\bf Abstract}

Isometries on formal power series over the finite field $\ff_2$
or on $2$--adic integers can be
computed by invertible transducers on inputs from $\{0,1\}^\infty$.
We consider the structural complexity of an isometry $f$,
measured as {\it tree complexity} $T(f,h)$, $h$ the tree height
[H.~Niederreiter, M.~Vielhaber, {\it J.~Cpx.}, ... more >>>

TR04-058 | 28th May 2004
John Case, Sanjay Jain, Eric Martin, Arun Sharma, Frank Stephan

#### Identifying Clusters from Positive Data

The present work studies clustering from an abstract point of view
and investigates its properties in the framework of inductive inference.
Any class $S$ considered is given by a numbering
$A_0,A_1,...$ of nonempty subsets of the natural numbers
or the rational k-dimensional vector space as a hypothesis space.
A clustering ... 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-060 | 22nd July 2004

#### Simple PCPs with Poly-log Rate and Query Complexity

We give constructions of PCPs of length n*polylog(n) (with respect
to circuits of size n) that can be verified by making polylog(n)
queries to bits of the proof. These PCPs are not only shorter than
previous ones, but also simpler. Our (only) building blocks are
Reed-Solomon codes and the bivariate ... more >>>

TR04-061 | 30th June 2004
Scott Aaronson

#### The Complexity of Agreement

A celebrated 1976 theorem of Aumann asserts that honest, rational
Bayesian agents with common priors will never "agree to disagree": if
their opinions about any topic are common knowledge, then those
opinions must be equal. Economists have written numerous papers
examining the assumptions behind this theorem. But two key questions
more >>>

TR04-062 | 28th July 2004
Stasys Jukna

#### A note on the P versus NP intersected with co-NP question in communication complexity

We consider the P versus NP\cap coNP question for the classical two-party communication protocols: if both a boolean function and its negation have small nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition case this question was answered by Aho, Ullman and ... more >>>

TR04-063 | 23rd July 2004
Yehuda Lindell, Benny Pinkas

#### A Proof of Yao's Protocol for Secure Two-Party Computation

Revisions: 1

In the mid 1980's, Yao presented a constant-round protocol for
securely computing any two-party functionality in the presence of
semi-honest adversaries (FOCS 1986). In this paper, we provide a
complete description of Yao's protocol, along with a rigorous
proof of security. Despite the importance of Yao's protocol to the
field ... more >>>

TR04-064 | 25th June 2004
Piotr Faliszewski

#### Exponential time reductions and sparse languages in NEXP

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>

TR04-065 | 28th July 2004
Luca Trevisan

#### Inapproximability of Combinatorial Optimization Problems

Revisions: 1

We survey results on the hardness of approximating combinatorial
optimization problems.

more >>>

TR04-066 | 6th July 2004
Tomoyuki Yamakami, Toshio Suzuki

#### Resource Bounded Immunity and Simplicity

Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we ... more >>>

TR04-067 | 20th July 2004
hadi salmasian, ravindran kannan, Santosh Vempala

#### The Spectral Method for Mixture Models

We present an algorithm for learning a mixture of distributions.
The algorithm is based on spectral projection and
is efficient when the components of the mixture are logconcave
distributions.

more >>>

TR04-068 | 13th August 2004
Nir Ailon, Bernard Chazelle

#### Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

TR04-069 | 13th August 2004
Eran Rom, Amnon Ta-Shma

#### Improving the alphabet size in high noise, almost optimal rate list decodable codes

Revisions: 2

In this note we revisit the construction of high noise, almost
optimal rate list decodable code of Guruswami ("Better extractors for better codes?")
Guruswami showed that based on optimal extractors one can build a
$(1-\epsilon,O({1 \over \epsilon}))$ list decodable codes of rate
$\Omega({\epsilon \over {log{1 \over \epsilon}}})$ and alphabet
size ... more >>>

TR04-070 | 22nd June 2004
Leonid Gurvits

#### Combinatorial and algorithmic aspects of hyperbolic polynomials

Let $p(x_1,...,x_n) =\sum_{ (r_1,...,r_n) \in I_{n,n} } a_{(r_1,...,r_n) } \prod_{1 \leq i \leq n} x_{i}^{r_{i}}$
be homogeneous polynomial of degree $n$ in $n$ real variables with integer nonnegative coefficients.
The support of such polynomial $p(x_1,...,x_n)$
is defined as $supp(p) = \{(r_1,...,r_n) \in I_{n,n} : a_{(r_1,...,r_n)} \neq 0 ... more >>> TR04-071 | 11th August 2004 Marcus Schaefer, Stephen A. Fenner #### Simplicity and Strong Reductions A set is called NP-simple if it lies in NP, and its complement is infinite, and does not contain any infinite subsets in NP. Hartmanis, Li and Yesha proved that no set which is hard for NP under many-one (Karp) reductions is NP-simple unless the intersection of NP and coNP ... more >>> TR04-072 | 19th August 2004 John Hitchcock #### Hausdorff Dimension and Oracle Constructions Bennett and Gill (1981) proved that P^A != NP^A relative to a random oracle A, or in other words, that the set O_[P=NP] = { A | P^A = NP^A } has Lebesgue measure 0. In contrast, we show that O_[P=NP] has Hausdorff dimension 1. ... more >>> TR04-073 | 9th July 2004 Henning Fernau #### A Top-Down Approach to Search-Trees: Improved Algorithmics for 3-Hitting Set In this paper, we show how to systematically improve on parameterized algorithms and their analysis, focusing on search-tree based algorithms for d-Hitting Set, especially for d=3. We concentrate on algorithms which are easy to implement, in contrast with the highly sophisticated algorithms which have been elsewhere designed to ... more >>> TR04-074 | 26th August 2004 Emanuele Viola #### On Parallel Pseudorandom Generators Revisions: 1 We study pseudorandom generator (PRG) constructions$G^f : {0,1}^l \to {0,1}^{l+s}$from one-way functions$f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form$G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$where$C$is a polynomial-size constant depth circuit and$C$and the$q$'s are generated from$x$arbitrarily. more >>> TR04-075 | 21st July 2004 Michael Schmitt #### Some dichotomy theorems for neural learning problems The computational complexity of learning from binary examples is investigated for linear threshold neurons. We introduce combinatorial measures that create classes of infinitely many learning problems with sample restrictions. We analyze how the complexity of these problems depends on the values for the measures. ... more >>> TR04-076 | 17th September 2004 Oliver Giel, Ingo Wegener #### Searching Randomly for Maximum Matchings Many real-world optimization problems in, e.g., engineering or biology have the property that not much is known about the function to be optimized. This excludes the application of problem-specific algorithms. Simple randomized search heuristics are then used with surprisingly good results. In order to understand the working principles behind such more >>> TR04-077 | 17th July 2004 Alina Beygelzimer, Varsha Dani, Tom Hayes, John Langford #### Reductions Between Classification Tasks There are two approaches to solving a new supervised learning task: either analyze the task independently or reduce it to a task that has already been thoroughly analyzed. This paper investigates the latter approach for classification problems. In addition to obvious theoretical motivations, there is fairly strong empirical evidence that ... more >>> TR04-078 | 3rd August 2004 Henning Fernau #### Two-Layer Planarization: Improving on Parameterized Algorithmics A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that there are no edge crossings when edges are drawn as straight-line segments. We study two variants of biplanarization problems: - Two-Layer Planarization TLP: can$k$edges be deleted from a ... more >>> TR04-079 | 30th August 2004 John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn #### The Arithmetical Complexity of Dimension and Randomness Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1]. Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>> TR04-080 | 7th September 2004 Lance Fortnow, Troy Lee, Nikolay Vereshchagin #### Kolmogorov Complexity with Error We introduce the study of Kolmogorov complexity with error. For a metric d, we define C_a(x) to be the length of a shortest program p which prints a string y such that d(x,y) \le a. We also study a conditional version of this measure C_{a,b}(x|y) where the task is, given ... more >>> TR04-081 | 9th September 2004 Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin #### Increasing Kolmogorov Complexity How much do we have to change a string to increase its Kolmogorov complexity. We show that we can increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings require Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ... more >>> TR04-082 | 9th September 2004 Olaf Beyersdorff #### Representable Disjoint NP-Pairs Revisions: 1 We investigate the class of disjoint NP-pairs under different reductions. The structure of this class is intimately linked to the simulation order of propositional proof systems, and we make use of the relationship between propositional proof systems and theories of bounded arithmetic as the main tool of our analysis. more >>> TR04-083 | 8th September 2004 Boaz Barak, Yehuda Lindell, Salil Vadhan #### Lower Bounds for Non-Black-Box Zero Knowledge We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions: <ol> <li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>> TR04-084 | 28th September 2004 George Karakostas #### A better approximation ratio for the Vertex Cover problem We reduce the approximation factor for Vertex Cover to$2-\Theta(1/\sqrt{logn})$(instead of the previous$2-\Theta(loglogn/logn})$, obtained by Bar-Yehuda and Even, and by Monien and Speckenmeyer in 1985. The improvement of the vanishing factor comes as an application of the recent results of Arora, Rao, and Vazirani that improved ... more >>> TR04-085 | 3rd October 2004 Erez Petrank, Guy Rothblum #### Selection from Structured Data Sets A large body of work studies the complexity of selecting the$j$-th largest element in an arbitrary set of$n$elements (a.k.a. the select$(j)$operation). In this work, we study the complexity of select in data that is partially structured by an initial preprocessing stage and in a data structure ... more >>> TR04-086 | 12th October 2004 Ronen Shaltiel, Chris Umans #### Pseudorandomness for Approximate Counting and Sampling We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions. Our main technical contribution allows one to boost'' a given hardness assumption. One special ... more >>> TR04-087 | 13th October 2004 Alexander Healy, Salil Vadhan, Emanuele Viola #### Using Nondeterminism to Amplify Hardness We revisit the problem of hardness amplification in$\NP$, as recently studied by O'Donnell (STOC `02). We prove that if$\NP$has a balanced function$f$such that any circuit of size$s(n)$fails to compute$f$on a$1/\poly(n)$fraction of inputs, then$\NP$has a function$f'$such ... more >>> TR04-088 | 12th October 2004 Emanuele Viola, Dan Gutfreund #### Fooling Parity Tests with Parity Gates We study the complexity of computing$k$-wise independent and$\epsilon$-biased generators$G : \{0,1\}^n \to \{0,1\}^m$. Specifically, we refer to the complexity of computing$G$\emph{explicitly}, i.e. given$x \in \{0,1\}^n$and$i \in \{0,1\}^{\log m}$, computing the$i$-th output bit of$G(x)$. Mansour, Nisan and Tiwari (1990) show that ... more >>> TR04-089 | 26th October 2004 Ingo Wegener #### Simulated Annealing Beats Metropolis in Combinatorial Optimization The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>> TR04-090 | 3rd November 2004 Kazuyuki Amano, Akira Maruoka #### Better Simulation of Exponential Threshold Weights by Polynomial Weights We give an explicit construction of depth two threshold circuit with polynomial weights and$\tilde{O}(n^5)$gates that computes an arbitrary threshold function. We also give the construction of such circuits with$O(n^3/\log n)$gates computing the COMPARISON and CARRY functions, and that with$O(n^4/\log n)$gates computing the ADDITION function. ... more >>> TR04-091 | 29th September 2004 Ondrej Klíma, Pascal Tesson, Denis Thérien #### Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups We consider the problem of testing whether a given system of equations over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgroups more >>> TR04-092 | 3rd November 2004 Oded Lachish, Ilan Newman #### Testing Periodicity A string$\alpha\in\Sigma^n$is called {\it p-periodic}, if for every$i,j \in \{1,\dots,n\}$, such that$i\equiv j \bmod p$,$\alpha_i = \alpha_{j}$, where$\alpha_i$is the$i$-th place of$\alpha$. A string$\alpha\in\Sigma^n$is said to be$period(\leq g)$, if there exists$p\in \{1,\dots,g\}$such that$\alpha$... more >>> TR04-093 | 9th November 2004 Oded Goldreich, Madhu Sudan, Luca Trevisan #### From logarithmic advice to single-bit advice Building on Barak's work (Random'02), Fortnow and Santhanam (FOCS'04) proved a time hierarchy for probabilistic machines with one bit of advice. Their argument is based on an implicit translation technique, which allow to translate separation results for short (say logarithmic) advice (as shown by Barak) into separations for ... more >>> TR04-094 | 10th November 2004 Omer Reingold #### Undirected ST-Connectivity in Log-Space We present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. The previous bound on the space complexity of undirected st-connectivity was log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and Zhou. As undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class SL), ... more >>> TR04-095 | 3rd November 2004 Daniele Micciancio #### Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given$m$(random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 ... more >>> TR04-096 | 4th November 2004 Eldar Fischer, Frederic Magniez, Michel de Rougemont #### Property and Equivalence Testing on Strings Revisions: 1 Using a new statistical embedding of words which has similarities with the Parikh mapping, we first construct a tolerant tester for the equality of two words, whose complexity is independent of the string size, where the distance between inputs is measured by the normalized edit distance with moves. As a ... more >>> TR04-097 | 2nd November 2004 Víctor Dalmau #### Malt'sev Constraints made Simple We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints. more >>> TR04-098 | 5th November 2004 Lance Fortnow, Rahul Santhanam, Luca Trevisan #### Promise Hierarchies We show that for any constant a, ZPP/b(n) strictly contains ZPTIME(n^a)/b(n) for some b(n) = O(log n log log n). Our techniques are very general and give the same hierarchy for all the common promise time classes including RTIME, NTIME \cap coNTIME, UTIME, MATIME, AMTIME and BQTIME. We show a ... more >>> TR04-099 | 11th November 2004 Ran Raz #### Extractors with Weak Random Seeds We show how to extract random bits from two or more independent weak random sources, in cases where only one source is of linear min-entropy and all other sources are of logarithmic min-entropy. We also give improved constructions of mergers and condensers. In all that comes below,$\delta$is an ... more >>> TR04-100 | 23rd November 2004 Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer #### The Complexity of Satisfiability Problems: Refining Schaefer's Theorem Revisions: 1 Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>> TR04-101 | 28th September 2004 Miroslav Chlebík, Janka Chlebíková #### Crown reductions for the Minimum Weighted Vertex Cover problem TR04-102 | 20th October 2004 Thomas Holenstein #### Key Agreement from Weak Bit Agreement Assume that Alice and Bob, given an authentic channel, have a protocol where they end up with a bit S_A and S_B, respectively, such that with probability (1+eps)/2 these bits are equal. Further assume that conditioned on the event S_A = S_B no polynomial time bounded algorithm can predict the ... more >>> TR04-103 | 19th November 2004 Lance Fortnow, Adam Klivans #### NP with Small Advice We prove a new equivalence between the non-uniform and uniform complexity of exponential time. We show that EXP in NP/log if and only if EXP = P^NP|| (polynomial time with non-adaptive queries to SAT). Our equivalence makes use of a recent result due to Shaltiel and Umans showing EXP in ... more >>> TR04-104 | 19th November 2004 Maria Lopez-Valdes, Mayordomo Elvira #### Dimension is compression Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes. Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous ... more >>> TR04-105 | 19th November 2004 Eldar Fischer, Lance Fortnow #### Tolerant Versus Intolerant Testing for Boolean Properties A property tester with high probability accepts inputs satisfying a given property and rejects inputs that are far from satisfying it. A tolerant property tester, as defined by Parnas, Ron and Rubinfeld, must also accept inputs that are close enough to satisfying the property. We construct properties of binary functions ... more >>> TR04-106 | 19th November 2004 Christian Glaßer, Alan L. Selman, Liyu Zhang #### Canonical Disjoint NP-Pairs of Propositional Proof Systems We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ... more >>> TR04-107 | 24th November 2004 Ingo Wegener, Philipp Woelfel #### New Results on the Complexity of the Middle Bit of Multiplication Revisions: 1 It is well known that the hardest bit of integer multiplication is the middle bit, i.e. MUL_{n-1,n}. This paper contains several new results on its complexity. First, the size s of randomized read-k branching programs, or, equivalently, its space (log s) is investigated. A randomized algorithm for MUL_{n-1,n} with k=O(log ... more >>> TR04-108 | 24th November 2004 Eric Allender, Samir Datta, Sambuddha Roy #### Topology inside NC^1 We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of ... more >>> TR04-109 | 15th November 2004 Neeraj Kayal, Nitin Saxena #### On the Ring Isomorphism & Automorphism Problems We study the complexity of the isomorphism and automorphism problems for finite rings with unity. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of rings. The problem is shown to be in the complexity class$\AM \cap co\AM$and hence ... more >>> TR04-110 | 24th November 2004 Tomoyuki Yamakami, Harumichi Nishimura #### An Application of Quantum Finite Automata to Interactive Proof Systems Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer with finite-dimensional quantum memory space. This paper seeks their direct application to interactive proof systems in which a mighty quantum prover communicates with a ... 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-112 | 26th November 2004 Neil Thapen, Nicola Galesi #### Resolution and pebbling games We define a collection of Prover-Delayer games that characterize certain subsystems of resolution. This allows us to give some natural criteria which guarantee lower bounds on the resolution width of a formula, and to extend these results to formulas of unbounded initial width. We also use games to give upper ... more >>> TR04-113 | 19th November 2004 Mårten Trolin #### Lattices with Many Cycles Are Dense We give a method for approximating any$n$-dimensional lattice with a lattice$\Lambda$whose factor group$\mathbb{Z}^n / \Lambda$has$n-1$cycles of equal length with arbitrary precision. We also show that a direct consequence of this is that the Shortest Vector Problem and the Closest Vector Problem cannot ... more >>> TR04-114 | 21st November 2004 Vladimir Trifonov #### An O(log n log log n) Space Algorithm for Undirected s,t-Connectivity We present a deterministic O(log n log log n) space algorithm for undirected s,t-connectivity. It is based on the deterministic EREW algorithm of Chong and Lam (SODA 93) and uses the universal exploration sequences for trees constructed by Kouck\'y (CCC 01). Our result improves the O(log^{4/3} n) bound of Armoni ... more >>> TR04-115 | 1st December 2004 Iftach Haitner, Ronen Shaltiel #### Statistical Zero-Knowledge Arguments for NP Using Approximable-Preimage-Size One-Way Functions A statistical zero knowledge argument for NP is a cryptographic primitive that allows a polynomial-time prover to convince another polynomial-time verifier of the validity of an NP statement. It is guaranteed that even an infinitely powerful verifier does not learn any additional information but the validity of the claim. Naor ... more >>> TR04-116 | 18th November 2004 PERRET ludovic #### On the computational complexity of some equivalence problems of polynomial systems of equations over finite fields We study in this paper the computational complexity of some equivalence relations on polynomial systems of equations over finite fields. These problems are analyzed with respect to polynomial-time many-one reductions (resp. Turing reductions, Levin reductions). In particular, we show that some of these problems are between ... more >>> TR04-117 | 1st December 2004 Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis #### Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy Lovasz and Schrijver described a generic method of tightening the LP and SDP relaxation for any 0-1 optimization problem. These tightened relaxations were the basis of several celebrated approximation algorithms (such as for MAX-CUT, MAX-3SAT, and SPARSEST CUT). We prove strong nonapproximability results in this model for well-known problems such ... more >>> TR04-118 | 21st December 2004 Marek Karpinski, Yakov Nekrich #### A Note on Traversing Skew Merkle Trees We consider the problem of traversing skew (unbalanced) Merkle trees and design an algorithm for traversing a skew Merkle tree in time O(log n/log t) and space O(log n (t/log t)), for any choice of parameter t\geq 2. This algorithm can be of special interest in situations when 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 >>> TR04-120 | 22nd November 2004 Andris Ambainis, William Gasarch, Aravind Srinivasan, Andrey Utis #### Lower bounds on the Deterministic and Quantum Communication Complexity of HAM_n^a Alice and Bob want to know if two strings of length$n$are almost equal. That is, do they differ on at most$a$bits? Let$0\le a\le n-1$. We show that any deterministic protocol, as well as any error-free quantum protocol ($C^*$version), for this problem requires at ... more >>> TR04-121 | 7th December 2004 Vikraman Arvind, Piyush Kurur, T.C. Vijayaraghavan #### Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy. In this paper we study the complexity of Bounded Color Multiplicity Graph Isomorphism (BCGI): the input is a pair of vertex-colored graphs such that the number of vertices of a given color in an input graph is bounded by$b\$. We show that BCGI is in the
#L hierarchy ... more >>>

ISSN 1433-8092 | Imprint