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.

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.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

okateim:
2019/07/19 [3]
On the m-eternal Domination Number of Cactus Graphs (https://t.co/LSqt0oNz1q)

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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.

okateim:
2019/07/19 [5]
Efficient computation of the Jacobi symbol (https://t.co/zrM9eEym8y)

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 0

Unqiue Words: 0

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.

okateim:
2019/07/19 [2]
Sensitive Distance and Reachability Oracles for Large Batch Updates (https://t.co/dscK3AEnkz)

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 0

Unqiue Words: 0

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.

okateim:
2019/07/19 [1]
Stack sorting with restricted stacks (https://t.co/qTAv6qIomR)

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 0

Unqiue Words: 0

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.

okateim:
2019/07/19 [4]
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders (https://t.co/ypDDiJnOO1)

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 27420

Unqiue Words: 3929

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
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.

Sample Sizes : None.

Authors: 2

Total Words: 11645

Unqiue Words: 2480

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.

okateim:
2019/07/18 [1]
Improved Algorithms for Time Decay Streams (https://t.co/JAS6y7YD1p)

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 9057

Unqiue Words: 2236

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.

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

Fast IRLS code for solving p-norm regression problems

Stargazers: 0

Subscribers: 2

Subscribers: 2

Forks: 0

Open Issues: 0

Open Issues: 0

None.

Sample Sizes : None.

Authors: 3

Total Words: 9500

Unqiue Words: 2385

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.

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.

Sample Sizes : None.

Authors: 1

Total Words: 9890

Unqiue Words: 1928

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible