### Top 10 Arxiv Papers Today in Data Structures And Algorithms

##### #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
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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
okateim: 2019/07/19 [3] On the m-eternal Domination Number of Cactus Graphs (https://t.co/LSqt0oNz1q)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
okateim: 2019/07/19 [5] Efficient computation of the Jacobi symbol (https://t.co/zrM9eEym8y)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
okateim: 2019/07/19 [2] Sensitive Distance and Reachability Oracles for Large Batch Updates (https://t.co/dscK3AEnkz)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
okateim: 2019/07/19 [1] Stack sorting with restricted stacks (https://t.co/qTAv6qIomR)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

##### #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
None.
###### Tweets
okateim: 2019/07/19 [4] Approximating Constraint Satisfaction Problems on High-Dimensional Expanders (https://t.co/ypDDiJnOO1)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 27420
Unqiue Words: 3929

##### #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
###### 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
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 11645
Unqiue Words: 2480

##### #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
None.
###### Tweets
okateim: 2019/07/18 [1] Improved Algorithms for Time Decay Streams (https://t.co/JAS6y7YD1p)
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9057
Unqiue Words: 2236

##### #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
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
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9500
Unqiue Words: 2385

##### #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
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)
None.
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
Online
###### Stats
Tracking 160,428 papers.