On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
From MaRDI portal
Publication:5470721
DOI10.1137/S0097539704447304zbMath1098.60026MaRDI QIDQ5470721
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Inequalities; stochastic orderings (60E15) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (33)
On triangle estimation using tripartite independent set queries ⋮ Motif estimation via subgraph sampling: the fourth-moment phenomenon ⋮ Separating sublinear time computations by approximate diameter ⋮ On Sampling Edges Almost Uniformly ⋮ The Erdős matching conjecture and concentration inequalities ⋮ Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs ⋮ Unnamed Item ⋮ Approximately Counting Triangles in Sublinear Time ⋮ Marchenko-Pastur law for a random tensor model ⋮ Almost optimal query algorithm for hitting set using a subset query ⋮ Nonnegative \(k\)-sums, fractional covers, and probability of small deviations ⋮ On a Conjecture of Feige for Discrete Log-Concave Distributions ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ On Approximating the Number of $k$-Cliques in Sublinear Time ⋮ Comparing the strength of query types in property testing: the case of \(k\)-colorability ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Level-based analysis of the univariate marginal distribution algorithm ⋮ On the Complexity of Sampling Vertices Uniformly from a Graph ⋮ On monotonicity of Ramanujan function for binomial random variables ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Small deviations of sums of independent random variables ⋮ Sublinear-time Algorithms ⋮ A sharp estimate for probability distributions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Combinatorial anti-concentration inequalities, with applications ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Quantum Chebyshev's Inequality and Applications ⋮ Three convolution inequalities on the real line with connections to additive combinatorics ⋮ Separating Sublinear Time Computations by Approximate Diameter ⋮ Unnamed Item
This page was built for publication: On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
