In this paper, we build on the idea of Valiant \cite{Val79a} and
Ben-Dor/Halevi \cite{Ben93}, that is, to count the number of satisfying
solutions of a boolean formula via computing the permanent of a specially
constructed matrix. We show that the Desnanot-Jacobi identity ($\dji$) prevents
Valiant's original approach to achieve a parsimonious reduction to the
permanent over a field of characteristic two.

Given a DNF formula on n variables, the two natural size measures are the
number of terms or size s(f), and the maximum width of a term w(f). It is
folklore that short DNF formulas can be made narrow. We prove a converse,
showing that narrow formulas can be sparsified. More precisely, any width w DNF
irrespective of its size can be $\epsilon$-approximated by a width $w$ DNF with
at most $(w\log(1/\epsilon))^{O(w)}$ terms.

Chang's lemma is a useful tool in additive combinatorics and the analysis of
Boolean functions. Here we give an elementary proof using entropy. The constant
we obtain is tight, and we give a slight improvement in the case where the
variables are highly biased.

For fixed compact connected Lie groups H \subseteq G, we provide a polynomial
time algorithm to compute the multiplicity of a given irreducible
representation of H in the restriction of an irreducible representation of G.
Our algorithm is based on a finite difference formula which makes the
multiplicities amenable to Barvinok's algorithm for counting integral points in
polytopes.

We prove new lower bounds on the encoding length of Matching Vector (MV)
codes. These recently discovered families of Locally Decodable Codes (LDCs)
originate in the works of Yekhanin (JACM 2008) and Efremenko (STOC 2009) and
are the only known families of LDCs with a constant number of queries and
sub-exponential encoding length. The systematic study of these codes, and their
limitations, was initiated by Dvir et al (SIAM J. Comp. 2011) where
quasi-linear lower bounds were proved on their encoding length. Our work makes
another step in this direction by proving two new lower.

We analyze the computational complexity of solving the three "temporal rift"
puzzles in the recent popular video game Final Fantasy XIII-2. We show that the
Tile Trial puzzle is NP-hard and we provide an efficient algorithm for solving
the Crystal Bonds puzzle. We also show that slight generalizations of the
Crystal Bonds and Hands of Time puzzles are NP-hard.

Partitioning the vertices of a graph into two roughly equal parts while
minimizing the number of edges crossing the cut is a fundamental problem
(called Balanced Separator) that arises in many settings. For this problem, and
variants such as the Uniform Sparsest Cut problem where the goal is to minimize
the fraction of pairs on opposite sides of the cut that are connected by an
edge, there are large gaps between the known approximation algorithms and
non-approximability results. While no constant factor approximation algorithms
are known, even APX-hardness is not known either.

We study the complexity of computing the sign of the Tutte polynomial of a
graph. As there are only three possible outcomes (positive, negative, and
zero), this seems at first sight more like a decision problem than a counting
problem. Surprisingly, however, there are large regions of the parameter space
for which computing the sign of the Tutte polynomial is actually #P-hard.

We propose a new order, the small polynomial path order (sPOP* for short).
The order sPOP* provides a characterisation of the class of polynomial time
computable function via term rewrite systems. Any polynomial time computable
function gives rise to a rewrite system that is compatible with sPOP*. On the
other hand any function defined by a rewrite system compatible with sPOP* is
polynomial time computable. Technically sPOP* is a tamed recursive path order
with product status.

This paper is an experimental exploration of the relationship between the
runtimes of Turing machines and the length of proofs in formal axiomatic
systems. We compare the number of halting Turing machines of a given size to
the number of provable theorems of first-order logic of a given size, and the
runtime of the longest-running Turing machine of a given size to the proof
length of the most-difficult-to-prove theorem of a given size.

Computing supertrees is a central problem in phylogenetics. The supertree
method that is by far the most widely used today was introduced in 1992 and is
called Matrix Representation with Parsimony analysis (MRP). Matrix
Representation using Flipping (MRF)}, which was introduced in 2002, is an
interesting variant of MRP: MRF is arguably more relevant that MRP and various
efficient implementations of MRF have been presented. From a theoretical point
of view, implementing MRF or MRP is solving NP-hard optimization problems.

We study the problem of matrix Lie algebra conjugacy. Lie algebras arise
centrally in areas as diverse as differential equations, particle physics,
group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A
matrix Lie algebra is a set L of matrices such that $A, B\in L$ implies $AB -
BA \in L$. Two matrix Lie algebras are conjugate if there is an invertible
matrix $M$ such that $L_1 = M L_2 M^{-1}$.

One approach to confronting computational hardness is to try to understand
the contribution of various parameters to the running time of algorithms and
the complexity of computational tasks. Almost no computational tasks in real
life are specified by their size alone. It is not hard to imagine that some
parameters contribute more intractability than others and it seems reasonable
to develop a theory of computational complexity which seeks to exploit this
fact. Such a theory should be able to address the needs of practicioners in
algorithmics.

I will discuss the recent proof that the complexity class NEXP
(nondeterministic exponential time) lacks nonuniform ACC circuits of polynomial
size. The proof will be described from the perspective of someone trying to
discover it.

We study the problem of obtaining efficient, deterministic, black-box
polynomial identity testing algorithms for depth-3 set-multilinear circuits
(over arbitrary fields). This class of circuits has an efficient,
deterministic, white-box polynomial identity testing algorithm (due to Raz and
Shpilka), but has no known such black-box algorithm. We recast this problem as
a question of finding a low-dimensional subspace H, spanned by rank 1 tensors,
such that any non-zero tensor in the dual space ker(H) has high rank.

The problem MaxLin2 can be stated as follows. We are given a system $S$ of
$m$ equations in variables $x_1,...,x_n$, where each equation is $\sum_{i \in
I_j}x_i = b_j$ is assigned a positive integral weight $w_j$ and $x_i,b_j \in
\mathbb{F}_2$, $I_j \subseteq \{1,2,...,n\}$ for $j=1,...,m$. We are required
to find an assignment of values to the variables in order to maximize the total
weight of the satisfied equations.

In the context of statistical physics, Chandrasekharan and Wiese recently
introduced the \emph{fermionant} $\Ferm_k$, a determinant-like quantity where
each permutation $\pi$ is weighted by $-k$ raised to the number of cycles in
$\pi$. We show that computing $\Ferm_k$ is #P-hard under Turing reductions for
any constant $k > 2$, and is $\oplusP$-hard for $k=2$, even for the adjacency
matrices of planar graphs.

The two somewhat conflicting requirements of efficiency and fairness make
ATFM an unsatisfactorily solved problem, despite its overwhelming importance.
In this paper, we present an economics motivated solution that is based on the
notion of a free market. Our contention is that in fact the airlines themselves
are the best judge of how to achieve efficiency and our market-based solution
gives them the ability to pay, at the going rate, to buy away the desired
amount of delay on a per flight basis.

We investigate the computational complexity of the empire colouring problem
(as defined by Percy Heawood in 1890) for maps containing empires formed by
exactly $r > 1$ countries each. We prove that the problem can be solved in
polynomial time using $s$ colours on maps whose underlying adjacency graph has
no induced subgraph of average degree larger than $s/r$.

It is discussed and surveyed a numerical method proposed before, that
alternative to the usual compression method, provides an approximation to the
algorithmic (Kolmogorov) complexity, particularly useful for short strings for
which compression methods simply fail. The method shows to be stable enough and
useful to conceive and compare patterns in an algorithmic models. (article in
Spanish)

We investigate the complexity of bit counting algorithms in different sets of
instructions.

We introduce an idea called anti-gadgets in complexity reductions. These
combinatorial gadgets have the effect of erasing the presence of some other
graph fragment, as if we had managed to include a negative copy of a graph
gadget.

This work considers computationally efficient privacy-preserving data
release. We study the task of analyzing a database containing sensitive
information about individual participants. Given a set of statistical queries
on the data, we want to release approximate answers to the queries while also
guaranteeing differential privacy---protecting each participant's sensitive
data.

In this paper, we present a more simpler, direct and elegant approach to the
equivalence problem for {\em measure many one-way quantum finite automata}
(MM-1QFAs, for short). The method used in present work essentially generalize
from the work of J.W.Carlyle [{\em J.Math.Anal.Appl., 7 (1963) 167-175}],
namely, reducing the equivalence problem for MM-1QFAs to the equivalence
problem for two initial vectors.

The Gr\"obner basis detection (GBD) is defined as follows: Given a set of
polynomials, decide whether there exists -and if "yes" find- a term order such
that the set of polynomials is a Gr\"obner basis. This problem was shown to be
NP-hard by Sturmfels and Wiegelmann. We show that GBD when studied in the
context of zero dimensional ideals is also NP-hard. An algorithm to solve GBD
for zero dimensional ideals is also proposed which runs in polynomial time if
the number of indeterminates is a constant.

"What can be learned about from the sole fact that I have been shown this
on-line advertisement?" By definition, the answer to this question is
non-trivial whenever advertisements are not served indiscriminately.
Advertisers, hoping to have targeted precisely and appropriately, use
information from multiple sources to give different on-line experiences to
different people. Thus the message of "giving you the ads that interest you"
does not tell the whole story of behavioral targeting, and the resulting
differentiation in user experience may, or may not, work to the advantage of
the user.

We consider the following problem that arises in outsourced storage: a user
stores her data $x$ on a remote server but wants to audit the server at some
later point to make sure it actually did store $x$. The goal is to design a
(randomized) verification protocol that has the property that if the server
passes the verification with some reasonably high probability then the user can
rest assured that the server is storing $x$.

This paper studies the computational complexity of the Edge Packing problem
and the Vertex Packing problem. The edge packing problem (denoted by
$\bar{EDS}$) and the vertex packing problem (denoted by $\bar{DS} $) are linear
programming duals of the edge dominating set problem and the dominating set
problem respectively. It is shown that these two problems are equivalent to the
set packing problem with respect to hardness of approximation and parametric
complexity.

The aim of this paper is to undertake an experimental investigation of the
trade-offs between program-size and time computational complexity. The
investigation includes an exhaustive exploration and systematic study of the
functions computed by the set of all 2-color Turing machines with 2, 3 and 4
states--denoted by (n,2) with n the number of states--with particular attention
to the runtimes and space usages when the machines have access to larger
resources (more states).

We present a (full) derandomization of HSSW algorithm for 3-SAT, proposed by
Hofmeister, Sch\"oning, Schuler, and Watanabe in [STACS'02]. Thereby, we obtain
an O(1.3303^n)-time deterministic algorithm for 3-SAT, which is currently
fastest.

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.

A general theory of resource-bounded measurability and measure is developed.
Starting from any feasible probability measure $\nu$ on the Cantor space $\C$
and any suitable complexity class $C \subseteq \C$, the theory identifies the
subsets of $\C$ that are $\nu$-measurable in $C$ and assigns measures to these
sets, thereby endowing $C$ with internal measure-theoretic structure.

In this note, we show that quantum finite automata can be polynomially more
succinct than their classical counterparts for promise problems in case of
exact computation. Additionally, in terms of language recognition, the same
result is shown to be valid up to a constant factor depending on how bigger the
size of the alphabet is.

We investigate the complexity of the model checking problem for propositional
intuitionistic logic. We show that the model checking problem for
intuitionistic logic with one variable is complete for logspace-uniform AC1,
and for intuitionistic logic with two variables it is P-complete. For
superintuitionistic logics with one variable, we obtain NC1-completeness for
the model checking problem and for the tautology problem.

We prove that q-ary sparse codes with small bias are self-correctable and
locally testable. We generalize a result of Kaufman and Sudan that proves the
local testability and correctability of binary sparse codes with small bias. We
use properties of q-ary Krawtchouk polynomials and the McWilliams identity
-that relates the weight distribution of a code to the weight distribution of
its dual- to derive bounds on the error probability of the randomized tester
and self-corrector we are analyzing.

We show that any $O_d(\epsilon^{-4d 7^d})$-independent family of Gaussians
$\epsilon$-fools any degree-$d$ polynomial threshold function.

Border basis detection (BBD) is described as follows: given a set of
generators of an ideal, decide whether that set of generators is a border basis
of the ideal with respect to some order ideal. The motivation for this problem
comes from a similar problem related to Gr\"obner bases termed as Gr\"obner
basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD
was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we
investigate the computational complexity of BBD and show that it is
NP-complete.

Let gamma be a (not necessarily finite) structure with a finite relational
signature. We prove that deciding whether a given existential positive sentence
holds in gamma is in Logspace or complete for the class CSP(gamma)_NP under
deterministic polynomial-time many-one reductions. Here, CSP(gamma)_NP is the
class of problems that can be reduced to the Constraint Satisfaction Problem of
gamma under non-deterministic polynomial-time many-one reductions.

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called
sps(k,d,n) circuits) over base field F. It is a major open problem to design a
deterministic polynomial time blackbox algorithm that tests if C is identically
zero. Klivans & Spielman (STOC 2001) observed that the problem is open even
when k is a constant. This case has been subjected to a serious study over the
past few years, starting from the work of Dvir & Shpilka (STOC 2005).

We study the adversarial satisfiability problem, where the adversary can
choose whether variables are negated in clauses or not in order to make the
resulting formula unsatisfiable. This is one case of a general class of
adversarial optimization problems that often arise in practice and are
algorithmically much harder than the standard optimization problems. We use the
cavity method to compute large deviations of the entropy in the random
satisfiability problem with respect to the negation-configurations.

In 1994, S.G. Matthews introduced the notion of partial metric space in order
to obtain a suitable mathematical tool for program verification [Ann. New York
Acad. Sci. 728 (1994), 183-197]. He gave an application of this new structure
to parallel computing by means of a partial metric version of the celebrated
Banach fixed point theorem [Theoret. Comput. Sci. 151 (1995), 195-205]. Later
on, M.P.

The multiple Stack Travelling Salesman Problem, STSP, deals with the collect
and the deliverance of n commodities in two distinct cities. The two cities are
represented by means of two edge-valued graphs (G1,d2) and (G2,d2). During the
pick-up tour, the commodities are stored into a container whose rows are
subject to LIFO constraints.

In a recent paper Lima, Panario and Wang have provided a new method to
multiply polynomials in Chebyshev basis which aims at reducing the total number
of multiplication when polynomials have small degree. Their idea is to use
Karatsuba's multiplication scheme to improve upon the naive method but without
being able to get rid of its quadratic complexity. In this paper, we extend
their result by providing a reduction scheme which allows to multiply
polynomial in Chebyshev basis by using algorithms from the monomial basis case
and therefore get the same asymptotic complexity estimate.

We prove that quantum Turing machines are strictly superior to probabilistic
Turing machines in function computation for any space bound $ o(\log(n)) $.

We study Boolean circuits as a representation of Boolean functions and
consider different equivalence, audit, and enumeration problems. For a number
of restricted sets of gate types (bases) we obtain efficient algorithms, while
for all other gate types we show these problems are at least NP-hard.

We study problems of reconfiguration of shortest paths in graphs. We prove
that the shortest reconfiguration sequence can be exponential in the size of
the graph and that it is NP-hard to compute the shortest reconfiguration
sequence even when we know that the sequence has polynomial length. Moreover,
we also study reconfiguration of independent sets in three different models and
analyze relationships between these models, observing that shortest path
reconfiguration is a special case of independent set reconfiguration in perfect
graphs, under any of the three models.

This paper has been withdrawn by the corresponding author because the newest
version is now published in Discrete Applied Mathematics.

It is well known that Sokoban is PSPACE-complete (Culberson 1998) and several
of its variants are NP-hard (Demaine et al. 2003). In this paper we prove the
NP-hardness of some variants of Sokoban where the warehouse keeper can only
pull boxes.

This paper describe the symmentry and asymmentry of TM and problems. I take
attention to transition function's domain and range. I clarify the TM's feature
that brings Computation ability to TM, and the NTM's feature that brings rapid
computation ability to NTM. And I make the problem that have uncountable
relation between problem and solver like SAT (problem input finite set have
one-to-one relationship with solver input's finite power set), and I clarify
the coNP is not in P using that the co-problem's input have exponential size
symmetries.

For current state-of-the-art DPLL SAT-solvers the two main bottlenecks are
the amounts of time and memory used. In proof complexity, these resources
correspond to the length and space of resolution proofs. There has been a long
line of research investigating these proof complexity measures, but while
strong results have been established for length, our understanding of space and
how it relates to length has remained quite poor.

Starting from the fact that complete Accepting Hybrid Networks of
Evolutionary Processors allow much communication between the nodes and are far
from network structures used in practice, we propose in this paper three
network topologies that restrict the communication: star networks, ring
networks, and grid networks. We show that ring-AHNEPs can simulate 2-tag
systems, thus we deduce the existence of a universal ring-AHNEP. For star
networks or grid networks, we show a more general result; that is, each
recursively enumerable language can be accepted efficiently by a star- or
grid-AHNEP.

The complexity of graph homomorphism problems has been the subject of intense
study.

A polynomial identity testing algorithm must determine whether an input
polynomial (given for instance by an arithmetic circuit) is identically equal
to 0. In this paper, we show that a deterministic black-box identity testing
algorithm for (high-degree) univariate polynomials would imply a lower bound on
the arithmetic complexity of the permanent. The lower bounds that are known to
follow from derandomization of (low-degree) multivariate identity testing are
weaker.

The problem of deciding whether one point in a program is data dependent upon
another is fundamental to program analysis and has been widely studied. In this
paper we consider this problem at the abstraction level of program schemas, in
which computations occur in the Herbrand domain of terms and predicate symbols,
which represent arbitrary predicate functions, are allowed.

This paper is our third step towards developing a theory of testing monomials
in multivariate polynomials and concentrates on two problems: (1) How to
compute the coefficients of multilinear monomials; and (2) how to find a
maximum multilinear monomial when the input is a $\Pi\Sigma\Pi$ polynomial. We
first prove that the first problem is \#P-hard and then devise a $O^*(3^ns(n))$
upper bound for this problem for any polynomial represented by an arithmetic
circuit of size $s(n)$. Later, this upper bound is improved to $O^*(2^n)$ for
$\Pi\Sigma\Pi$ polynomials.

The work in this paper is to initiate a theory of testing monomials in
multivariate polynomials. The central question is to ask whether a polynomial
represented by certain economically compact structure has a multilinear
monomial in its sum-product expansion. The complexity aspects of this problem
and its variants are investigated with two folds of objectives. One is to
understand how this problem relates to critical problems in complexity, and if
so to what extent. The other is to exploit possibilities of applying algebraic
properties of polynomials to the study of those problems.

In this paper, we study the integrality gap of the Knapsack linear program in
the Sherali- Adams and Lasserre hierarchies. First, we show that an integrality
gap of 2 - {\epsilon} persists up to a linear number of rounds of
Sherali-Adams, despite the fact that Knapsack admits a fully polynomial time
approximation scheme [27,33]. Second, we show that the Lasserre hierarchy
closes the gap quickly. Specifically, after t rounds of Lasserre, the
integrality gap decreases to t/(t - 1).

We show how one can use certain deterministic algorithms for higher-value
constraint satisfaction problems (CSPs) to speed up deterministic local search
for 3-SAT. This way, we improve the deterministic worst-case running time for
3-SAT to O(1.439^n).

We consider the problem of exact identification for read-once functions over
arbitrary Boolean bases. We introduce a new type of queries (subcube identity
ones), discuss its connection to previously known ones, and study the
complexity of the problem in question. Besides these new queries, learning
algorithms are allowed to use classic membership ones. We present a technique
of modeling an equivalence query with a polynomial number of membership and
subcube identity ones, thus establishing (under certain conditions) a
polynomial upper bound on the complexity of the problem.

Graphs with high symmetry or regularity are the main source for
experimentally hard instances of the notoriously difficult graph isomorphism
problem. In this paper, we study the computational complexity of isomorphism
testing for line graphs of $t$-$(v,k,\lambda)$ designs. For this class of
highly regular graphs, we obtain a worst-case running time of $O(v^{\log v +
O(1)})$ for bounded parameters $t,k,\lambda$. In a first step, our approach
makes use of the Babai--Luks algorithm to compute canonical forms of
$t$-designs.

In their paper on the ``chasm at depth four'', Agrawal and Vinay have shown
that polynomials in m variables of degree O(m) which admit arithmetic circuits
of size 2^o(m) also admit arithmetic circuits of depth four and size 2^o(m).
This theorem shows that for problems such as arithmetic circuit lower bounds or
black-box derandomization of identity testing, the case of depth four circuits
is in a certain sense the general case. In this paper we show that smaller
depth four circuits can be obtained if we start from polynomial size arithmetic
circuits.

Normalized information distance (NID) uses the theoretical notion of
Kolmogorov complexity, which for practical purposes is approximated by the
length of the compressed version of the file involved, using a real-world
compression program. This practical application is called 'normalized
compression distance' and it is trivially computable. It is a parameter-free
similarity measure based on compression, and is used in pattern recognition,
data mining, phylogeny, clustering, and classification. The complexity
properties of its theoretical precursor, the NID, have been open.

The paper gives estimations for the sizes of the the following sets: (1) the
set of strings that have a given dependency with a fixed string, (2) the set of
strings that are pairwise \alpha independent, (3) the set of strings that are
mutually \alpha independent. The relevant definitions are as follows: C(x) is
the Kolmogorov complexity of the string x. A string y has \alpha -dependency
with a string x if C(y) - C(y|x) \geq \alpha. A set of strings {x_1, \ldots,
x_t} is pairwise \alpha-independent if for all i different from j, C(x_i) -
C(x_i | x_j) \leq \alpha.

This volume of the Electronic Proceedings in Theoretical Computer Science
(EPTCS) contains extended abstracts of talks to be presented at the Seventh
International Conference on Computability and Complexity in Analysis (CCA 2010)
that will take place in Zhenjiang, China, June 21-25, 2010. This conference is
the seventeenth event in the series of CCA annual meetings. The CCA conferences
are aimed at promoting the study and advancement of the theory of computability
and complexity over real-valued data and its application.

In computable analysis, sequences of rational numbers which effectively
converge to a real number x are used as the (rho-) names of x. A real number x
is computable if it has a computable name, and a real function f is computable
if there is a Turing machine M which computes f in the sense that, M accepts
any rho-name of x as input and outputs a rho-name of f(x) for any x in the
domain of f.

We present a method for estimating the complexity of an image based on the
concept of logical depth. Unlike the application of the concept of algorithmic
complexity by itself, the addition of the concept of logical depth results in a
characterization of objects by organizational (physical) complexity. We use
this measure to classify images by their information content. The method
provides a means for evaluating and classifying objects by way of their visual
representations.

Schoening presents a simple randomized algorithm for (d,k)-CSP problems with
running time (d(k-1)/k)^n poly(n). Here, d is the number of colors, k is the
size of the constraints, and n is the number of variables. A derandomized
version of this, given by Dantsin et al., achieves a running time of
(dk/(k+1))^n poly(n), inferior to Schoening's. We come up with a simple
modification of the deterministic algorithm, achieving a running time of
(d(k-1)/k * k^d/(k^d-1))^n \poly(n).

A dissertation submitted to the University of Bristol in accordance with the
requirements of the degree of Doctor of Philosophy (PhD) in the Faculty of
Engineering, Department of Computer Science, July 2009.

We propose to consider non confluence with respect to implicit complexity. We
come back to some well known classes of first-order functional program, for
which we have a characterization of their intentional properties, namely the
class of cons-free programs, the class of programs with an interpretation, and
the class of programs with a quasi-interpretation together with a termination
proof by the product path ordering. They all correspond to PTIME. We prove that
adding non confluence to the rules leads to respectively PTIME, NPTIME and
PSPACE.

We consider boolean circuits computing n-operators f:{0,1}^n --> {0,1}^n. As
gates we allow arbitrary boolean functions; neither fanin nor fanout of gates
is restricted. An operator is linear if it computes n linear forms, that is,
computes a matrix-vector product y=Ax over GF(2). We prove the existence of
n-operators requiring about n^2 wires in any circuit, and linear n-operators
requiring about n^2/\log n wires in depth-2 circuits, if either all output
gates or all gates on the middle layer are linear.

In answer to Ko's question raised in 1983, we show that an initial value
problem given by a polynomial-time computable, Lipschitz continuous function
can have a polynomial-space complete solution. The key insight is simple: the
Lipschitz condition means that the feedback in the differential equation is
weak. We define a class of polynomial-space computation tableaux with equally
weak feedback, and show that they are still polynomial-space complete. The same
technique also settles Ko's two later questions on Volterra integral equations.

We study the complexity of constraint satisfaction problems for templates
Gamma that are first-order definable in (Z; succ), the integers with the
successor relation. Assuming a widely believed conjecture from finite domain
constraint satisfaction (we require the tractability conjecture by Bulatov,
Jeavons and Krokhin in the special case of transitive finite templates), we
provide a full classification for the case that Gamma is locally finite (i.e.,
the Gaifman graph of Gamma has finite degree).

Hartmanis used Kolmogorov complexity to provide an alternate proof of the
classical result of Baker, Gill, and Solovay that there is an oracle relative
to which P is not NP. We refine the technique to strengthen the result,
constructing an oracle relative to which a conjecture of Lipton is false.

We study the parameterized control complexity of fallback voting, a voting
system that combines preference-based with approval voting. Electoral control
is one of many different ways for an external agent to tamper with the outcome
of an election. We show that adding and deleting candidates in fallback voting
are W[2]-hard for both the constructive and destructive case, parameterized by
the amount of action taken by the external agent.

We show an Omega(sqrt{n}/T^3) lower bound for the space required by any
unidirectional constant-error randomized T-pass streaming algorithm that
recognizes whether an expression over two types of parenthesis is
well-parenthesized. This proves a conjecture due to Magniez, Mathieu, and Nayak
(2009) and rigorously establishes the peculiar power of bi-directional streams
over unidirectional ones observed in the algorithms they present.

In this paper the minimum spanning tree problem with uncertain edge costs is
discussed. In order to model the uncertainty a discrete scenario set is
specified and a robust framework is adopted to choose a solution. The min-max,
min-max regret and 2-stage min-max versions of the problem are discussed. The
complexity and approximability of all these problems are explored.

Previous studies of search in channel graphs has assumed that the search is
global; that is, that the status of any link can be probed by the search
algorithm at any time. We consider for the first time local search, for which
only links to which an idle path from the source has already been established
may be probed. We show that some well known channel graphs may require
exponentially more probes, on the average, when search must be local than when
it may be global.

We investigate the complexity of approximately counting stable matchings in
the $k$-attribute model, where the preference lists are determined by dot
products of "preference vectors" with "attribute vectors", or by Euclidean
distances between "preference points" and "attribute points". Irving and
Leather proved that counting the number of stable matchings in the general case
is $#P$-complete.

Earlier we introduced (M.I.Trofimov, E.A.Smolenskii, Application of the
Electronegativity Indices of Organic Molecules to Tasks of Chemical
Informatics, Russian Chemical Bulletin 54(2005), 2235-2246.
DOI:10.1007/s11172-006-0105-6) effective recursive algorithm for graph
isomorphism testing. In this paper we describe used approach and iterative
modification of this algorithm, which modification has polynomial time
complexity for all graphs.

The notion of computability is stable (i.e. independent of the choice of an
indexing) over infinite-dimensional vector spaces provided they have a finite
"tensorial dimension". Such vector spaces with a finite tensorial dimension
permit to define an absolute notion of completeness for quantum computation
models and give a precise meaning to the Church-Turing thesis in the framework
of quantum theory. (Extra keywords: quantum programming languages, denotational
semantics, universality.)

We prove that NP differs from coNP and coNP is not a subset of MA in the
number-on-forehead model of multiparty communication complexity for up to k =
(1-\epsilon)log(n) players, where \epsilon>0 is any constant. Specifically, we
construct a function F with co-nondeterministic complexity O(log(n)) and
Merlin-Arthur complexity n^{\Omega(1)}. The problem was open for k > 2.

The parity decision tree model extends the decision tree model by allowing
the computation of a parity function in one step. We prove that the
deterministic parity decision tree complexity of any Boolean function is
polynomially related to the non-deterministic complexity of the function or its
complement. We also show that they are polynomially related to an analogue of
the block sensitivity. We further study parity decision trees in their
relations with an intermediate variant of the decision trees, as well as with
communication complexity.

When can a model of a physical system be regarded as computable? We provide
the definition of a computable physical model to answer this question. The
connection between our definition and Kreisel's notion of a mechanistic theory
is discussed, and several examples of computable physical models are given,
including models which feature discrete motion, models which feature
non-discrete continuous motion, and non-deterministic models such as
radioactive decay.

We study deterministic extractors for bit-fixing sources (a.k.a. resilient
functions) and exposure-resilient functions for small min-entropy. That is, of
the n bits given as input to the function, k << n bits are uniformly random and
unknown to the adversary. We show that a random function is a resilient
function with high probability if and only if k is at least roughly log n. In
contrast, we show that a random function is a static (resp. adaptive)
exposure-resilient function with high probability even if k is as small as a
constant (resp. log(log n)).

The last decade has seen a revival of interest in pebble games in the context
of proof complexity. Pebbling has proven to be a useful tool for studying
resolution-based proof systems when comparing the strength of different
subsystems, showing bounds on proof space, and establishing size-space
trade-offs. The typical approach has been to encode the pebble game played on a
graph as a CNF formula and then argue that proofs of this formula must inherit
(various aspects of) the pebbling properties of the underlying graph.
Unfortunately, the reductions used here are not tight.

The Turing machine (TM) and the Church thesis have formalized the concept of
computable number, this allowed to display non-computable numbers. This paper
defines the concept of number "approachable" by a TM and shows that some (if
not all) known non-computable numbers are approachable by TMs. Then an example
of a number not approachable by a TM is given.

We study restricted computation models related to the Tree Evaluation
Problem}. The TEP was introduced in earlier work as a simple candidate for the
(*very*) long term goal of separating L and LogDCFL. The input to the problem
is a rooted, balanced binary tree of height h, whose internal nodes are labeled
with binary functions on [k] = {1,...,k} (each given simply as a list of k^2
elements of [k]), and whose leaves are labeled with elements of [k]. Each node
obtains a value in [k] equal to its binary function applied to the values of
its children, and the output is the value of the root.

These are the lecture notes for the DIMACS Tutorial "Limits of Approximation
Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building,
Rutgers University on 20-21 July, 2009. This tutorial was jointly sponsored by
the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus
on Algorithmic Foundations of the Internet, and the Center for Computational
Intractability with support from the National Security Agency and the National
Science Foundation.

This paper provides a bridge between the classical tiling theory and cellular
automata on one side, and the complex neighborhood self-assembling situations
that exist in practice, on the other side. A neighborhood $N$ is a finite set
of pairs $(i,j) \in \Z ^2$, indicating that the neighbors of a position $(x,y)$
are the positions $(x+i,y+j)$ for $(i,j) \in N$. This includes classical
neighborhoods of size four, as well as arbitrarily complex neighborhoods.

Our primary motivation is the comparison of two different traditions used in
ICC to characterize the class FPTIME of the polynomial time computable
functions. On one side, FPTIME can be captured by Intuitionistic Light Affine
Logic (ILAL), a logic derived from Linear Logic, characterized by the
structural invariant Stratification. On the other side, FPTIME can be captured
by Safe Recursion on Notation (SRN), an algebra of functions based on
Predicative Recursion, a restriction of the standard recursion schema used to
defiine primitive recursive functions.

The problems studied in this article originate in the Graph Motif problem
introduced by Lacroix et al. (TCBB 2006) in the context of biological networks.
The problem is to decide if a vertex-colored graph has a connected subgraph
whose colors equals a given multiset of colors M. Using an algebraic framework
recently introduced in Koutis (ICALP 2008) and Koutis, Williams (ICALP 2009),
we obtain new FPT algorithms for Graph Motif and variants, with improved
running times.

In this paper we study algebraic branching programs (ABPs) with restrictions
on the order and the number of reads of variables in the program. Given a
permutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for
any directed path $p$ from source to sink, a variable can appear at most once
on $p$, and the order in which variables appear on $p$ must respect $\pi$. An
ABP $A$ is said to be of read $r$, if any variable appears at most $r$ times in
$A$. Our main result pertains to the identity testing problem. Over any field
$F$ and in the black-box model, i.e.

A fertile area of recent research has demonstrated concrete polynomial time
lower bounds for solving natural hard problems on restricted computational
models. Among these problems are Satisfiability, Vertex Cover, Hamilton Path,
Mod6-SAT, Majority-of-Majority-SAT, and Tautologies, to name a few. The proofs
of these lower bounds follow a certain proof-by-contradiction strategy that we
call alternation-trading. An important open problem is to determine how
powerful such proofs can possibly be.

The existence of a (p-)optimal propositional proof system is a major open
question in (proof) complexity; many people conjecture that such systems do not
exist. Krajicek and Pudlak (1989) show that this question is equivalent to the
existence of an algorithm that is optimal on all propositional tautologies.
Monroe (2009) recently gave a conjecture implying that such algorithm does not
exist.

We confirm the eventual evasiveness of several classes of monotone graph
properties under widely accepted number theoretic hypotheses. In particular we
show that Chowla's conjecture on Dirichlet primes implies that (a) for any
graph $H$, "forbidden subgraph $H$" is eventually evasive and (b) all
nontrivial monotone properties of graphs with $\le n^{3/2-\epsilon}$ edges are
eventually evasive. ($n$ is the number of vertices.)

Recently, many techniques have been introduced that allow the (automated)
classification of the runtime complexity of term rewrite systems (TRSs for
short). In earlier work, the authors have shown that for confluent TRSs,
innermost polynomial runtime complexity induces polytime computability of the
functions defined.

We show that all languages accepted in time f(n) >= n^2 can be accepted in
space O(f(n)^{1/2})_and_ in time O(f(n)). The proof is carried out by
simulation, based on the idea of guessing the sequences of internal states of
the simulated TM when entering certain critical cells, whose location is also
guessed. Our method cannot be generalised easily to many-tapes TMs, and in no
case can it be relativised.

A {\em parametric weighted graph} is a graph whose edges are labeled with
continuous real functions of a single common variable. For any instantiation of
the variable, one obtains a standard edge-weighted graph. Parametric weighted
graph problems are generalizations of weighted graph problems, and arise in
various natural scenarios. Parametric weighted graph algorithms consist of two
phases.

Random Number Generators play a critical role in a number of important
applications. In practice, statistical testing is employed to gather evidence
that a generator indeed produces numbers that appear to be random. In this
paper, we reports on the studies that were conducted on the compressed data
using 8 compression algorithms or compressors. The test results suggest that
the output of compression algorithms or compressors has bad randomness, the
compression algorithms or compressors are not suitable as random number
generator.

The Tile Assembly Model is a Turing universal model that Winfree introduced
in order to study the nanoscale self-assembly of complex (typically aperiodic)
DNA crystals. Winfree exhibited a self-assembly that tiles the first quadrant
of the Cartesian plane with specially labeled tiles appearing at exactly the
positions of points in the Sierpinski triangle. More recently, Lathrop, Lutz,
and Summers proved that the Sierpinski triangle cannot self-assemble in the
"strict" sense in which tiles are not allowed to appear at positions outside
the target structure.

We present a simple, natural #P-complete problem. Let G be a directed graph,
and let k be a positive integer. We define q(G;k) as follows. At each vertex v,
we place a k-dimensional complex vector x_v. We take the product, over all
edges (u,v), of the inner product <x_u,x_v>. Finally, q(G;k) is the expectation
of this product, where the x_v are chosen uniformly and independently from all
vectors of norm 1 (or, alternately, from the Gaussian distribution). We show
that q(G;k) is proportional to G's cycle partition polynomial, and therefore
that it is #P-complete for any k>1.

An aperiodic tile set was first constructed by R.Berger while proving the
undecidability of the domino problem. It turned out that aperiodic tile sets
appear in many topics ranging from logic (the Entscheidungsproblem) to physics
(quasicrystals) We present a new construction of an aperiodic tile set that is
based on Kleene's fixed-point construction instead of geometric arguments. This
construction is similar to J. von Neumann self-reproducing automata; similar
ideas were also used by P. Gacs in the context of error-correcting
computations.

We report progress on the \NL vs \UL problem. [-] We show unconditionally
that the complexity class $\ReachFewL\subseteq\UL$. This improves on the
earlier known upper bound $\ReachFewL \subseteq \FewL$. [-] We investigate the
complexity of min-uniqueness - a central notion in studying the \NL vs \UL
problem. We show that min-uniqueness is necessary and sufficient for showing
$\NL =\UL$. We revisit the class $\OptL[\log n]$ and show that {\sc
ShortestPathLength} - computing the length of the shortest path in a DAG, is
complete for $\OptL[\log n]$.

The Graph Isomorphism problem restricted to graphs of bounded treewidth or
bounded tree distance width are known to be solvable in polynomial time
[Bod90],[YBFT99]. We give restricted space algorithms for these problems
proving the following results: - Isomorphism for bounded tree distance width
graphs is in L and thus complete for the class. We also show that for this kind
of graphs a canon can be computed within logspace.

We show that the Tile Assembly Model exhibits a strong notion of universality
where the goal is to give a single tile assembly system that simulates the
behavior of any other tile assembly system.

In comparative genomic, the first step of sequence analysis is usually to
decompose two or more genomes into syntenic blocks that are segments of
homologous chromosomes. For the reliable recovery of syntenic blocks, noise and
ambiguities in the genomic maps need to be removed first. Maximal Strip
Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff
for reliably recovering syntenic blocks from genomic maps in the midst of noise
and ambiguities.

Multi-letter {\it quantum finite automata} (QFAs) were a new one-way QFA
model proposed recently by Belovs, Rosmanis, and Smotrovs (LNCS, Vol. 4588,
Springer, Berlin, 2007, pp. 60-71), and they showed that multi-letter QFAs can
accept with no error some regular languages ($(a+b)^{*}b$) that are
unacceptable by the one-way QFAs.

In this manuscript, assuming that Graedel's 1991 results are correct (which
implies that bounds on the solution values for optimization problems can be
expressed in existential second order logic where the first order part is
universal Horn), I will show that Clique and Vertex Cover can be solved in
polynomial time if the input structure is ordered and contains a successor
predicate. In the last section, we will argue about the validity of Graedel's
1991 results.

In the paper, we consider several types of queries for classical and new
problems of learning and testing read-once functions. In several cases, the
border between polynomial and exponential complexities is obtained.

We study truthful mechanisms for hiring a team of agents in three classes of
set systems: Vertex Cover auctions, k-flow auctions, and cut auctions. For
Vertex Cover auctions, the vertices are owned by selfish and rational agents,
and the auctioneer wants to purchase a vertex cover from them. For k-flow
auctions, the edges are owned by the agents, and the auctioneer wants to
purchase k edge-disjoint s-t paths, for given s and t. In the same setting, for
cut auctions, the auctioneer wants to purchase an s-t cut.

Abduction is a fundamental and important form of non-monotonic reasoning.
Given a knowledge base explaining how the world behaves it aims at finding an
explanation for some observed manifestation. In this paper we focus on
propositional abduction, where the knowledge base and the manifestation are
represented by propositional formulae. The problem of deciding whether there
exists an explanation has been shown to be SigmaP2-complete in general. We
consider variants obtained by restricting the allowed connectives in the
formulae to certain sets of Boolean functions.

In this paper we study polynomial identity testing of sums of $k$ read-once
algebraic branching programs ($\Sigma_k$-RO-ABPs), generalizing the work in
(Shpilka and Volkovich 2008,2009), who considered sums of $k$ read-once
formulas ($\Sigma_k$-RO-formulas). We show that $\Sigma_k$-RO-ABPs are strictly
more powerful than $\Sigma_k$-RO-formulas, for any $k \leq \lfloor n/2\rfloor$,
where $n$ is the number of variables. We obtain the following results:

We provide asymptotically sharp bounds for the Gaussian surface area and the
Gaussian noise sensitivity of polynomial threshold functions. In particular we
show that if $f$ is a degree-$d$ polynomial threshold function, then its
Gaussian sensitivity at noise rate $\epsilon$ is less than some quantity
asymptotic to $\frac{d\sqrt{2\epsilon}}{\pi}$ and the Gaussian surface area is
at most $\frac{d}{\sqrt{2\pi}}$. Furthermore these bounds are asymptotically
tight as $\epsilon\to 0$ and $f$ the threshold function of a product of $d$
distinct homogeneous linear functions.

The Abstract Milling problem is a natural and quite general graph-theoretic
model for geometric milling problems. Given a graph, one asks for a walk that
covers all its vertices with a minimum number of turns, as specified in the
graph model by a 0/1 turncost function fx at each vertex x giving, for each
ordered pair of edges (e,f) incident at x, the turn cost at x of a walk that
enters the vertex on edge e and departs on edge f. We describe an initial study
of the parameterized complexity of the problem.

We investigate the power of the Wang tile self-assembly model at temperature
1, a threshold value that permits attachment between any two tiles that share
even a single bond. When restricted to deterministic assembly in the plane, no
temperature 1 assembly system has been shown to build a shape with a tile
complexity smaller than the diameter of the shape.

It is currently not possible to quantify the resources needed to perform a
computation. As a consequence, it is not possible to reliably evaluate the
hardware resources needed for the application of algorithms or the running of
programs. This is apparent in both computer science, for instance, in
cryptanalysis, and in neuroscience, for instance, comparative neuro-anatomy.

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

Our first result shows that low-degree polynomial threshold functions cannot
approximate any function with many influential variables. We provide a couple
of examples where this technique yields tight approximation bounds.

Let x be a random vector coming from any k-wise independent distribution over
{-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is
determined up to an additive epsilon for k = poly(1/epsilon). This answers an
open question of Diakonikolas et al. (FOCS 2009). Using standard constructions
of k-wise independent distributions, we obtain a broad class of explicit
generators that epsilon-fool the class of degree-2 threshold functions with
seed length log(n)*poly(1/epsilon).

We propose models for lobbying in a probabilistic environment, in which an
actor (called "The Lobby") seeks to influence voters' preferences of voting for
or against multiple issues when the voters' preferences are represented in
terms of probabilities. In particular, we provide two evaluation criteria and
three bribery methods to formally describe these models, and we consider the
resulting forms of lobbying with and without issue weighting.

In the paper we develop a method for constructing quantum algorithms for
computing Boolean functions by quantum ordered read-once branching programs
(quantum OBDDs). Our method is based on fingerprinting technique and
representation of Boolean functions by their characteristic polynomials. We use
circuit notation for branching programs for desired algorithms presentation.
For several known functions our approach provides optimal QOBDDs.

This paper demonstrates that P != NP. The way was to construct an artificial
problem (a generalization to SAT: the XG-SAT, much more difficult than the
former) and to demonstrate that it is in NP but not in P. The demonstration
consists of:

We prove that any monotone switching network solving directed connectivity on
N vertices must have size at least N^(Omega(lgN)).