Top 10 Arxiv Papers Today in Data Structures And Algorithms


2.005 Mikeys
#1. The Complexity of Partial Function Extension for Coverage Functions
Umang Bhaskar, Gunjan Kumar
Coverage functions are an important subclass of submodular functions, finding applications in machine learning, game theory, social networks, and facility location. We study the complexity of partial function extension to coverage functions. That is, given a partial function consisting of a family of subsets of $[m]$ and a value at each point, does there exist a coverage function defined on all subsets of $[m]$ that extends this partial function? Partial function extension is previously studied for other function classes, including boolean functions and convex functions, and is useful in many fields, such as obtaining bounds on learning these function classes. We show that determining extendibility of a partial function to a coverage function is NP-complete, establishing in the process that there is a polynomial-sized certificate of extendibility. The hardness also gives us a lower bound for learning coverage functions. We then study two natural notions of approximate extension, to account for errors in the data set. The...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/18 [2] The Complexity of Partial Function Extension for Coverage Functions (https://t.co/Jp6QOCC0IE)
DO: The Complexity of Partial Function Extension for Coverage Functions. https://t.co/QygWr1INtt
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#2. On the m-eternal Domination Number of Cactus Graphs
Václav Blažej, Jan Matyáš Křišťan, Tomáš Valla
Given a graph $G$, guards are placed on vertices of $G$. Then vertices are subject to an infinite sequence of attacks so that each attack must be defended by a guard moving from a neighboring vertex. The m-eternal domination number is the minimum number of guards such that the graph can be defended indefinitely. In this paper we study the m-eternal domination number of cactus graphs, that is, connected graphs where each edge lies in at most two cycles, and we consider three variants of the m-eternal domination number: first variant allows multiple guards to occupy a single vertex, second variant does not allow it, and in the third variant additional "eviction" attacks must be defended. We provide a new upper bound for the m-eternal domination number of cactus graphs, and for a subclass of cactus graphs called Christmas cactus graphs, where each vertex lies in at most two cycles, we prove that these three numbers are equal. Moreover, we present a linear-time algorithm for computing them.
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/19 [3] On the m-eternal Domination Number of Cactus Graphs (https://t.co/LSqt0oNz1q)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#3. Efficient computation of the Jacobi symbol
Niels Möller
The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time GCD algorithms (Euclid, Lehmer) and subquadratic algorithms (Knuth, Sch\"onhage, M\"oller), the additional cost is linear, roughly one table lookup per quotient in the quotient sequence. This method was used for the 2010 rewrite of the Jacobi symbol computation in GMP.
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/19 [5] Efficient computation of the Jacobi symbol (https://t.co/zrM9eEym8y)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#4. Sensitive Distance and Reachability Oracles for Large Batch Updates
Jan van den Brand, Thatchaphol Saranurak
In the sensitive distance oracle problem, there are three phases. We first preprocess a given directed graph $G$ with $n$ nodes and integer weights from $[-W,W]$. Second, given a single batch of $f$ edge insertions and deletions, we update the data structure. Third, given a query pair of nodes $(u,v)$, return the distance from $u$ to $v$. In the easier problem called sensitive reachability oracle problem, we only ask if there exists a directed path from $u$ to $v$. Our first result is a sensitive distance oracle with $\tilde{O}(Wn^{\omega+(3-\omega)\mu})$ preprocessing time, $\tilde{O}(Wn^{2-\mu}f^{2}+Wnf^{\omega})$ update time, and $\tilde{O}(Wn^{2-\mu}f+Wnf^{2})$ query time where the parameter $\mu\in[0,1]$ can be chosen. The data-structure requires $O(Wn^{2+\mu} \log n)$ bits of memory. This is the first algorithm that can handle $f\ge\log n$ updates. Previous results (e.g. [Demetrescu et al. SICOMP'08; Bernstein and Karger SODA'08 and FOCS'09; Duan and Pettie SODA'09; Grandoni and Williams FOCS'12]) can handle at most 2...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/19 [2] Sensitive Distance and Reachability Oracles for Large Batch Updates (https://t.co/dscK3AEnkz)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#5. Stack sorting with restricted stacks
Giulio Cerbai, Anders Claesson, Luca Ferrari
The (classical) problem of characterizing and enumerating permutations that can be sorted using two stacks connected in series is still largely open. In the present paper we address a related problem, in which we impose restrictions both on the procedure and on the stacks. More precisely, we consider a greedy algorithm where we perform the rightmost legal operation (here "rightmost" refers to the usual representation of stack sorting problems). Moreover, the first stack is required to be $\sigma$-avoiding, for some permutation $\sigma$, meaning that, at each step, the elements maintained in the stack avoid the pattern $\sigma$ when read from top to bottom. Since the set of permutations which can be sorted by such a device (which we call $\sigma$-machine) is not always a class, it would be interesting to understand when it happens. We will prove that the set of $\sigma$-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we will analyze two specific $\sigma$-machines in full...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/19 [1] Stack sorting with restricted stacks (https://t.co/qTAv6qIomR)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

2.004 Mikeys
#6. Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani
We consider the problem of approximately solving constraint satisfaction problems with arity $k > 2$ ($k$-CSPs) on instances satisfying certain expansion properties, when viewed as hypergraphs. Random instances of $k$-CSPs, which are also highly expanding, are well-known to be hard to approximate using known algorithmic techniques (and are widely believed to be hard to approximate in polynomial time). However, we show that this is not necessarily the case for instances where the hypergraph is a high-dimensional expander. We consider the spectral definition of high-dimensional expansion used by Dinur and Kaufman [FOCS 2017] to construct certain primitives related to PCPs. They measure the expansion in terms of a parameter $\gamma$ which is the analogue of the second singular value for expanding graphs. Extending the results by Barak, Raghavendra and Steurer [FOCS 2011] for 2-CSPs, we show that if an instance of MAX k-CSP over alphabet $[q]$ is a high-dimensional expander with parameter $\gamma$, then it is possible to approximate...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/19 [4] Approximating Constraint Satisfaction Problems on High-Dimensional Expanders (https://t.co/ypDDiJnOO1)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 27420
Unqiue Words: 3929

2.002 Mikeys
#7. Binary Decision Diagrams: from Tree Compaction to Sampling
Julien Clément, Antoine Genitrini
Any Boolean function corresponds with a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a direct acyclic graph (\textsc{dag}) where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (\textsc{robdd}). We propose to revisit the classical compaction process to give a new way of enumerating \textsc{robdd}s of a given size without considering fully expanded trees and the compaction step. Our method also provides an unranking procedure for the set of \textsc{robdd}s. As a by-product we get a random uniform and exhaustive sampler for \textsc{robdd}s for a given number of variables and size. For efficiency our algorithms rely on a precomputation step. Finally, we give some key ideas to extend the approach to other strategies of compaction, in relation with variants of \textsc{bdd}s (namely \textsc{qbdd}s and \textsc{zbdd}s).
more | pdf | html
Figures
Tweets
arxiv_org: Binary Decision Diagrams: from Tree Compaction to Sampling. https://t.co/pDJbb19FGM https://t.co/20VDmA1KPc
okateim: 2019/07/17 [7] Binary Decision Diagrams: from Tree Compaction to Sampling (https://t.co/0cvVAOhI5U)
DrPjenFI: RT @arxiv_org: Binary Decision Diagrams: from Tree Compaction to Sampling. https://t.co/pDJbb19FGM https://t.co/20VDmA1KPc
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11645
Unqiue Words: 2480

2.001 Mikeys
#8. Improved Algorithms for Time Decay Streams
Vladimir Braverman, Harry Lang, Enayat Ullah, Samson Zhou
In the time-decay model for data streams, elements of an underlying data set arrive sequentially with the recently arrived elements being more important. A common approach for handling large data sets is to maintain a \emph{coreset}, a succinct summary of the processed data that allows approximate recovery of a predetermined query. We provide a general framework that takes any offline-coreset and gives a time-decay coreset for polynomial time decay functions. We also consider the exponential time decay model for $k$-median clustering, where we provide a constant factor approximation algorithm that utilizes the online facility location algorithm. Our algorithm stores $\mathcal{O}(k\log(h\Delta)+h)$ points where $h$ is the half-life of the decay function and $\Delta$ is the aspect ratio of the dataset. Our techniques extend to $k$-means clustering and $M$-estimators as well.
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/18 [1] Improved Algorithms for Time Decay Streams (https://t.co/JAS6y7YD1p)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9057
Unqiue Words: 2236

1.999 Mikeys
#9. Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression
Deeksha Adil, Richard Peng, Sushant Sachdeva
Linear regression in $\ell_p$-norm is a canonical optimization problem that arises in several applications, including sparse recovery, semi-supervised learning, and signal processing. Generic convex optimization algorithms for solving $\ell_p$-regression are slow in practice. Iteratively Reweighted Least Squares (IRLS) is an easy to implement family of algorithms for solving these problems that has been studied for over 50 years. However, these algorithms often diverge for p > 3, and since the work of Osborne (1985), it has been an open problem whether there is an IRLS algorithm that is guaranteed to converge rapidly for p > 3. We propose p-IRLS, the first IRLS algorithm that provably converges geometrically for any $p \in [2,\infty).$ Our algorithm is simple to implement and is guaranteed to find a $(1+\varepsilon)$-approximate solution in $O(p^{3.5} m^{\frac{p-2}{2(p-1)}} \log \frac{m}{\varepsilon}) \le O_p(\sqrt{m} \log \frac{m}{\varepsilon} )$ iterations. Our experiments demonstrate that it performs even better than our...
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/17 [1] Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression (https://t.co/ATQDobYAkc)
arxiv_cs_LG: Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression. Deeksha Adil, Richard Peng, and Sushant Sachdeva https://t.co/yrUVg8gSqh
Memoirs: Fast, Provably convergent IRLS Algorithm for p-norm Linear Regression. https://t.co/0ExjFshjYe
Github

Fast IRLS code for solving p-norm regression problems

Repository: pIRLS
User: utoronto-theory
Language: MATLAB
Stargazers: 0
Subscribers: 2
Forks: 0
Open Issues: 0
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9500
Unqiue Words: 2385

1.998 Mikeys
#10. Some Black-box Reductions for Objective-robust Discrete Optimization Problems Based on their LP-Relaxations
Khaled Elbassioni
We consider robust discrete minimization problems where uncertainty is defined by a convex set in the objective. We show how an integrality gap verifier for the linear programming relaxation of the non-robust version of the problem can be used to derive approximation algorithms for the robust version.
more | pdf | html
Figures
None.
Tweets
okateim: 2019/07/17 [5] Some Black-box Reductions for Objective-robust Discrete Optimization Problems Based on their LP-Relaxations (https://t.co/sYiA37Xutn)
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 9890
Unqiue Words: 1928

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 160,428 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 160,428 papers.