Top 10 Arxiv Papers Today in Data Structures And Algorithms


0.0 Mikeys
#1. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs
Lars Jaffke, Paloma T. Lima
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
Figures
None.
Tweets
ComputerPapers: A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. https://t.co/znaP1SGAta
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8522
Unqiue Words: 1516

0.0 Mikeys
#2. A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest
Neil Olver, Frans Schalekamp, Suzanne van der Ster, Leen Stougie, Anke van Zuylen
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
Figures
None.
Tweets
ComputerPapers: A Duality Based 2-Approximation Algorithm for Maximum Agreement Forest. https://t.co/h5pRHTzcWo
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 17622
Unqiue Words: 2562

0.0 Mikeys
#3. Distributed Triangle Detection via Expander Decomposition
Yi-Jun Chang, Seth Pettie, Hengjie Zhang
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 16055
Unqiue Words: 3127

0.0 Mikeys
#4. On Euclidean Methods for Cubic and Quartic Jacobi Symbols
Eric Bach, Bryce Sandlund
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 7209
Unqiue Words: 2171

0.0 Mikeys
#5. MISSION: Ultra Large-Scale Feature Selection using Count-Sketches
Amirali Aghazadeh, Ryan Spring, Daniel LeJeune, Gautam Dasarathy, Anshumali Shrivastava, Richard G. Baraniuk
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
Figures
None.
Tweets
Github

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

Repository: MISSION
User: rdspring1
Language: C++
Stargazers: 3
Subscribers: 3
Forks: 1
Open Issues: 0
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 6
Total Words: 8909
Unqiue Words: 2607

0.0 Mikeys
#6. Turning Cliques into Paths to Achieve Planarity
Patrizio Angelini, Peter Eades, Seok-Hee Hong, Karsten Klein, Stephen Kobourov, Giuseppe Liotta, Alfredo Navarra, Alessandra Tappini
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
Figures
None.
Tweets
ComputerPapers: Turning Cliques into Paths to Achieve Planarity. https://t.co/cxQEwhZqcR
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 8
Total Words: 5352
Unqiue Words: 1235

0.0 Mikeys
#7. A deterministic polynomial kernel for Odd Cycle Transversal and Vertex Multiway Cut in planar graphs
Bart M. P. Jansen, Marcin Pilipczuk, Erik Jan van Leeuwen
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
Figures
None.
Tweets
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
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 27270
Unqiue Words: 3513

0.0 Mikeys
#8. Approximating optimal transport with linear programs
Kent Quanrud
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
Figures
None.
Tweets
ComputerPapers: Approximating optimal transport with linear programs. https://t.co/BVu4gOrcj6
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 4021
Unqiue Words: 1115

0.0 Mikeys
#9. Independent Sets in Vertex-Arrival Streams
Graham Cormode, Jacques Dark, Christian Konrad
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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11440
Unqiue Words: 2476

0.0 Mikeys
#10. Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
Karl Bringmann, Bhaskar Ray Chaudhury
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
Figures
None.
Tweets
ComputerPapers: Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS. https://t.co/FJNYFXDDZe
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 10034
Unqiue Words: 2325

About

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.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 72,893 papers.