TAMC2011 Accepted Papers with Abstracts
Submodular Function Minimization under a Submodular Set Covering Constraint
Abstract:
In this paper, we consider the problem of minimizing a submodular
function under a submodular set covering constraint. We propose
an approximation algorithm for this problem by extending the algorithm
of Iwata and Nagano [FOCS'09] for the set cover problem with
a submodular cost function.
function under a submodular set covering constraint. We propose
an approximation algorithm for this problem by extending the algorithm
of Iwata and Nagano [FOCS'09] for the set cover problem with
a submodular cost function.
On the polynomial depth of various sets of random strings
Abstract:
This paper proposes new notions of polynomial depth (called monotone poly depth),
based on a polynomial version
of monotone Kolmogorov complexity. We show that monotone poly depth satisfies all desirable properties of depth notions i.e.,
both trivial and random sequences are not monotone poly deep, monotone poly depth satisfies the slow growth law i.e.,
no simple process can transform a non deep sequence into a deep one, and
monotone poly deep sequences exist (unconditionally).
We give two natural example of deep sets, by showing that both the set of Levin-random strings and the set of Kolmogorov strings are monotone poly deep.
based on a polynomial version
of monotone Kolmogorov complexity. We show that monotone poly depth satisfies all desirable properties of depth notions i.e.,
both trivial and random sequences are not monotone poly deep, monotone poly depth satisfies the slow growth law i.e.,
no simple process can transform a non deep sequence into a deep one, and
monotone poly deep sequences exist (unconditionally).
We give two natural example of deep sets, by showing that both the set of Levin-random strings and the set of Kolmogorov strings are monotone poly deep.
On the Amount of Nonconstructivity in Learning Recursive Functions
Abstract:
Nonconstructive proofs are a powerful mechanism in mathematics.
Furthermore, nonconstructive computations by various types of machines and
automata have been considered by e.g., Karp and Lipton~\cite{kl-em-82} and
Freivalds~\cite{f-ciaa-09}.
They allow to regard more complicated algorithms from the viewpoint
of much more primitive computational devices. The amount of
nonconstructivity is a quantitative characterization of the distance
between types of computational devices with respect to solving a specific
problem.
In the present paper, the amount of nonconstructivity in learning of
recursive functions is studied. Different learning types are compared
with respect to the amount of nonconstructivity needed to learn the whole
class of general recursive functions.
Upper and lower bounds for the amount of nonconstructivity needed are proved.
Furthermore, nonconstructive computations by various types of machines and
automata have been considered by e.g., Karp and Lipton~\cite{kl-em-82} and
Freivalds~\cite{f-ciaa-09}.
They allow to regard more complicated algorithms from the viewpoint
of much more primitive computational devices. The amount of
nonconstructivity is a quantitative characterization of the distance
between types of computational devices with respect to solving a specific
problem.
In the present paper, the amount of nonconstructivity in learning of
recursive functions is studied. Different learning types are compared
with respect to the amount of nonconstructivity needed to learn the whole
class of general recursive functions.
Upper and lower bounds for the amount of nonconstructivity needed are proved.
Non-Adaptive Complex Group Testing with Multiple Positive Sets
Abstract:
Given $n$ items with at most $d$ of them having a particular property
(referred as positive items), a single test on a selected subset of
them is positive if the subset contains any positive item. The
non-adaptive group testing problem is to design how to group the items
to minimize the number of tests required to identify all positive items
in which all tests are performed in parallel. This problem is well-studied
and algorithms exist that match the lower bound with a small gap of
$\log d$ asymptoticically. An
important generalization of the problem is to consider the case that
individual positive item cannot make a test positive, but a combination
of them (referred as positive subsets) can do. The problem is referred as
the {\it non-adaptive complex group testing}.
Assume there are at most $d$ positive subsets whose sizes are at
most $s$, existing algorithms either require $\Omega(\log^s n)$ tests
for general $n$ or $O({s+d \choose d} \log n)$ tests for some special
values of $n$ . However, the number of items in each test cannot be
very small or very large in real situation. The above algorithms
cannot be applied because there is no control on the number of items
in each test. In this paper, we provide a novel and practical
derandomized algorithm to construct the tests, which has two
important properties. (1) Our algorithm requires only
$O\left((d+s)^{d+s+1}/(d^d s^s) \log n\right)$ tests for all
positive integers $n$ which matches the upper bound on the
number of tests when all positive subsets are
singletons, i.e. $s=1$. (2) All tests in our algorithm can have
the same number of tested items $k$. Thus, our algorithm can
solve the problem with additional constraints on the number of
tested items in each test, such as maximum or minimum number of
tested items.
(referred as positive items), a single test on a selected subset of
them is positive if the subset contains any positive item. The
non-adaptive group testing problem is to design how to group the items
to minimize the number of tests required to identify all positive items
in which all tests are performed in parallel. This problem is well-studied
and algorithms exist that match the lower bound with a small gap of
$\log d$ asymptoticically. An
important generalization of the problem is to consider the case that
individual positive item cannot make a test positive, but a combination
of them (referred as positive subsets) can do. The problem is referred as
the {\it non-adaptive complex group testing}.
Assume there are at most $d$ positive subsets whose sizes are at
most $s$, existing algorithms either require $\Omega(\log^s n)$ tests
for general $n$ or $O({s+d \choose d} \log n)$ tests for some special
values of $n$ . However, the number of items in each test cannot be
very small or very large in real situation. The above algorithms
cannot be applied because there is no control on the number of items
in each test. In this paper, we provide a novel and practical
derandomized algorithm to construct the tests, which has two
important properties. (1) Our algorithm requires only
$O\left((d+s)^{d+s+1}/(d^d s^s) \log n\right)$ tests for all
positive integers $n$ which matches the upper bound on the
number of tests when all positive subsets are
singletons, i.e. $s=1$. (2) All tests in our algorithm can have
the same number of tested items $k$. Thus, our algorithm can
solve the problem with additional constraints on the number of
tested items in each test, such as maximum or minimum number of
tested items.
The Complexity and Approximability of Minimum Contamination Problems
Abstract:
In this article, we investigate the complexity and approximability
of the Minimum Contamination Problems, which are derived from
epidemic spreading areas and have been extensively studied recently.
We show that both the Minimum Average Contamination Problem and the
Minimum Worst Contamination Problem are NP-hard problems even on
restrict cases. For any $\epsilon>0$, we give $(1+\epsilon,
O(\frac{1+\epsilon}{\epsilon}\log n))$-bicriteria approximation
algorithm for the Minimum Average Contamination Problem. Moreover, we show that the
Minimum Average Contamination Problem is NP-hard to be approximated
within $5/3-\epsilon$ and the Minimum Worst Contamination Problem is
NP-hard to be approximated within $2-\epsilon$, for any
$\epsilon>0$, giving the first hardness results of approximation of
constant ratios to the problems.
of the Minimum Contamination Problems, which are derived from
epidemic spreading areas and have been extensively studied recently.
We show that both the Minimum Average Contamination Problem and the
Minimum Worst Contamination Problem are NP-hard problems even on
restrict cases. For any $\epsilon>0$, we give $(1+\epsilon,
O(\frac{1+\epsilon}{\epsilon}\log n))$-bicriteria approximation
algorithm for the Minimum Average Contamination Problem. Moreover, we show that the
Minimum Average Contamination Problem is NP-hard to be approximated
within $5/3-\epsilon$ and the Minimum Worst Contamination Problem is
NP-hard to be approximated within $2-\epsilon$, for any
$\epsilon>0$, giving the first hardness results of approximation of
constant ratios to the problems.
Group-theoretic Lower Bounds for the Complexity of Matrix Multiplication
Abstract:
The complexity of multiplication in group algebras is closely related to the famous problem of the complexity of matrix multiplication. Inspired by the recent group-theoretic approach by Cohn and Umans and the following group-theoretic algorithms by Cohn et al. for matrix multiplication, we present conditional group-theoretic lower bounds for the complexity of matrix multiplication. These bounds depend on the complexity of the multiplication in group algebras.
We then turn to the complexity of multiplication in group algebras. Using Bläser's lower bounds we characterize all semisimple group algebras of the minimal bilinear complexity and prove the improved lower bounds for the other group algebras. We also show the upper bounds for the bilinear complexity of multiplication in group algebras that improve the best previously known Atkinson's upper bound. Our bounds depend on the complexity of matrix multiplication and are "almost linear" if the exponent of matrix multiplication equals 2.
We then turn to the complexity of multiplication in group algebras. Using Bläser's lower bounds we characterize all semisimple group algebras of the minimal bilinear complexity and prove the improved lower bounds for the other group algebras. We also show the upper bounds for the bilinear complexity of multiplication in group algebras that improve the best previously known Atkinson's upper bound. Our bounds depend on the complexity of matrix multiplication and are "almost linear" if the exponent of matrix multiplication equals 2.
Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions
Abstract:
We discuss the optimal allocation problem in
combinatorial auction, where the items
are allocated to bidders so that
the sum of the bidders' utility functions is maximized.
In this paper, we consider the case where
utility functions are given by
quadratic functions; the class of quadratic utility functions has
a succinct representation but is sufficiently general.
The main aim of this paper is to reveal the computational complexity
of the optimal allocation problem with quadratic utility functions.
We consider various important cases of
quadratic utility functions, and show
NP-hardness and polynomial-time exact/approximation algorithm for each case.
These results are shown by using the relationship
with graph cut problems such as the min/max cut problem and the multiway
cut problem.
combinatorial auction, where the items
are allocated to bidders so that
the sum of the bidders' utility functions is maximized.
In this paper, we consider the case where
utility functions are given by
quadratic functions; the class of quadratic utility functions has
a succinct representation but is sufficiently general.
The main aim of this paper is to reveal the computational complexity
of the optimal allocation problem with quadratic utility functions.
We consider various important cases of
quadratic utility functions, and show
NP-hardness and polynomial-time exact/approximation algorithm for each case.
These results are shown by using the relationship
with graph cut problems such as the min/max cut problem and the multiway
cut problem.
A Bad Instance for k-means++
Abstract:
k-means++ is a seeding technique for the k-means method with an expected approximation ratio of O(\log k), where k denotes the number of clusters. Examples are known on which the expected approximation ratio of k-means++ is Omega(\log k), showing that the upper bound is asymptotically tight. However, it remained open whether k-means++ yields an O(1)-approximation with probability 1/poly(k) or even with constant probability. We settle this question and present instances on which k-means++ achieves an approximation ratio of (2/3-\epsilon)*\log(k) only with exponentially small probability.
A Compact encoding of Unordered Binary Trees
Abstract:
A naive encoding of ordered binary trees with $n$ vertices
needs $2n$ bits for each tree,
and it is asymptotically optimal.
In this paper we give a new simple encoding of unordered binary trees.
The encoding needs at most $4+1.4n$ bits for each tree.
Our encoding and decoding algorithms are simple and
run in $O(n)$ time.
needs $2n$ bits for each tree,
and it is asymptotically optimal.
In this paper we give a new simple encoding of unordered binary trees.
The encoding needs at most $4+1.4n$ bits for each tree.
Our encoding and decoding algorithms are simple and
run in $O(n)$ time.
Deterministic Algorithms for Multi-Criteria TSP
Abstract:
We present deterministic approximation algorithms for the multi-criteria traveling salesman problem (TSP). Our algorithms are faster and simpler than the existing randomized algorithms.
First, we devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/(2k) - \eps and 1/(4k-2) - \eps, respectively, where k is the number of objective functions. For two objective functions, we obtain ratios of
3/8 - \eps and 1/4 - \eps for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.
Second, we adapt the generic cycle cover algorithm for Min-TSP. It achieves ratios of 3/2 + \eps, 1/2 + (\gamma^3)/(1-3\gamma^2) + \eps, and 1/2 + (\gamma^2)/(1-\gamma) + \eps for multi-criteria Min-ATSP with distances 1 and 2, Min-ATSP with \gamma-triangle inequality and Min-STSP with \gamma-triangle inequality, respectively.
First, we devise algorithms for the symmetric and asymmetric multi-criteria Max-TSP that achieve ratios of 1/(2k) - \eps and 1/(4k-2) - \eps, respectively, where k is the number of objective functions. For two objective functions, we obtain ratios of
3/8 - \eps and 1/4 - \eps for the symmetric and asymmetric TSP, respectively. Our algorithms are self-contained and do not use existing approximation schemes as black boxes.
Second, we adapt the generic cycle cover algorithm for Min-TSP. It achieves ratios of 3/2 + \eps, 1/2 + (\gamma^3)/(1-3\gamma^2) + \eps, and 1/2 + (\gamma^2)/(1-\gamma) + \eps for multi-criteria Min-ATSP with distances 1 and 2, Min-ATSP with \gamma-triangle inequality and Min-STSP with \gamma-triangle inequality, respectively.
How to Cut a Graph into Many Pieces
Abstract:
In this paper we consider the problem of finding a graph separator of a given
size that decomposes the graph into the maximum number of connected components.
We present the picture of the computational complexity and the approximability of this
problem for several natural classes of graphs.
We first provide an overview of the hardness of approximation of this problem, which
stems mainly from its close relation to the INDEPENDENT SET and to the MAXIMUM
CLIQUE problem. Next, we show that the problem is solvable in polynomial time for
interval graphs and graphs of bounded treewidth. We also show that MAXINUM COMPONENTS
is fixed-parameter tractable on planar graphs with the size of the separator as
the parameter. Our main contribution is the derivation of an efficient polynomial-time
approximation scheme for the problem on planar graphs.
size that decomposes the graph into the maximum number of connected components.
We present the picture of the computational complexity and the approximability of this
problem for several natural classes of graphs.
We first provide an overview of the hardness of approximation of this problem, which
stems mainly from its close relation to the INDEPENDENT SET and to the MAXIMUM
CLIQUE problem. Next, we show that the problem is solvable in polynomial time for
interval graphs and graphs of bounded treewidth. We also show that MAXINUM COMPONENTS
is fixed-parameter tractable on planar graphs with the size of the separator as
the parameter. Our main contribution is the derivation of an efficient polynomial-time
approximation scheme for the problem on planar graphs.
Lower Bounds for the Smoothed Number of Pareto optimal Solutions
Abstract:
In 2009, Roeglin and Teng showed that the smoothed number of Pareto optimal solutions of linear multi-criteria optimization problems is polynomially bounded in the number n of variables and the maximum density \phi of the semi-random input model for any fixed number of objective functions. Their bound is, however, not very practical because the exponents grow exponentially in the number (d+1) of objective functions. In a recent breakthrough, Moitra and O'Donnell improved this bound significantly to O(n^{2d} \phi^{d(d+1)/2}).
An "intriguing problem", which Moitra and O'Donnell formulate in their paper, is how much further this bound can be improved. The previous lower bounds do not exclude the possibility of a polynomial upper bound whose degree does not depend on d. In this paper we resolve this question by constructing a class of instances with \Omega((n \phi)^{(d-\log{d}) \cdot (1-\Theta{1/\phi})}) Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of \Omega(n^2 \phi^{1 - \Theta{1/\phi}}), which almost matches the known upper bound of O(n^2 \phi).
An "intriguing problem", which Moitra and O'Donnell formulate in their paper, is how much further this bound can be improved. The previous lower bounds do not exclude the possibility of a polynomial upper bound whose degree does not depend on d. In this paper we resolve this question by constructing a class of instances with \Omega((n \phi)^{(d-\log{d}) \cdot (1-\Theta{1/\phi})}) Pareto optimal solutions in expectation. For the bi-criteria case we present a higher lower bound of \Omega(n^2 \phi^{1 - \Theta{1/\phi}}), which almost matches the known upper bound of O(n^2 \phi).
Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
Abstract:
In this paper, we provide polynomial-time algorithms for different extensions
of the matching counting problem, namely maximal matchings, path
matchings (linear forest) and paths, on graph classes of bounded clique-width.
For maximal matchings, we introduce matching-cover pairs to efficiently
handle maximality in the local structure, and develop a polynomial
time algorithm.
For path matchings, we develop a way to classify the path matchings in
a polynomial number of equivalent classes.
Using these, we develop dynamic programing algorithms that run in
polynomial time of the graph size, but in exponential time of the clique-width.
In particular, we show that for a graph $G$ of $n$ vertices and clique-width
$k$, these problems can be solved in $O(n^{f(k)})$ time where $f$ is
exponential in $k$ or in $O(n^{g(l)})$ time where $g$ is linear or quadratic
in $l$ if an $l$-expression for $G$ is given as input.
of the matching counting problem, namely maximal matchings, path
matchings (linear forest) and paths, on graph classes of bounded clique-width.
For maximal matchings, we introduce matching-cover pairs to efficiently
handle maximality in the local structure, and develop a polynomial
time algorithm.
For path matchings, we develop a way to classify the path matchings in
a polynomial number of equivalent classes.
Using these, we develop dynamic programing algorithms that run in
polynomial time of the graph size, but in exponential time of the clique-width.
In particular, we show that for a graph $G$ of $n$ vertices and clique-width
$k$, these problems can be solved in $O(n^{f(k)})$ time where $f$ is
exponential in $k$ or in $O(n^{g(l)})$ time where $g$ is linear or quadratic
in $l$ if an $l$-expression for $G$ is given as input.
Low Distortion Metric Embeddings Into Constant Dimension
Abstract:
We investigate the possibility of embedding an n-point metric space into a constant dimensional vector space with the maximum norm, such that the embedding is almost isometric, that is, the distortion of distances is kept arbitrarily close to 1. When the source metric is generated by any fixed norm on a
finite dimensional vector space, we prove that this embedding is always possible, such that the dimension of the target space remains constant, independent of n. Our result is the first of this type, as in all previous results either the dimension of the target space grows to infinity with n, or the distortion is not arbitrarily low, even for quite special metrics. Furthermore, our embedding can be computed in deterministic linear time in n, given oracle access to the norm.
finite dimensional vector space, we prove that this embedding is always possible, such that the dimension of the target space remains constant, independent of n. Our result is the first of this type, as in all previous results either the dimension of the target space grows to infinity with n, or the distortion is not arbitrarily low, even for quite special metrics. Furthermore, our embedding can be computed in deterministic linear time in n, given oracle access to the norm.
Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
Abstract:
Spanning tree congestion is a relatively new graph parameter,
which has been studied intensively.
This paper studies the complexity of the problem to determine the spanning tree congestion
for non-sparse graph classes, while it was investigated for some sparse graph classes before.
We prove that the problem is NP-hard even for chain graphs and split graphs.
To cope with the hardness of the problem,
we present a fast (exponential-time) exact algorithm that runs in $O^{\ast}(2^{n})$ time,
where $n$ denotes the number of vertices.
Additionally, we provide a constant-factor approximation algorithm for cographs,
and a linear-time algorithm for chordal cographs.
which has been studied intensively.
This paper studies the complexity of the problem to determine the spanning tree congestion
for non-sparse graph classes, while it was investigated for some sparse graph classes before.
We prove that the problem is NP-hard even for chain graphs and split graphs.
To cope with the hardness of the problem,
we present a fast (exponential-time) exact algorithm that runs in $O^{\ast}(2^{n})$ time,
where $n$ denotes the number of vertices.
Additionally, we provide a constant-factor approximation algorithm for cographs,
and a linear-time algorithm for chordal cographs.
Grey-Box Steganography
Abstract:
In steganography secret messages are encoded into unsuspicious covertexts
such that an adversary cannot distinguish the resulting stegotexts from original covertexts.
To accomplish their respective tasks, encoder and adversary need information about the covertext distribution.
In previous analyses, the knowledge about the covertext channel was highly unbalanced:
while the adversary had full knowledge, the encoder could only query a black-box sampling oracle.
In such a situation, the only general steganographic method known is rejection sampling,
for which the sampling complexity has been shown to be exponential in the rate of message bits per covertext document.
The other extreme, a white-box setting, where the encoder knows the covertext distribution perfectly,
resp. the distribution is efficiently computable, is also unrealistic in practice.
To resolve these deficiencies and to get a finer-grained security analysis, we propose a new model,
called grey-box steganography.
Here, the encoder starts with at least some partial knowledge about the type of covertext channel.
Using the sampling oracle, he first uses machine learning techniques to learn the covertext distribution
and then tries to actively construct a suitable stegotext -- either by modifying a covertext or by creating a new one.
We illustrate our concept with channels that can be described by monomials.
They can easily be learnt from positive examples.
A generic construction is given showing that
besides the learning complexity, the efficiency of grey-box steganography depends on the
complexity of the membership test, and suitable modification procedures.
For the concept class monomials we present an efficient algorithm for changing a covertext into a stegotext.
such that an adversary cannot distinguish the resulting stegotexts from original covertexts.
To accomplish their respective tasks, encoder and adversary need information about the covertext distribution.
In previous analyses, the knowledge about the covertext channel was highly unbalanced:
while the adversary had full knowledge, the encoder could only query a black-box sampling oracle.
In such a situation, the only general steganographic method known is rejection sampling,
for which the sampling complexity has been shown to be exponential in the rate of message bits per covertext document.
The other extreme, a white-box setting, where the encoder knows the covertext distribution perfectly,
resp. the distribution is efficiently computable, is also unrealistic in practice.
To resolve these deficiencies and to get a finer-grained security analysis, we propose a new model,
called grey-box steganography.
Here, the encoder starts with at least some partial knowledge about the type of covertext channel.
Using the sampling oracle, he first uses machine learning techniques to learn the covertext distribution
and then tries to actively construct a suitable stegotext -- either by modifying a covertext or by creating a new one.
We illustrate our concept with channels that can be described by monomials.
They can easily be learnt from positive examples.
A generic construction is given showing that
besides the learning complexity, the efficiency of grey-box steganography depends on the
complexity of the membership test, and suitable modification procedures.
For the concept class monomials we present an efficient algorithm for changing a covertext into a stegotext.
Approximating Edge Dominating Set in Dense Graphs
Abstract:
We study the approximation complexity of the Minimum Edge Dominating Set problem in everywhere $\epsilon$-dense and average $\bar{\epsilon}$-dense graphs. More precisely, we consider the computational complexity of approximating a generalization of the Minimum Edge Dominating Set problem, the so called Minimum Subset Edge Dominating Set problem. As a direct result, we obtain for the special case of the Minimum Edge Dominating Set problem in everywhere $\epsilon$-dense and average $\bar{\epsilon}$-dense graphs by using the techniques of Karpinski and Zelikovsky, the approximation ratios of $\min\{2,3/(1+2\epsilon)\}$ and of
$\min\{2,3/(3-2\sqrt{1-\bar{\epsilon}})\}$, respectively.
On the other hand, we show that it is UGC-hard to approximate the Minimum Edge Dominating Set problem in everywhere $\epsilon$-dense graphs with a ratio better than $2/(1+\epsilon)$ with $\epsilon>1/3$ and $2/(2-\sqrt{1-\bar{\epsilon}})$ with $\bar{\epsilon}> 5/9$ in average $\bar{\epsilon}$-dense graphs.
$\min\{2,3/(3-2\sqrt{1-\bar{\epsilon}})\}$, respectively.
On the other hand, we show that it is UGC-hard to approximate the Minimum Edge Dominating Set problem in everywhere $\epsilon$-dense graphs with a ratio better than $2/(1+\epsilon)$ with $\epsilon>1/3$ and $2/(2-\sqrt{1-\bar{\epsilon}})$ with $\bar{\epsilon}> 5/9$ in average $\bar{\epsilon}$-dense graphs.
Hide-and-Seek: Algorithms for Polygon Walk Problems
Abstract:
Jack and Jill want to play hide-and-seek on the boundary of a simple polygon. Given arbitrary paths for the two children along this boundary, our goal is to determine whether Jack can walk along his path without ever being seen by Jill. To solve this problem, we use a linear-sized skeleton invisibility diagram to implicitly represent invisibility information between pairs of points on the boundary of the simple polygon. This structure has additional applications for any polygon walk problem where one entity wishes to remain hidden throughout a traversal of some path. We also show how Jack can avoid being seen not just by one moving child but by an arbitrary number of moving children.
Approximating minimum cost source location problems with local vertex-connectivity demands
Abstract:
The source location problem is a problem of computing a minimum cost source set in an undirected graph so that the connectivity between the source set and a vertex is at least the demand of the vertex.
In this paper, the connectivity between a source set S and a vertex v is dened as the maximum number of paths between v and S no two of which have common vertex except v. We propose an O(d^* log d^*)-approximation algorithm for the problem with maximum demand d^*. We also dene a variant of the source location problem and propose an approximation algorithm for it.
In this paper, the connectivity between a source set S and a vertex v is dened as the maximum number of paths between v and S no two of which have common vertex except v. We propose an O(d^* log d^*)-approximation algorithm for the problem with maximum demand d^*. We also dene a variant of the source location problem and propose an approximation algorithm for it.
Improved Approximation Bounds for the Student-Project Allocation Problem with Preferences over Projects
Abstract:
Manlove and O'Malley proposed the Student-Project Allocation Problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of 21/19 (>1.1052).
Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models
Abstract:
We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin randomized protocol in the Simultaneous Message Passing (SMP) model, with the communication cost matching the known lower bound for the \emph{quantum} and \emph{two-way} model up to a logarithm factor. As a corollary, this closes a quadratic gap between quantum lower bound and randomized upper bound for the one-way model, answering an open question raised in Shi and Zhang \cite{SZ09}.
Catching a fast robber on interval graphs
Abstract:
We analyse the Cops and $\infty$-fast Robber game on the class of interval graphs and prove it to be polynomially decidable on such graphs. This solves an open problem posed in paper ``Pursuing a fast robber on a graph'' by Fomin et al. The game is known to be already NP-hard on chordal graphs and split-graphs.
The game is played by two players, one controlling k cops, the other a robber. The players alternate in turns, all the cops move at once to distance at most one, the robber moves along any cop-free path. Cops win by capturing the robber, the robber by avoiding capture.
The analysis relies on the properties of an interval representation of the graph. We show that while the game-state is generally exponential, every cops' move can be decomposed into simple moves of two types, split and sweep, defined by certain cuts in the interval representation. This gives a restricted game equivalent to the original one together with a winning strategy computable in polynomial time.
The game is played by two players, one controlling k cops, the other a robber. The players alternate in turns, all the cops move at once to distance at most one, the robber moves along any cop-free path. Cops win by capturing the robber, the robber by avoiding capture.
The analysis relies on the properties of an interval representation of the graph. We show that while the game-state is generally exponential, every cops' move can be decomposed into simple moves of two types, split and sweep, defined by certain cuts in the interval representation. This gives a restricted game equivalent to the original one together with a winning strategy computable in polynomial time.
An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
Abstract:
We study the problem of reconfiguring one list edge-coloring of a graph into another list edge-coloring by changing only one edge color assignment at a time, while at all times maintaining a list edge-coloring, given a list of allowed colors for each edge. Ito, Kaminski and Demaine gave a sufficient condition so that any list edge-coloring of a tree can be transformed into any other. In this paper, we give a new sufficient condition which improves the known one. Our sufficient condition is best possible in some sense. The proof is constructive, and yields a polynomial-time algorithm that finds a transformation between two given list edge-colorings of a tree with $n$ vertices via $O(n^2)$ recoloring steps. We remark that the upper bound $O(n^2)$ on the number of recoloring steps is tight, because there is an infinite family of instances on paths that satisfy our sufficient condition and whose reconfiguration requires $\Omega(n^2)$ recoloring steps.
A Real Elementary Approach to the Master Recurrence and Generalizations
Abstract:
The master theorem provides a solution to
a well-known divide-and-conquer recurrence,
called here the master recurrence.
This paper proves two cook-book style generalizations of
this master theorem. The first extends the treated class of driving
functions to the natural class of exponential-logarithmic (EL) functions.
The second extends the result to the multiterm master recurrence.
The power and simplicity of our approach comes from
re-interpreting integer recurrences as real recurrences,
with emphasis on elementary techniques and real induction.
a well-known divide-and-conquer recurrence,
called here the master recurrence.
This paper proves two cook-book style generalizations of
this master theorem. The first extends the treated class of driving
functions to the natural class of exponential-logarithmic (EL) functions.
The second extends the result to the multiterm master recurrence.
The power and simplicity of our approach comes from
re-interpreting integer recurrences as real recurrences,
with emphasis on elementary techniques and real induction.
Extending Partial Representations of Interval Graphs
Abstract:
We initiate the study of the computational complexity of the question of extending partial representations of geometric intersection graphs. In this paper we consider classes of interval graphs -- given a collection of real intervals that forms an
intersection representation of an induced subgraph of an input graph, is it possible to add intervals to achieve an intersection representation of the entire graph? We present an $\O(n^2)$ time algorithm that solves this problem and constructs a representation if one exists. Our algorithm can also be used to list all nonisomorphic extensions with $\O(n^2)$ delay.
Although the classes of proper and unit interval graphs coincide, the partial representation extension problems differ on them. We present an $\O(mn)$ time decision algorithm for partial representation extension of proper interval graphs, but for unit interval graphs the complexity remains open.
Finally we show how our methods can be used for solving the problem of simultaneous interval representations. We prove that this problem is fixed-paramater tractable with the size of the common intersection of the input graphs being the parameter.
intersection representation of an induced subgraph of an input graph, is it possible to add intervals to achieve an intersection representation of the entire graph? We present an $\O(n^2)$ time algorithm that solves this problem and constructs a representation if one exists. Our algorithm can also be used to list all nonisomorphic extensions with $\O(n^2)$ delay.
Although the classes of proper and unit interval graphs coincide, the partial representation extension problems differ on them. We present an $\O(mn)$ time decision algorithm for partial representation extension of proper interval graphs, but for unit interval graphs the complexity remains open.
Finally we show how our methods can be used for solving the problem of simultaneous interval representations. We prove that this problem is fixed-paramater tractable with the size of the common intersection of the input graphs being the parameter.
Near approximation of maximum weight matching through efficient weight reduction
Abstract:
Let G be an edge-weighted hypergraph on n vertices, m edges
of size \le s, where the edges have real weights in an interval [1, W].
We show that if we can approximate a maximum weight matching in G within factor \alpha in time T(n,m,W) then we can find a matching of weight at least
(\alpha-\epsilon) times the maximum weight of a matching in G in time (\epsilon^{-1})^{O(1)}\times \max_{1\le q \le O(\epsilon
\frac {\log {\frac n {\epsilon}}} {\log \epsilon^{-1}})}
\max_{m_1+...m_q=m}\sum_1^qT(\min\{n,sm_j\},m_{j},(\epsilon^{-1})^{O(\epsilon^{-1})}).
In particular, if we combine our result with the recent
(1-\epsilon)-approximation algorithm for maximum weight matching in graphs
due to Duan and Pettie whose time complexity
has a poly-logarithmic dependence on W then we obtain a
(1-\epsilon)-approximation algorithm for maximum weight
matching in graphs running in time
(\epsilon^{-1})^{O(1)}(m+n).
of size \le s, where the edges have real weights in an interval [1, W].
We show that if we can approximate a maximum weight matching in G within factor \alpha in time T(n,m,W) then we can find a matching of weight at least
(\alpha-\epsilon) times the maximum weight of a matching in G in time (\epsilon^{-1})^{O(1)}\times \max_{1\le q \le O(\epsilon
\frac {\log {\frac n {\epsilon}}} {\log \epsilon^{-1}})}
\max_{m_1+...m_q=m}\sum_1^qT(\min\{n,sm_j\},m_{j},(\epsilon^{-1})^{O(\epsilon^{-1})}).
In particular, if we combine our result with the recent
(1-\epsilon)-approximation algorithm for maximum weight matching in graphs
due to Duan and Pettie whose time complexity
has a poly-logarithmic dependence on W then we obtain a
(1-\epsilon)-approximation algorithm for maximum weight
matching in graphs running in time
(\epsilon^{-1})^{O(1)}(m+n).
Multiprocessor Speed Scaling for Jobs with Arbitrary Sizes and Deadlines
Abstract:
In this paper we study energy efficient deadline scheduling on multiprocessors. The problem is to dispatch jobs to processors and determine the speed and jobs to run in each processor so as to complete all jobs by their deadlines using the minimum energy. The problem has been well studied for the single processor case. For the multiprocessor setting, constant competitive online algorithms for special cases of
unit size jobs or arbitrary size jobs with agreeable deadlines have been proposed.
A randomized algorithm has been proposed for the jobs of arbitrary sizes and arbitrary deadlines. We propose a deterministic online algorithm for the general setting and show that it is $O(\log P)$-competitive, where $P$ is the ratio of
the maximum and minimum job size.
unit size jobs or arbitrary size jobs with agreeable deadlines have been proposed.
A randomized algorithm has been proposed for the jobs of arbitrary sizes and arbitrary deadlines. We propose a deterministic online algorithm for the general setting and show that it is $O(\log P)$-competitive, where $P$ is the ratio of
the maximum and minimum job size.
Switching to Hedgehog-Free Graphs is NP-Complete
Abstract:
We study the problem of deciding if, for a fixed graph H, a given graph is switching-equivalent to an H-free graph. In all cases of H that have been solved so far, the problem is decidable in polynomial time. We give infinitely many graphs H such that the problem is NP-complete, thus solving an open problem [Kratochvil, Nesetril and Zyka, Ann. Discrete Math. 51 (1992)].
Energy and Fan-in of Threshold Circuits Computing Mod Functions
Abstract:
In this paper,
we consider a threshold circuit $C$
computing the modulus function MOD$_m$,
and investigate a relationship between two complexity measures,
fan-in $l$ and energy $e$ of $C$, where
the fan-in $l$ is defined to be the maximum number of inputs of every
gate in $C$, and the energy $e$ to be
the maximum number of gates outputting ``1'' over all inputs to $C$.
We first prove that MOD$_m$ of $n$ variables can be computed by a
threshold circuit
of fan-in $l$ and energy $e= O ( n/l )$, and then
provide an almost tight
lower bound $e= \Omega ((n-m)/l)$.
Our results imply that there exists a tradeoff between
the fan-in and energy of threshold circuits computing the modulus
function.
we consider a threshold circuit $C$
computing the modulus function MOD$_m$,
and investigate a relationship between two complexity measures,
fan-in $l$ and energy $e$ of $C$, where
the fan-in $l$ is defined to be the maximum number of inputs of every
gate in $C$, and the energy $e$ to be
the maximum number of gates outputting ``1'' over all inputs to $C$.
We first prove that MOD$_m$ of $n$ variables can be computed by a
threshold circuit
of fan-in $l$ and energy $e= O ( n/l )$, and then
provide an almost tight
lower bound $e= \Omega ((n-m)/l)$.
Our results imply that there exists a tradeoff between
the fan-in and energy of threshold circuits computing the modulus
function.
An Improved Kernel for Planar Connected Dominating Set
Abstract:
In this paper, we study the Planar Connected Dominating Set problem, which,
given a planar graph~$G=(V,E)$ and a non-negative integer~$k$, asks for a
subset~$D\subseteq V$ with~$|D|\le k$ such that~$D$ forms a dominating set
of~$G$ and induces a connected graph. Answering an open question by S.~Saurabh
[The 2nd Workshop on Kernelization (WorKer 2010)], we provide a kernelization
algorithm for this problem leading to a problem kernel with~$130k$ vertices,
significantly improving the previously best upper bound on the kernel size.
To this end, we incorporate a vertex coloring technique with data reduction
rules and introduce for the first time a distinction of two types of regions
into the region decomposition framework, which allows a refined analysis of the
region size and could be used to reduce the kernel sizes achieved by the
region decomposition technique for a large range of problems.
given a planar graph~$G=(V,E)$ and a non-negative integer~$k$, asks for a
subset~$D\subseteq V$ with~$|D|\le k$ such that~$D$ forms a dominating set
of~$G$ and induces a connected graph. Answering an open question by S.~Saurabh
[The 2nd Workshop on Kernelization (WorKer 2010)], we provide a kernelization
algorithm for this problem leading to a problem kernel with~$130k$ vertices,
significantly improving the previously best upper bound on the kernel size.
To this end, we incorporate a vertex coloring technique with data reduction
rules and introduce for the first time a distinction of two types of regions
into the region decomposition framework, which allows a refined analysis of the
region size and could be used to reduce the kernel sizes achieved by the
region decomposition technique for a large range of problems.
NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth
Abstract:
ACC_m circuits are circuits consisting of unbounded fan-in AND, OR and MOD_m gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of ACC_m circuits of quasi-polynomial size and o(loglog n) depth, where m is an arbitrarily chosen constant.
Closed Left-r.e. Sets
Abstract:
A set is called r-closed left-r.e. iff every set r-reducible
to it is also a left-r.e. set. It is shown that there is a
cohesive many-one-closed left-r.e. set; furthermore, it is shown
that the many-one-closed left-r.e. sets have only polylogarithmic
initial segment Kolmogorov complexity. Ascending reductions are
many-one reductions via an ascending function; for ascending-closed
left-r.e. sets one can get much higher initial segment Kolmogorov
complexities although also in that case the complexity has to
remain sublinear in the length of the initial segment.
to it is also a left-r.e. set. It is shown that there is a
cohesive many-one-closed left-r.e. set; furthermore, it is shown
that the many-one-closed left-r.e. sets have only polylogarithmic
initial segment Kolmogorov complexity. Ascending reductions are
many-one reductions via an ascending function; for ascending-closed
left-r.e. sets one can get much higher initial segment Kolmogorov
complexities although also in that case the complexity has to
remain sublinear in the length of the initial segment.
On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric
Abstract:
It is known that the d-dimensional Steiner Minimum Tree
Problem in Hamming metric is NP-complete if d is considered to be a
part of the input size. On the other hand, it was an open question whether
the problem is also NP-complete in fixed dimensions. In this paper we
answer this question by showing that the problem is NP-complete for
any dimension strictly greater than 2. We also show that the Steiner ratio is 2 − 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special case d = 3.
Problem in Hamming metric is NP-complete if d is considered to be a
part of the input size. On the other hand, it was an open question whether
the problem is also NP-complete in fixed dimensions. In this paper we
answer this question by showing that the problem is NP-complete for
any dimension strictly greater than 2. We also show that the Steiner ratio is 2 − 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special case d = 3.
Edge Contractions in Subclasses of Chordal Graphs
Abstract:
Modifying a given graph to obtain another graph is a well-studied problem with applications in many fields. Given two input graphs G and H, the Contractibility problem is to decide whether H can be obtained from G by a sequence of edge contractions. This problem is known to be NP-complete already when both input graphs are trees of bounded diameter. We prove that Contractibility can be solved in polynomial time when G is a trivially perfect graph and H is a threshold graph, thereby giving the first classes of graphs of unbounded treewidth and unbounded degree on which the problem can be solved in polynomial time. We show that this polynomial-time result is in a sense tight, by proving that Contractibility is NP-complete when G and H are both trivially perfect graphs, and when G is a split graph and H is a threshold graph. If the graph H is fixed and only G is given as input, then the problem is called H-Contractibility. This problem is known to be NP-complete on general graphs already when H is a path on four vertices. We show that, for any fixed graph H, the H-Contractibility problem can be solved in polynomial time if the input graph G is a split graph.
A Better Upper Bound on Weights of Exact Threshold Functions
Abstract:
A Boolean function is called an {\em exact threshold function} if it decides whether the input vector $\vec{x}\in\{0,1\}^n$ is on a hyperplane $\vec{w}^T\vec{x}=t$ ($\vec{w}\in\mathbb{Z}^n$ is called the {\em weights}). In this paper we study the upper bound of the weights required to represent any exact threshold function. Let $k$ be the dimension of the linear subspace spanned by Boolean points on $\vec{w}^T\vec{x}=t$. We first give an upper bound $O(n^k)$ for constant $k$, which matches the lower bound in~\cite{Babai:2010}. Then we prove an upper bound $O(k^{O(k^2)}n^k)$ for general cases, improving the result $\min\{n^{2^k},n^{n/2+1}\}$ in~\cite{Babai:2010}.
Fast Exact Algorithm for L(2,1)-Labeling of Graphs
Abstract:
An L(2,1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2,1)-span of a graph is the minimum possible span of its L(2,1)-labelings. We show how to compute the L(2,1)-span of a connected graph in time $O^*(2.6488^n)$. Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3.2361, with 3 seemingly having been the Holy Grail.
Generalized Satisfiability for the Description Logic ALC
Abstract:
The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms.Several fragments of ALC, notably logics in the FL, EL, and DL-Lite families, have an easier satisfiability problem; sometimes it is even tractable. We classify the complexity of the standard satisfiability problems for all possible Boolean and quantifier fragments of ALC in the presence of general axioms.
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
Abstract:
We present an alternative proof of a theorem by Courcelle, Makowski and Rotics
which states that problems expressible in MSO are solvable in linear time
for graphs of bounded rankwidth. Our proof uses a game-theoretic approach
and has the advantage of being self-contained, intuitive, and fairly easy to follow.
In particular, our presentation does not assume any background in logic or automata theory. We believe that it is good to have alternative proofs of this important result. Moreover our approach can be generalized to prove other results of a similar flavor, for example, that of Courcelle's Theorem for treewidth.
which states that problems expressible in MSO are solvable in linear time
for graphs of bounded rankwidth. Our proof uses a game-theoretic approach
and has the advantage of being self-contained, intuitive, and fairly easy to follow.
In particular, our presentation does not assume any background in logic or automata theory. We believe that it is good to have alternative proofs of this important result. Moreover our approach can be generalized to prove other results of a similar flavor, for example, that of Courcelle's Theorem for treewidth.
Approximability of the Subset Sum Reconfiguration Problem
Abstract:
The {\sc subset sum} problem is a well-known NP-complete problem in which we wish to find a packing (subset) of items (integers) into a knapsack with capacity so that the sum of integers in the packing is at most the capacity of the knapsack and at least a given integer threshold. In this paper, we study the problem of reconfiguring one packing into another packing by moving only one item at a time, while at all times maintaining the feasibility of packings. First we show that this decision problem is strongly NP-hard, and is PSPACE-complete if we are given a conflict graph for the set of items in which each vertex corresponds to an item and each edge represents a pair of items that are not allowed to be packed together into the knapsack. We then study an optimization version of the problem: we wish to maximize the minimum sum among all packings in the reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme (PTAS), while the problem is APX-hard if we are given a conflict graph.
Pi_0^1 Sets and tilings
Abstract:
In this paper, we prove that given any Pi_0^1 subset P of {0, 1}^N
there is a tileset τ with a countable set of configurations C such that P
is recursively homeomorphic to C \ U where U is a computable set of
configurations. As a consequence, if P is countable, this tileset has the
exact same set of Turing degrees.
there is a tileset τ with a countable set of configurations C such that P
is recursively homeomorphic to C \ U where U is a computable set of
configurations. As a consequence, if P is countable, this tileset has the
exact same set of Turing degrees.
Locally injective homomorphism to the simple Weight graphs
Abstract:
A Weight graph is a connected (multi)graph with two vertices $u$ and $v$
of degree at least three and other vertices of degree two.
Moreover, if any of these two vertices is removed, the remaining graph contains a cycle.
A Weight graph is called simple if the degree of $u$ and $v$ is three.
We show full computational complexity characterization
of the problem of deciding the existence of a locally injective homomorphism
from an input graph $G$ to any fixed simple Weight graph by identifying
some polynomial cases and some NP-complete cases.
of degree at least three and other vertices of degree two.
Moreover, if any of these two vertices is removed, the remaining graph contains a cycle.
A Weight graph is called simple if the degree of $u$ and $v$ is three.
We show full computational complexity characterization
of the problem of deciding the existence of a locally injective homomorphism
from an input graph $G$ to any fixed simple Weight graph by identifying
some polynomial cases and some NP-complete cases.
Planarity Testing Revisited
Abstract:
Planarity Testing is the problem of determining whether a given graph
is planar while planar embedding is the corresponding construction problem.
The bounded space complexity of these problems has been
determined to be exactly deterministic logarithmic space by Allender and Mahajan with the aid of Reingold's result. Unfortunately, the algorithm is quite daunting and generalizing it to, say the bounded genus case, seems a tall order.
We present a simple planar embedding algorithm running in logspace.
The algorithm uses the unique embedding of $3$-connected planar graphs, a variant
of Tutte's criterion on the conflict graphs of cycles and an explicit
change of basis for the cycle space.
We also present a logspace algorithm to find an obstacle to planarity, viz. a
Kuratowski minor, for non-planar graphs. To the best of
our knowledge this is the first logspace algorithm for this problem.
is planar while planar embedding is the corresponding construction problem.
The bounded space complexity of these problems has been
determined to be exactly deterministic logarithmic space by Allender and Mahajan with the aid of Reingold's result. Unfortunately, the algorithm is quite daunting and generalizing it to, say the bounded genus case, seems a tall order.
We present a simple planar embedding algorithm running in logspace.
The algorithm uses the unique embedding of $3$-connected planar graphs, a variant
of Tutte's criterion on the conflict graphs of cycles and an explicit
change of basis for the cycle space.
We also present a logspace algorithm to find an obstacle to planarity, viz. a
Kuratowski minor, for non-planar graphs. To the best of
our knowledge this is the first logspace algorithm for this problem.
Intuitive Probability Logic
Abstract:
In literature, different deductive systems are developed for probability logics.
But, for formulas, they provide essentially equivalent definitions of consistency.
In this paper, we present a guided maximally consistent extension theorem which says that any probability assignment to formulas in a finite local language satisfying some constraints specified by probability formulas is consistent in probability logics, and hence connects this reasoning with formal reasoning about probabilities. Moreover, we employ this theorem to show two interesting results:
(1) The satisfiability of a probability formula is
equivalent to the solvability of the corresponding system of linear
inequalities through a natural translation based on atoms not on
Hintikka sets;
(2) the Countably Additivity Rule in Goldblatt10 is
necessary for his deductive construction of final coalgebras for
functors on Meas, the category of measurable spaces.
But, for formulas, they provide essentially equivalent definitions of consistency.
In this paper, we present a guided maximally consistent extension theorem which says that any probability assignment to formulas in a finite local language satisfying some constraints specified by probability formulas is consistent in probability logics, and hence connects this reasoning with formal reasoning about probabilities. Moreover, we employ this theorem to show two interesting results:
(1) The satisfiability of a probability formula is
equivalent to the solvability of the corresponding system of linear
inequalities through a natural translation based on atoms not on
Hintikka sets;
(2) the Countably Additivity Rule in Goldblatt10 is
necessary for his deductive construction of final coalgebras for
functors on Meas, the category of measurable spaces.
Some Tractable Win-Lose Games
Abstract:
Finding a Nash equilibrium in a bimatrix game is PPAD-hard (Chen and Deng, 2006, Chen, Deng and Teng, 2009). The problem, even when restricted to win-lose bimatrix games, remains PPAD-hard (Abbott, Kane and Valiant, 2005). However, there do exist polynomial time tractable classes of win-lose bimatrix games - such as, very sparse games (Codenotti, Leoncini and Resta, 2006) and planar games (Addario-Berry, Olver and Vetta, 2007).
We extend the results in the latter work to $K_{3,3}$ minor-free games and a subclass of $K_5$ minor-free games. Both these classes strictly contain planar games. Further, we sharpen the upper bound to unambiguous logspace UL, a small complexity class contained well within polynomial time P. Apart from these classes of games, our results also extend to a class of games that contain both $K_{3,3}$ and $K_5$ as minors, thereby covering a large and non-trivial class of win-lose bimatrix games. For this class, we prove an upper bound of nondeterministic logspace NL, again a small complexity class in P. Our techniques are primarily graph theoretic and use structural characterizations of the considered minor-closed families.
We extend the results in the latter work to $K_{3,3}$ minor-free games and a subclass of $K_5$ minor-free games. Both these classes strictly contain planar games. Further, we sharpen the upper bound to unambiguous logspace UL, a small complexity class contained well within polynomial time P. Apart from these classes of games, our results also extend to a class of games that contain both $K_{3,3}$ and $K_5$ as minors, thereby covering a large and non-trivial class of win-lose bimatrix games. For this class, we prove an upper bound of nondeterministic logspace NL, again a small complexity class in P. Our techniques are primarily graph theoretic and use structural characterizations of the considered minor-closed families.
A Note on Obfuscation for Cryptographic Functionalities of Secret-Operation then Public-Encryption
Abstract:
Obfuscating programs has been a fascinating field of theoretical
cryptography in recent years. Hohenberger et al. in TCC'07 and
Hada in EUROCRYPT'10 showed that re-encryption and encrypted
signature are obfuscateable and their constructions are dedicated
and the security proofs are complicated. Whereas, obfuscation for
other complicated cryptographic functionalities still remains
unknown.
In a recent breakthrough on fully homomorphic encryption in
STOC'09, Gentry noted that one algorithm in his construction,
called \textsf{Recrypt}, is a re-encryption program. Along
Gentry's sight, we observe that with fully homomorphic encryption,
we can obfuscate a category of functionalities, including
re-encryption and encrypted signature and even
signature-then-encryption, which can be characterized as first
secret operation and then public encryption. We formally
demonstrate the obfuscation for this category of functionalities,
in which the construction and security proof are general and
simple. We then show the applicability of this obfuscation that it
is secure in the contexts of the three functionalities.
cryptography in recent years. Hohenberger et al. in TCC'07 and
Hada in EUROCRYPT'10 showed that re-encryption and encrypted
signature are obfuscateable and their constructions are dedicated
and the security proofs are complicated. Whereas, obfuscation for
other complicated cryptographic functionalities still remains
unknown.
In a recent breakthrough on fully homomorphic encryption in
STOC'09, Gentry noted that one algorithm in his construction,
called \textsf{Recrypt}, is a re-encryption program. Along
Gentry's sight, we observe that with fully homomorphic encryption,
we can obfuscate a category of functionalities, including
re-encryption and encrypted signature and even
signature-then-encryption, which can be characterized as first
secret operation and then public encryption. We formally
demonstrate the obfuscation for this category of functionalities,
in which the construction and security proof are general and
simple. We then show the applicability of this obfuscation that it
is secure in the contexts of the three functionalities.
Lower Bounds for Testing Computability by Small Width OBDDs
Abstract:
We consider the problem of testing whether a boolean function f is computable by
a read-once, width-two ordered binary decision diagram (OBDD), also known as a branching program. This problem has two variants: one where the variables must occur in a fixed, known order, and one where the variables are allowed to occur in an arbitrary order. We show that for both variants, any nonadaptive testing algorithm must make Omega(n) queries, and thus any adaptive testing algorithm must
make Omega(log n) queries. These bounds are essentially tight, as they match (up to O(log log n) factors) upper bounds proven by Ron and Tsur. We also consider the problem of testing width-4 OBDDs where the variables occur in a fixed order. We
show that for this problem Omega(n) queries are required, resolving a conjecture of Goldreich. We prove all of our lower bounds using a new technique of Blais, Brody, and Matulef, giving simple reductions from known hard problems in communication complexity to the testing problems at hand. Our results for width-2 OBDDs provide the first examples of the power of this technique for proving strong nonadaptive bounds.
a read-once, width-two ordered binary decision diagram (OBDD), also known as a branching program. This problem has two variants: one where the variables must occur in a fixed, known order, and one where the variables are allowed to occur in an arbitrary order. We show that for both variants, any nonadaptive testing algorithm must make Omega(n) queries, and thus any adaptive testing algorithm must
make Omega(log n) queries. These bounds are essentially tight, as they match (up to O(log log n) factors) upper bounds proven by Ron and Tsur. We also consider the problem of testing width-4 OBDDs where the variables occur in a fixed order. We
show that for this problem Omega(n) queries are required, resolving a conjecture of Goldreich. We prove all of our lower bounds using a new technique of Blais, Brody, and Matulef, giving simple reductions from known hard problems in communication complexity to the testing problems at hand. Our results for width-2 OBDDs provide the first examples of the power of this technique for proving strong nonadaptive bounds.
Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
Abstract:
In this paper we introduce a new graph class denoted as Gen(P3,C3,C5).
It contains all graphs that can be generated via split composition by using paths
P3 and cycles C3 and C5 as components. This new graph class extends the
well known class of distance-hereditary graphs, which corresponds to
Gen(P3,C3). For the new class we provide efficient algorithms for several
basic combinatorial problems: recognition, stretch number, stability number,
clique number, domination number, chromatic number, graph isomorphism, and
clique width.
It contains all graphs that can be generated via split composition by using paths
P3 and cycles C3 and C5 as components. This new graph class extends the
well known class of distance-hereditary graphs, which corresponds to
Gen(P3,C3). For the new class we provide efficient algorithms for several
basic combinatorial problems: recognition, stretch number, stability number,
clique number, domination number, chromatic number, graph isomorphism, and
clique width.
The hardness of Median in the synchronized bit communication model
Abstract:
The synchronized bit communication model, defined recently by Impagliazzo and Williams in \emph{Communication complexity with synchronized clocks}, CCC '10, is a communication model which allows the participants to share a common clock. The main open problem posed in this paper was the following: does the synchronized bit model allow a logarithmic speed-up for all functions over the standard deterministic model of communication? We resolve this question in the negative by showing that the Median function, whose communication complexity is $O(\log n)$, does not admit polytime synchronized bit protocol with communication complexity $O\left(\log^{1-\varepsilon} n\right)$ for any $\varepsilon > 0$. Our results follow by a new round-communication trade-off for the Median function in the standard model, which easily translates to its hardness in the synchronized bit model.
Succinct Dynamic Cardinal Trees with Constant Time Operations for Small Alphabet
Abstract:
Cardinal trees are one of the fundamental data structures which are rooted trees that each node has at most $k$ children, and each edge is labeled with a symbol from the alphabet $\{1,\ldots,k\}$. We present a succinct representation for $k$-ary cardinal trees of $n$ nodes where $k=O(polylog(n))$. Our data structure requires~$2n+n\log k+o(n\log k)$ bits and performs the following operations in $O(1)$ time: {\sf parent}, {\sf child}($i$) {\sf label-child}($\alpha$), {\sf degree}, {\sf subtree-size}, {\sf preorder}, {\sf is-ancestor}($x$), {\sf insert-leaf}($\alpha$), {\sf delete-leaf}($\alpha$). The space is close to the information theoretic lower bound. The update times are amortized. The operations are performed in the course of traversing the tree. This improves the best succinct dynamic binary tree representation of~\cite{dynamic_binary03_dynarray} by dropping the update time from $O((\log\log)^{1+\epsilon})$ to $O(1)$, for $\epsilon>0$. It also improves the succinct dynamic $k$-ary cardinal trees representation of Arroyuelo~\cite{diego08} for small alphabet, by speeding up both the query time of~$O(\log\log n)$, and the update time of~$O((\log\log n)^2/\log\log\log n)$ to $O(1)$, solving an open problem in~\cite{diego08}.
Integer Representation Towards Efficient Counting in Bit Probe Model
Abstract:
We consider the problem of representing numbers in close to optimal space and supporting increment, decrement, addition and subtraction operations efficiently.
We study the problem in the bit probe model, and analyze the number of bits read and written to perform the operations, both in the worst-case and in the average-case.
For {\em space-optimal counters} where we are interested in representing any number in the range [0...2^n-1] using exactly n bits and support the increment and
decrement operations, we give a representation that reads at most n-1 bits and writes at most 3 bits in the worst-case. To the best of our knowledge, this is the first such representation which reads strictly less than n bits to support the operations.
For Redundant Counters where we only need to represent numbers in the range [0...L]
for some integer L < 2^n-1 using n bits, we define the efficiency of the counter as the ratio between L+1 and 2^n.
We present various representations that achieve different trade-offs between the read and write complexities and the efficiency.
We also give another representation of integers that uses n + O(log n ) bits to represent integers in the range [0...2^n-1] that supports efficient addition and deletion operations, improving space complexity of an earlier representation by Munro and Rahman [Algorithmica, 2010].
We study the problem in the bit probe model, and analyze the number of bits read and written to perform the operations, both in the worst-case and in the average-case.
For {\em space-optimal counters} where we are interested in representing any number in the range [0...2^n-1] using exactly n bits and support the increment and
decrement operations, we give a representation that reads at most n-1 bits and writes at most 3 bits in the worst-case. To the best of our knowledge, this is the first such representation which reads strictly less than n bits to support the operations.
For Redundant Counters where we only need to represent numbers in the range [0...L]
for some integer L < 2^n-1 using n bits, we define the efficiency of the counter as the ratio between L+1 and 2^n.
We present various representations that achieve different trade-offs between the read and write complexities and the efficiency.
We also give another representation of integers that uses n + O(log n ) bits to represent integers in the range [0...2^n-1] that supports efficient addition and deletion operations, improving space complexity of an earlier representation by Munro and Rahman [Algorithmica, 2010].
An algebraic characterization of strictly piecewise languages
Abstract:
This paper provides an algebraic characterization of the Strictly Piecewise class of languages introduced by Rogers et al. (2010), which not only appear relevant to natural language but is also a mathematically natural subclass of the Piecewise Testable languages, which were first studied by Imre Simon (1975). The algebraic characterization highlights a similarity between the Strictly Piecewise and Strictly Local languages (McNaughton and Papert 1971), and also leads to a procedure which can decide whether a regular language L is Strictly Piecewise in polynomial time in the length of the syntactic monoid for L.
