In the $k$-Steiner Orientation problem we are given a mixed graph, that is,
with both directed and undirected edges, and a set of $k$ terminal pairs. The
goal is to find an orientation of the undirected edges that maximizes the
number of terminal pairs for which there is a path from the source to the sink.
The problem is known to be W[1]-hard when parameterized by $k$ and hard to
approximate up to some constant for FPT algorithms assuming Gap-ETH. On the
other hand, no approximation better than $O(k)$ is known.
We show that $k$-Steiner Orientation admits no sublogarithmic approximation
algorithm, even with a parameterized running time, assuming W[1] $\ne$ FPT. To
obtain this result, we reduce the problem to itself via a hashing-based gap
amplification technique, which turns out useful even outside of the FPT
paradigm. Precisely, we rule out any approximation ratio of the form $(\log
k)^{o(1)}$ for parameterized algorithms and $(\log n)^{o(1)}$ for purely
polynomial running time, under the same assumption. This constitutes a...

more |
pdf
| html
None.

okateim:
2019/07/16 [13]
Inapproximability within W[1]: the case of Steiner Orientation (https://t.co/bQ8zJcYPAE)

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

In this paper, we study reversibility of one-dimensional(1D) linear cellular
automata(LCA) under null boundary condition, whose core problems have been
divided into two main parts: calculating the period of reversibility and
verifying the reversibility in a period. With existing methods, the time and
space complexity of these two parts are still too expensive to be employed. So
the process soon becomes totally incalculable with a slightly big size, which
greatly limits its application. In this paper, we set out to solve these two
problems using two efficient algorithms, which make it possible to solve
reversible LCA of very large size. Furthermore, we provide an interesting
perspective to conversely generate 1D LCA from a given period of reversibility.
Due to our methods' efficiency, we can calculate the reversible LCA with large
size, which has much potential to enhance security in cryptography system.

more |
pdf
| html
SciencePapers:
Efficient methods to determine the reversibility of general 1D linear cellular automata in polynomial complexity. https://t.co/Zk2JYtrJyQ

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 9213

Unqiue Words: 1987

The Super-SAT or SSAT problem was introduced by Dinur, Kindler, Raz and
Safra[2002,2003] to prove the NP-hardness of approximation of two popular
lattice problems - Shortest Vector Problem (SVP) and Closest Vector Problem
(CVP). They conjectured that SSAT is NP-hard to approximate to within factor
$n^c$ for some constant $c>0$, where $n$ is the size of the SSAT instance. In
this paper we prove this conjecture assuming the Projection Games Conjecture
(PGC), given by Moshkovitz[2012]. This implies hardness of approximation of SVP
and CVP within polynomial factors, assuming the Projection Games Conjecture.
We also reduce SSAT to the Nearest Codeword Problem (NCP) and Learning
Halfspace Problem (LHP), as considered by Arora, Babai, Stern and
Sweedyk[1997]. This proves that both these problems are NP-hard to approximate
within factor $N^{c'/\log\log n}$ for some constant $c'>0$ where $N$ is the
size of the instances of the respective problems. Assuming the Projection Games
Conjecture these problems are proved to be NP-hard to...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 12396

Unqiue Words: 2294

Inspired by the boolean discrepancy problem, we study the following
optimization problem which we term \textsc{Spherical Discrepancy}: given $m$
unit vectors $v_1, \dots, v_m$, find another unit vector $x$ that minimizes
$\max_i \langle x, v_i\rangle$. We show that \textsc{Spherical Discrepancy} is
APX-hard and develop a multiplicative weights-based algorithm that achieves
nearly optimal worst-case error bounds. We use our algorithm to give the first
non-trivial lower bounds for the problem of covering a hypersphere by
hyperspherical caps of uniform volume at least $2^{-o(\sqrt{n})}$, and to give
a lower bound for covering a Gaussian random variable by equal-sized
halfspaces. Up to a log factor, our lower bounds match known upper bounds in
this regime. Finally, we show how to modify our algorithm to solve a natural
version of the Koml{\'o}s problem for the spherical setting.

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 158,360 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible