Hardness magnification reduces major complexity separations (such as
$\mathsf{\mathsf{EXP}} \nsubseteq \mathsf{NC}^1$) to proving lower bounds for
some natural problem $Q$ against weak circuit models. Several recent works
[OS18, MMW19, CT19, OPS19, CMMW19, Oli19, CJW19a] have established results of
this form. In the most intriguing cases, the required lower bound is known for
problems that appear to be significantly easier than $Q$, while $Q$ itself is
susceptible to lower bounds but these are not yet sufficient for magnification.
In this work, we provide more examples of this phenomenon, and investigate
the prospects of proving new lower bounds using this approach. In particular,
we consider the following essential questions associated with the hardness
magnification program:
Does hardness magnification avoid the natural proofs barrier of Razborov and
Rudich [RR97]?
Can we adapt known lower bound techniques to establish the desired lower
bound for $Q$?

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 6

Total Words: 28402

Unqiue Words: 4364

We continue and extend previous work on the parameterized complexity analysis
of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby
strengthening earlier results both on the side of parameterized hardness as
well as on the side of fixed-parameter tractability. Other than for its famous
sister problem Stable Marriage which focuses on a bipartite scenario, Stable
Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose
edges specify the possible matchings of each two agents (agents are represented
by graph vertices). Herein, incomplete lists and ties reflect the fact that in
realistic application scenarios the agents cannot bring all other agents into a
linear order. Among our main contributions is to show that it is W[1]-hard to
compute a maximum-cardinality stable matching for acceptability graphs of
bounded treedepth, bounded tree-cut width, and bounded feedback vertex number
(these are each time the respective parameters). However, if we `only' ask for
perfect stable matchings or...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

We consider the $k$-prize-collecting Steiner tree problem. An instance is
composed of an integer $k$ and a graph $G$ with costs on edges and penalties on
vertices. The objective is to find a tree spanning at least $k$ vertices which
minimizes the cost of the edges in the tree plus the penalties of vertices not
in the tree. This is one of the most fundamental network design problems and is
a common generalization of the prize-collecting Steiner tree and the
$k$-minimum spanning tree problems. Our main result is a 2-approximation
algorithm, which improves on the currently best known approximation factor of
3.96 and has a faster running time. The algorithm builds on a modification of
the primal-dual framework of Goemans and Williamson, and reveals interesting
properties that can be applied to other similar problems.

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 226,515 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible