Daniel Berend
YOU?
Author Swipe
View article: On a Conjecture of Schilling Regarding the Coupon Collector's Problem
On a Conjecture of Schilling Regarding the Coupon Collector's Problem Open
This article addresses a conjecture by Schilling concerning the optimality of the uniform distribution in the generalized Coupon Collector's Problem (CCP) where, in each round, a subset (package) of $s$ coupons is drawn from a total of $n$…
View article: Density modulo 1 and Hardy fields
Density modulo 1 and Hardy fields Open
In this article we extend Boshernitzan’s result on density modulo 1 of sequences arising from functions belonging to a Hardy field. We also merge these results with Furstenberg’s ×2×3 theorem. We prove, for example, that, given a vector f …
View article: A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring
A Greedy Probabilistic Heuristic for Graph Black-and-White Anticoloring Open
Given a graph $G$ and positive integers $b$ and $w$, the Black-and-White Coloring problem asks about the existence of a partial vertex-coloring of $G$, with $b$ vertices colored black and $w$ white, such that there is no edge between a bla…
View article: Exceptional Points for Density Modulo 1
Exceptional Points for Density Modulo 1 Open
It is well known that almost every dilation of a sequence of real numbers, that diverges to $\infty$, is dense modulo~1. This paper studies the exceptional set of points -- those for which the dilation is not dense. Specifically, we consid…
View article: Exact expressions for the maximal probability that all $k$-wise independent bits are 1
Exact expressions for the maximal probability that all $k$-wise independent bits are 1 Open
Let $M(n, k, p)$ denote the maximum probability of the event $X_1 = X_2 = \cdots = X_n=1$ under a $k$-wise independent distribution whose marginals are Bernoulli random variables with mean $p$. A long-standing question is to calculate $M(n…
View article: Simultaneous visibility in the integer lattice
Simultaneous visibility in the integer lattice Open
Two lattice points are visible from one another if there is no lattice point on the open line segment joining them. Let $S$ be a finite subset of $\mathbb{Z}^k$. The asymptotic density of the set of lattice points, visible from all points …
View article: Fast Simulations of the Multi-Album Collector
Fast Simulations of the Multi-Album Collector Open
Our starting point is the coupon collector's problem. In this problem, there are $n$ coupons that are drawn uniformly randomly with replacement. The question is how many drawings on average are needed to collect at least one copy (or some …
View article: The Time for Reconstructing the Attack Graph in DDoS Attacks
The Time for Reconstructing the Attack Graph in DDoS Attacks Open
Despite their frequency, denial-of-service (DoS\blfootnote{Denial of Service (DoS), Distributed Denial of Service (DDoS), Probabilistic Packet Marking (PPM), coupon collector's problem (CCP)}) and distributed-denial-of-service (DDoS) attac…
View article: Algorithms for Reconstructing DDoS Attack Graphs using Probabilistic Packet Marking
Algorithms for Reconstructing DDoS Attack Graphs using Probabilistic Packet Marking Open
DoS and DDoS attacks are widely used and pose a constant threat. Here we explore Probability Packet Marking (PPM), one of the important methods for reconstructing the attack-graph and detect the attackers. We present two algorithms. Differ…
View article: Consecutive Ratios in Second-Order Linear Recurrence Sequences
Consecutive Ratios in Second-Order Linear Recurrence Sequences Open
Let ( a n ) n=0 ∞ be a second-order linear recurrence sequence with constant coefficient. We study the limit points and asymptotic distribution of the sequence of consecutive ratios a n +1 / a n .
View article: Maximum of exponential random variables, Hurwitz's zeta function, and the partition function
Maximum of exponential random variables, Hurwitz's zeta function, and the partition function Open
A natural problem in the context of the coupon collector's problem is the behavior of the maximum of independent geometrically distributed random variables (with distinct parameters). This question has been addressed by Brennan et al. (Bri…
View article: On Biased Random Walks, Corrupted Intervals, and Learning Under\n Adversarial Design
On Biased Random Walks, Corrupted Intervals, and Learning Under\n Adversarial Design Open
We tackle some fundamental problems in probability theory on corrupted random\nprocesses on the integer line. We analyze when a biased random walk is expected\nto reach its bottommost point and when intervals of integer points can be\ndete…
View article: Effect of Initial Assignment on Local Search Performance for Max Sat
Effect of Initial Assignment on Local Search Performance for Max Sat Open
In this paper, we explore the correlation between the quality of initial assignments provided to local search heuristics and that of the corresponding final assignments. We restrict our attention to the Max r-Sat problem and to one of the …
View article: A Model of Random Industrial SAT
A Model of Random Industrial SAT Open
One of the most studied models of SAT is random SAT. In this model, instances are composed from clauses chosen uniformly randomly and independently of each other. This model may be unsatisfactory in that it fails to describe various featur…
View article: On the Satisfiability Threshold of Random Community-Structured SAT
On the Satisfiability Threshold of Random Community-Structured SAT Open
For both historical and practical reasons, the Boolean satisfiability problem (SAT) has become one of central importance in computer science. One type of instances arises when the clauses are chosen uniformly randomly \textendash{} random …
View article: An almost mixing of all orders property of algebraic dynamical systems
An almost mixing of all orders property of algebraic dynamical systems Open
We consider dynamical systems, consisting of $\mathbb{Z}^{2}$ -actions by continuous automorphisms on shift-invariant subgroups of $\mathbb{F}_{p}^{\mathbb{Z}^{2}}$ , where $\mathbb{F}_{p}$ is the field of order $p$ . These systems provide…
View article: The Expected Missing Mass under an Entropy Constraint
The Expected Missing Mass under an Entropy Constraint Open
In Berend and Kontorovich (2012), the following problem was studied: A random sample of size t is taken from a world (i.e., probability space) of size n; bound the expected value of the probability of the set of elements not appearing in t…
View article: Exponential vs. Subexponential Tower of Hanoi Variants
Exponential vs. Subexponential Tower of Hanoi Variants Open
We deal here with Tower of Hanoi variants played on digraphs. A major source for such variants is achieved by adding pegs and/or restricting direct moves between certain pairs of pegs. It is natural to represent a variant of this kind by a…