A resolving set $S$ of a graph $G$ is a subset of its vertices such that no
two vertices of $G$ have the same distance vector to $S$. The Metric Dimension
problem asks for a resolving set of minimum size, and in its decision form, a
resolving set of size at most some specified integer. This problem is
NP-complete, and remains so in very restricted classes of graphs. It is also
W[2]-complete with respect to the size of the solution. Metric Dimension has
proven elusive on graphs of bounded treewidth. On the algorithmic side, a
polytime algorithm is known for trees, and even for outerplanar graphs, but the
general case of treewidth at most two is open. On the complexity side, no
parameterized hardness is known. This has led several papers on the topic to
ask for the parameterized complexity of Metric Dimension with respect to
treewidth. We provide a first answer to the question.
We show that Metric Dimension parameterized by the treewidth of the input
graph is W[1]-hard. More refinedly we prove that, unless the Exponential...

more |
pdf
| html
None.

okateim:
2019/07/19 [7]
Metric Dimension Parameterized by Treewidth (https://t.co/VpA6gwyolE)

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

The Fourier Transform is one of the most important linear transformations
used in science and engineering. Cooley and Tukey's Fast Fourier Transform
(FFT) from 1964 is a method for computing this transformation in time $O(n\log
n)$. From a lower bound perspective, relatively little is known. Ailon shows in
2013 an $\Omega(n\log n)$ bound for computing the normalized Fourier Transform
assuming only unitary operations on pairs of coordinates is allowed. The goal
of this document is to describe a natural open problem that arises from this
work, which is related to group theory, and in particular to representation
theory.

more |
pdf
| html
None.

NPunuvar:
Interesting Open Problem Related to Complexity of Computing the Fourier Transform and Group Theory
https://t.co/4o9vKCFVHD

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 1579

Unqiue Words: 604

Simon's problem played an important role in the history of quantum
algorithms, as it inspired Shor to discover the celebrated quantum algorithm
solving integer factorization in polynomial time. Besides, the quantum
algorithm for Simon's problem has been recently applied to break symmetric
cryptosystems. Generalized Simon's problem is a natural extension of Simon's
problem: Given a function $f:\{0,1\}^n \to \{0,1\}^m$ with $n \le m$ and the
promise that there exists a subgroup $S \le \mathbb{Z}_2^n$ of rank $k$ s.t.
for any $s, x\in\{0,1\}^n, f(x) = f(x\oplus s)$ iff $s\in S$, the goal is to
find $S$. It is not difficult to design a quantum algorithm for solving this
problem exactly with query complexity of $O(n-k)$. However, so far it is not
clear what is the classical deterministic query complexity of this problem. %
Therefore, it is interesting and nontrivial to consider that, not only for
clarifying the gap between quantum and classical computing on this problem, but
also from the viewpoint of classical computing.
In this...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 7682

Unqiue Words: 1588

Andreev's Problem states the following: Given an integer $d$ and a subset of
$S \subseteq \mathbb{F}_q \times \mathbb{F}_q$, is there a polynomial $y =
p(x)$ of degree at most $d$ such that for every $a \in \mathbb{F}_q$, $(a,p(a))
\in S$? We show an $\text{AC}^0[\oplus]$ lower bound for this problem.
This problem appears to be similar to the list recovery problem for degree
$d$-Reed-Solomon codes over $\mathbb{F}_q$ which states the following: Given
subsets $A_1,\ldots,A_q$ of $\mathbb{F}_q$, output all (if any) the
Reed-Solomon codewords contained in $A_1\times \cdots \times A_q$. For our
purpose, we study this problem when $A_1, \ldots, A_q$ are random subsets of a
given size, which may be of independent interest.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 8905

Unqiue Words: 1996

We study the role of perfect completeness in probabilistically checkable
proof systems (PCPs) and give a new way to transform a PCP with imperfect
completeness to a PCP with perfect completeness when the initial gap is a
constant. In particular, we show that $\text{PCP}_{c,s}[r,q] \subseteq
\text{PCP}_{1,1-\Omega(1)}[r+O(1),q+O(r)]$, for $c-s=\Omega(1)$. This implies
that one can convert imperfect completeness to perfect in linear-sized PCPs for
$NTIME[O(n)]$ with a $O(\log n)$ additive loss in the query complexity $q$. We
show our result by constructing a "robust circuit" using threshold gates. These
results are a gap amplification procedure for PCPs (when completeness is
imperfect), analogous to questions studied in parallel repetition and
pseudorandomness.
We also investigate the time complexity of approximating perfectly
satisfiable instances of 3SAT versus those with imperfect completeness. We show
that the Gap-ETH conjecture without perfect completeness is equivalent to
Gap-ETH with perfect completeness, i.e. we show that...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

In this paper we study the complexity of counting Constraint Satisfaction
Problems (CSPs) of the form #CSP($\mathcal{C}$,-), in which the goal is, given
a relational structure $\mathbf{A}$ from a class $\mathcal{C}$ of structures
and an arbitrary structure $\mathbf{B}$, to find the number of homomorphisms
from $\mathbf{A}$ to $\mathbf{B}$. Flum and Grohe showed that
#CSP($\mathcal{C}$,-) is solvable in polynomial time if $\mathcal{C}$ has
bounded treewidth [FOCS'02]. Building on the work of Grohe [JACM'07] on
decision CSPs, Dalmau and Jonsson then showed that, if $\mathcal{C}$ is a
recursively enumerable class of relational structures of bounded arity, then
assuming FPT $\neq$ #W[1], there are no other cases of #CSP($\mathcal{C}$,-)
solvable exactly in polynomial time (or even fixed-parameter time) [TCS'04].
We show that, assuming FPT $\neq$ W[1] (under randomised parametrised
reductions) and for $\mathcal{C}$ satisfying certain general conditions,
#CSP($\mathcal{C}$,-) is not solvable even approximately for $\mathcal{C}$...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

*Tracking 160,435 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible