A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the
vertex set such that every hyperedge contains all $q$ colors.
We prove that given a rainbow $(k - 2\lfloor \sqrt{k}\rfloor)$-colorable
$k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring.
Previously, this was only known for rainbow $\lfloor k/2 \rfloor$-colorable
hypergraphs (Guruswami and Lee, SODA 2015).
We also study a generalization which we call rainbow $(q, p)$-coloring,
defined as a coloring using $q$ colors such that every hyperedge contains at
least $p$ colors. We prove that given a rainbow $(k - \lfloor \sqrt{kc}
\rfloor, k- \lfloor3\sqrt{kc} \rfloor)$-colorable $k$ uniform hypergraph, it is
NP-hard to find a normal $c$-coloring for any constant $c < k/10$.
The proof of our second result relies on two combinatorial theorems. One of
the theorems was proved by Sarkaria (J.~Comb.~Theory.~1990) using topological
methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.

more |
pdf
| html
None.

MathPaper:
Improved Inapproximability of Rainbow Coloring. https://t.co/cKHqAlDqFP

el0j:
https://t.co/2KKULetosz

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 13077

Unqiue Words: 2541

This paper illustrates the power of Gaussian Elimination by adapting it to
Positive 1-in-3-SAT.
We derive a general kernelization method for this problem and thus obtain an
upper bound for the complexity of its counting version of O(2kR 2^{(1-k)R}) for
number of variables R and clauses-to-variables ratio k.
Combining this method with previous results gives a time and space complexity
for the counting problem of O(4/3|V|2^{3|V|/8}) and O(4/3|V|2^{3|V|/16}).

more |
pdf
| html
None.

ComputerPapers:
A Kernel Method for Positive 1-in-3-SAT. https://t.co/6UBSRvb0QN

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 2901

Unqiue Words: 941

We introduce the notions of algorithmic mutual information and rarity of
quantum states. These definitions enjoy conservation inequalities over unitary
transformations and partial traces. We show that a large majority of pure
states have minute self algorithmic information. We provide an algorithmic
variant to the no-cloning theorem, by showing that only a small minority of
quantum pure states can clone a non negligible amount of algorithmic
information. We also provide a chain rule inequality for quantum algorithmic
entropy. We show that rarity does not increase under POVM measurements.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 4725

Unqiue Words: 1247

Divisorial gonality and stable divisorial gonality are graph parameters,
which have an origin in algebraic geometry. Divisorial gonality of a connected
graph $G$ can be defined with help of a chip firing game on $G$. The stable
divisorial gonality of $G$ is the minimum divisorial gonality over all
subdivisions of edges of $G$.
In this paper we prove that deciding whether a given connected graph has
stable divisorial gonality at most a given integer $k$ belongs to the class NP.
Combined with the result that (stable) divisorial gonality is NP-hard by
Gijswijt, we obtain that stable divisorial gonality is NP-complete. The proof
consist of a partial certificate that can be verified by solving an Integer
Linear Programming instance. As a corollary, we have that the number of
subdivisions needed for minimum stable divisorial gonality of a graph with $n$
vertices is bounded by $2^{p(n)}$ for a polynomial $p$.

more |
pdf
| html
None.

M157q_News_RSS:
Stable divisorial gonality is in NP. (arXiv:1808.06921v1 [https://t.co/v2KswNHWZT])
https://t.co/RGFofFAIGT
Divisorial gonality and stable divisorial gonality

MathPaper:
Stable divisorial gonality is in NP. https://t.co/k4i3XR4jUg

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 8082

Unqiue Words: 1317

Polynomial Pigeonhole Principle (PPP) is an important subclass of TFNP with
profound connections to the complexity of the fundamental cryptographic
primitives: collision-resistant hash functions and one-way permutations. In
contrast to most of the other subclasses of TFNP, no complete problem is known
for PPP. Our work identifies the first PPP-complete problem without any circuit
or Turing Machine given explicitly in the input, and thus we answer a
longstanding open question from [Papadimitriou1994]. Specifically, we show that
constrained-SIS (cSIS), a generalized version of the well-known Short Integer
Solution problem (SIS) from lattice-based cryptography, is PPP-complete.
In order to give intuition behind our reduction for constrained-SIS, we
identify another PPP-complete problem with a circuit in the input but closely
related to lattice problems. We call this problem BLICHFELDT and it is the
computational problem associated with Blichfeldt's fundamental theorem in the
theory of lattices.
Building on the inherent connection...

more |
pdf
| html
None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 21937

Unqiue Words: 3762

We investigate the size complexity of proofs in $Res(s)$ -- an extension of
Resolution working on $s$-DNFs instead of clauses -- for families of
contradictions given in the {\em unusual binary} encoding. A motivation of our
work is size lower bounds of refutations in Resolution for families of
contradictions in the usual unary encoding. Our main interest is the $k$-Clique
Principle, whose Resolution complexity is still unknown.
Our main result is a $n^{\Omega(k)}$ lower bound for the size of refutations
of the binary $k$-Clique Principle in $Res(\lfloor \frac{1}{2}\log \log
n\rfloor)$. This improves the result of Lauria, Pudl\'ak et al. [24] who proved
the lower bound for Resolution, that is $Res(1)$.
Our second lower bound proves that in $RES(s)$ for $s\leq
\log^{\frac{1}{2-\epsilon}}(n)$, the shortest proofs of the $BinPHP^m_n$,
requires size $2^{n^{1-\delta}}$, for any $\delta>0$. Furthermore we prove that
$BinPHP^m_n$ can be refuted in size $2^{\Theta(n)}$ in treelike $Res(1)$,
contrasting with the unary case, where...

more |
pdf
| html
None.

ComputerPapers:
Resolution and the binary encoding of combinatorial principles. https://t.co/MnINh3QeoD

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 12434

Unqiue Words: 2521

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any
nonzero polynomial $f(x_1,\ldots, x_n)$ of degree at most $s$ will evaluate to
a nonzero value at some point on a grid $S^n \subseteq \mathbb{F}^n$ with $|S|
> s$. Thus, there is a deterministic polynomial identity test (PIT) for all
degree-$s$ size-$s$ algebraic circuits in $n$ variables that runs in time
$\mathrm{poly}(s) \cdot (s+1)^n$. In a surprising recent result, Agrawal, Ghosh
and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for
degree-$s$, size-$s$, $n$-variate circuits with running time as bad as
$s^{n^{0.5 - \delta}}\mathrm{Huge}(n)$, where $\delta > 0$ and
$\mathrm{Huge}(n)$ is an arbitrary function, can be used to construct blackbox
PIT algorithms for degree-$s$ size $s$ circuits with running time $s^{\exp
\circ \exp (O(\log ^\ast s))}$.
The authors asked if a similar conclusion followed if their hypothesis was
weakened to having deterministic PIT with running time $s^{o(n)}\cdot
\mathrm{Huge}(n)$. In this paper, we...

more |
pdf
| html
None.

ComputerPapers:
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits. https://t.co/7mEaCgrMPQ

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 6252

Unqiue Words: 1567

The diffusion of information has been widely modeled as stochastic diffusion
processes on networks. Alshamsi et al. (2018) proposed a model of strategic
diffusion in networks of related activities. In this work we investigate the
computational aspects of finding the optimal strategy of strategic diffusion.
We prove that finding an optimal solution to the problem is NP-complete in a
general case. To overcome this computational difficulty, we present an
algorithm to compute an optimal solution based on a dynamic programming
technique. We also show that the problem is fixed parameter-tractable when
parametrized by the product of the treewidth and maximum degree. We analyze the
possibility of developing an efficient approximation algorithm and show that
two heuristic algorithms proposed so far cannot have better than a logarithmic
approximation guarantee. Finally, we prove that the problem does not admit
better than a logarithmic approximation, unless P=NP.

more |
pdf
| html
None.

ComputerPapers:
Computational Aspects of Optimal Strategic Network Diffusion. https://t.co/v43QJkyyPd

SRoyLee:
Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s

SRoyLee:
Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s

SRoyLee:
Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s

SRoyLee:
Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s

SRoyLee:
Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s

SRoyLee:
Computational Aspects of Optimal Strategic Network Diffusion - https://t.co/j9kdTkyT9s

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 10930

Unqiue Words: 2077

We show that any DNNF circuit that expresses the set of linear orders over a
set of $n$ candidates must be of size $2^{\Omega(n)}$.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 3464

Unqiue Words: 897

The kth-power of a given graph G=(V,E) is obtained from G by adding an edge
between every two distinct vertices at a distance at most k in G. We call G a
k-Steiner power if it is an induced subgraph of the kth-power of some tree. Our
main contribution is a polynomial-time recognition algorithm of 4-Steiner
powers, thereby extending the decade-year-old results of (Lin, Kearney and
Jiang, ISAAC'00) for k=1,2 and (Chang and Ko, WG'07) for k=3. A graph G is
termed k-leaf power if there is some tree T such that: all vertices in V(G) are
leaf-nodes of T, and G is an induced subgraph of the kth-power of T. As a
byproduct of our main result, we give the first known polynomial-time
recognition algorithm for 6-leaf powers.

more |
pdf
| html
ComputerPapers:
Polynomial-time Recognition of 4-Steiner Powers. https://t.co/d6G0TgjeIs

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 29522

Unqiue Words: 3222

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 72,995 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible