A $b$-coloring of a graph $G$ is a proper coloring of its vertices such that
each color class contains a vertex that has at least one neighbor in all the
other color classes. The $b$-chromatic number of a graph $G$, denoted by
$\chi_b(G)$, is the maximum number $k$ such that $G$ admits a $b$-coloring with
$k$ colors. We consider the complexity of the problem of deciding whether a
graph $G$ has a $b$-coloring with $k$ colors, whenever the value of $k$ is
close to one of two upper bounds on $\chi_b(G)$: The maximum degree $\Delta(G)$
plus one, and the $m$-degree, denoted by $m(G)$, which is defined as the
maximum number $i$ such that $G$ has $i$ vertices of degree at least $i-1$. We
obtain a dichotomy result stating that for fixed $k \in \{\Delta(G) + 1 - p,
m(G) - p\}$, the problem is polynomial-time solvable whenever $p \in \{0, 1\}$
and, even when $k = 3$, it is NP-complete whenever $p \ge 2$. We furthermore
give an FPT-algorithm parameterized by $k + \ell$, where $\ell$ denotes the
number of vertices of degree at least $k$,...

more |
pdf
| html
None.

ComputerPapers:
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. https://t.co/znaP1SGAta

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 8522

Unqiue Words: 1516

We give a 2-approximation algorithm for the Maximum Agreement Forest problem
on two rooted binary trees. This NP-hard problem has been studied extensively
in the past two decades, since it can be used to compute the rooted Subtree
Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm
is combinatorial and its running time is quadratic in the input size. To prove
the approximation guarantee, we construct a feasible dual solution for a novel
linear programming formulation. In addition, we show this linear program is
stronger than previously known formulations, and we give a compact formulation,
showing that it can be solved in polynomial time

more |
pdf
| html
None.

ComputerPapers:
A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. https://t.co/h5pRHTzcWo

None.

None.

Sample Sizes : None.

Authors: 5

Total Words: 17622

Unqiue Words: 2562

We present improved distributed algorithms for triangle detection and its
variants in the CONGEST model. We show that Triangle Detection, Counting, and
Enumeration can be solved in $\tilde{O}(n^{1/2})$ rounds. In contrast, the
previous state-of-the-art bounds for Triangle Detection and Enumeration were
$\tilde{O}(n^{2/3})$ and $\tilde{O}(n^{3/4})$, respectively, due to Izumi and
LeGall (PODC 2017).
The main technical novelty in this work is a distributed graph partitioning
algorithm. We show that in $\tilde{O}(n^{1-\delta})$ rounds we can partition
the edge set of the network $G=(V,E)$ into three parts $E=E_m\cup E_s\cup E_r$
such that
(a) Each connected component induced by $E_m$ has minimum degree
$\Omega(n^\delta)$ and conductance $\Omega(1/\text{poly} \log(n))$. As a
consequence the mixing time of a random walk within the component is
$O(\text{poly} \log(n))$.
(b) The subgraph induced by $E_s$ has arboricity at most $n^{\delta}$.
(c) $|E_r| \leq |E|/6$.
All of our algorithms are based on the following generic...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 16055

Unqiue Words: 3127

We study the bit complexity of two methods, related to the Euclidean
algorithm, for computing cubic and quartic analogs of the Jacobi symbol. The
main bottleneck in such procedures is computation of a quotient for long
division. We give examples to show that with standard arithmetic, if quotients
are computed naively (by using exact norms as denominators, then rounding), the
algorithms have $\Theta(n^3)$ bit complexity. It is a "folk theorem" that this
can be reduced to $O(n^2)$ by modifying the division procedure. We give a
self-contained proof of this, and show that quadratic time is best possible for
these algorithms (with standard arithmetic or not).
We also address the relative efficiency of using reciprocity, as compared to
Euler's criterion, for testing if a given number is a cubic or quartic residue
modulo an odd prime. Which is preferable depends on the number of residue tests
to be done.
Finally, we discuss the cubic and quartic analogs of Eisenstein's
even-quotient algorithm for computing Jacobi symbols in ${\bf...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 7209

Unqiue Words: 2171

Feature selection is an important challenge in machine learning. It plays a
crucial role in the explainability of machine-driven decisions that are rapidly
permeating throughout modern society. Unfortunately, the explosion in the size
and dimensionality of real-world datasets poses a severe challenge to standard
feature selection algorithms. Today, it is not uncommon for datasets to have
billions of dimensions. At such scale, even storing the feature vector is
impossible, causing most existing feature selection methods to fail.
Workarounds like feature hashing, a standard approach to large-scale machine
learning, helps with the computational feasibility, but at the cost of losing
the interpretability of features. In this paper, we present MISSION, a novel
framework for ultra large-scale feature selection that performs stochastic
gradient descent while maintaining an efficient representation of the features
in memory using a Count-Sketch data structure. MISSION retains the simplicity
of feature hashing without sacrificing the...

more |
pdf
| html
None.

MISSION: Ultra Large-Scale Feature Selection using Count-Sketches

Stargazers: 3

Subscribers: 3

Subscribers: 3

Forks: 1

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 6

Total Words: 8909

Unqiue Words: 2607

Motivated by hybrid graph representations, we introduce and study the
following beyond-planarity problem, which we call $h$-Clique2Path Planarity:
Given a graph $G$, whose vertices are partitioned into subsets of size at most
$h$, each inducing a clique, remove edges from each clique so that the subgraph
induced by each subset is a path, in such a way that the resulting subgraph of
$G$ is planar. We study this problem when $G$ is a simple topological graph,
and establish its complexity in relation to $k$-planarity. We prove that
$h$-Clique2Path Planarity is NP-complete even when $h=4$ and $G$ is a simple
$3$-plane graph, while it can be solved in linear time, for any $h$, when $G$
is $1$-plane.

more |
pdf
| html
None.

ComputerPapers:
Turning Cliques into Paths to Achieve Planarity. https://t.co/cxQEwhZqcR

None.

None.

Sample Sizes : None.

Authors: 8

Total Words: 5352

Unqiue Words: 1235

We show that Odd Cycle Transversal and Vertex Multiway Cut admit
deterministic polynomial kernels when restricted to planar graphs and
parameterized by the solution size. This answers a question of Saurabh. On the
way to these results, we provide an efficient sparsification routine in the
flavor of the sparsification routine used for the Steiner Tree problem in
planar graphs (FOCS 2014). It differs from the previous work because it
preserves the existence of low-cost subgraphs that are not necessarily Steiner
trees in the original plane graph, but structures that turn into (supergraphs
of) Steiner trees after adding all edges between pairs of vertices that lie on
a common face. We also show connections between Vertex Multiway Cut and the
Vertex Planarization problem, where the existence of a polynomial kernel
remains an important open problem.

more |
pdf
| html
None.

M157q_News_RSS:
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs. (arXiv:1810.01136v2 [cs.DS] UPDATED)
https://t.co/jlKyQeoLv8
We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to

ComputerPapers:
A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs. https://t.co/ESUPKmJM1X

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 27270

Unqiue Words: 3513

In the regime of bounded transportation costs, additive approximations for
the optimal transport problem are reduced (rather simply) to relative
approximations for positive linear programs, resulting in faster additive
approximation algorithms for optimal transport.

more |
pdf
| html
None.

ComputerPapers:
Approximating optimal transport with linear programs. https://t.co/BVu4gOrcj6

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 4021

Unqiue Words: 1115

We consider the classic maximal and maximum independent set problems in three
models of graph streams:
In the edge-arrival model we see a stream of edges which collectively define
a graph, this model has been well-studied for a variety of problems. We first
show that the space complexity for a one-pass streaming algorithm to find a
maximal independent set is quadratic (i.e. we must store all edges). We further
show that the problem does not become much easier if we only require
approximate maximality.
In the "explicit" vertex stream model, the input stream is a sequence of
vertices making up the graph, where every vertex arrives along with its
incident edges that connect to previously arrived vertices. Various graph
problems require substantially less space to solve in this setting than for
edge-arrival streams. We show that every one-pass $c$-approximation algorithm
for maximum independent set (MIS) on explicit vertex streams requires space
$\Omega(\frac{n^2}{c^7})$, where $n$ is the number of vertices of the input
graph, and...

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 11440

Unqiue Words: 2476

We study sketching and streaming algorithms for the Longest Common
Subsequence problem (LCS) on strings of small alphabet size $|\Sigma|$. For the
problem of deciding whether the LCS of strings $x,y$ has length at least $L$,
we obtain a sketch size and streaming space usage of $\mathcal{O}(L^{|\Sigma| -
1} \log L)$.
We also prove matching unconditional lower bounds.
As an application, we study a variant of LCS where each alphabet symbol is
equipped with a weight that is given as input, and the task is to compute a
common subsequence of maximum total weight. Using our sketching algorithm, we
obtain an $\mathcal{O}(\textrm{min}\{nm, n + m^{{\lvert \Sigma
\rvert}}\})$-time algorithm for this problem, on strings $x,y$ of length $n,m$,
with $n \ge m$. We prove optimality of this running time up to lower order
factors, assuming the Strong Exponential Time Hypothesis.

more |
pdf
| html
None.

ComputerPapers:
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. https://t.co/FJNYFXDDZe

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 10034

Unqiue Words: 2325

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

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible