Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFinding Hidden Cliques of Size sqrt{N/e} in Nearly Linear Time
383
0
0.0
(
0
)
Added by
Yash Deshpande
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Consider an Erdos-Renyi random graph in which each edge is present independently with probability 1/2, except for a subset $sC_N$ of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The best known algorithm provably finds the clique in linear time with high probability, provided $|sC_N|ge 1.261sqrt{N}$ cite{dekel2011finding}. Spectral methods can be shown to fail on cliques smaller than $sqrt{N}$. In this paper we describe a nearly linear time algorithm that succeeds with high probability for $|sC_N|ge (1+eps)sqrt{N/e}$ for any $eps>0$. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on $N$ vertices). For large girth regular graphs of degree $(Delta+1)$ we prove that `local algorithms succeed if $|sC_N|ge (1+eps)N/sqrt{eDelta}$ and fail if $|sC_N|le(1-eps)N/sqrt{eDelta}$.
rate research
Read More
In this paper, new techniques that allow conditional entropy to estimate the combinatorics of symbols are applied to animal communication studies to estimate the communications repertoire size. By using the conditional entropy estimates at multiple orders, the paper estimates the total repertoire sizes for animal communication across bottlenose dolphins, humpback whales, and several species of birds for N-grams length one to three. In addition to discussing the impact of this method on studies of animal communication complexity, the reliability of these estimates is compared to other methods through simulation. While entropy does undercount the total repertoire size due to rare N-grams, it gives a more accurate picture of the most frequently used repertoire than just repertoire size alone.
Let ${X_n}_{n=0}^{infty}$ be a stationary real-valued time series with unknown distribution. Our goal is to estimate the conditional expectation of $X_{n+1}$ based on the observations $X_i$, $0le ile n$ in a strongly consistent way. Bailey and Ryabko proved that this is not possible even for ergodic binary time series if one estimates at all values of $n$. We propose a very simple algorithm which will make prediction infinitely often at carefully selected stopping times chosen by our rule. We show that under certain conditions our procedure is strongly (pointwise) consistent, and $L_2$ consistent without any condition. An upper bound on the growth of the stopping times is also presented in this paper.
Transfer entropy (TE) was introduced by Schreiber in 2000 as a measurement of the predictive capacity of one stochastic process with respect to another. Originally stated for discrete time processes, we expand the theory in line with recent work of Spinney, Prokopenko, and Lizier to define TE for stochastic processes indexed over a compact interval taking values in a Polish state space. We provide a definition for continuous time TE using the Radon-Nikodym Theorem, random measures, and projective limits of probability spaces. As our main result, we provide necessary and sufficient conditions to obtain this definition as a limit of discrete time TE, as well as illustrate its application via an example involving Poisson point processes. As a derivative of continuous time TE, we also define the transfer entropy rate between two processes and show that (under mild assumptions) their stationarity implies a constant rate. We also investigate TE between homogeneous Markov jump processes and discuss some open problems and possible future directions.
Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on the sparsifier size are not known, mainly because the hypergraph Laplacian is non-linear, and thus lacks the linear-algebraic structure and tools that have been so effective for graphs. Our main contribution is the first algorithm for constructing $epsilon$-spectral sparsifiers for hypergraphs with $O^*(n)$ hyperedges, where $O^*$ suppresses $(epsilon^{-1} log n)^{O(1)}$ factors. This bound is independent of the rank $r$ (maximum cardinality of a hyperedge), and is essentially best possible due to a recent bit complexity lower bound of $Omega(nr)$ for hypergraph sparsification. This result is obtained by introducing two new tools. First, we give a new proof of spectral concentration bounds for sparsifiers of graphs; it avoids linear-algebraic methods, replacing e.g.~the usual application of the matrix Bernstein inequality and therefore applies to the (non-linear) hypergraph setting. To achieve the result, we design a new sequence of hypergraph-dependent $epsilon$-nets on the unit sphere in $mathbb{R}^n$. Second, we extend the weight assignment technique of Chen, Khanna and Nagda [FOCS20] to the spectral sparsification setting. Surprisingly, the number of spanning trees after the weight assignment can serve as a potential function guiding the reweighting process in the spectral setting.
We prove large (and moderate) deviations for a class of linear combinations of spacings generated by i.i.d. exponentially distributed random variables. We allow a wide class of coefficients which can be expressed in terms of continuous functions defined on [0, 1] which satisfy some suitable conditions. In this way we generalize some recent results by Giuliano et al. (2015) which concern the empirical cumulative entropies defined in Di Crescenzo and Longobardi (2009a).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
