Balls and bins: A study in negative dependence
From MaRDI portal
Publication:4705326
DOI<99::AID-RSA1>3.0.CO;2-M 10.1002/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-MzbMath0964.60503OpenAlexW1997988698MaRDI QIDQ4705326
Devdatt P. Dubhashi, Desh Ranjan
Publication date: 19 December 1999
Full work available at URL: https://doi.org/10.1002/(sici)1098-2418(199809)13:2<99::aid-rsa1>3.0.co;2-m
Related Items (89)
Ordered binary decision diagrams and the Shannon effect ⋮ Tight bounds for parallel randomized load balancing ⋮ Tail bounds for the height and width of a random tree with a given degree sequence ⋮ Conditional negative association for competing urns ⋮ Determinantal probability measures ⋮ Overlap properties of geometric expanders ⋮ Counting distinct items over update streams ⋮ The structure and complexity of Nash equilibria for a selfish routing game ⋮ Random Walks in Polytopes and Negative Dependence ⋮ Concentration of the collision estimator ⋮ Rapid social connectivity ⋮ Tree/endofunction bijections and concentration inequalities ⋮ Distributed wireless link scheduling in the SINR model ⋮ Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems ⋮ The state complexity of random DFAs ⋮ Domination analysis for minimum multiprocessor scheduling ⋮ Moderate deviations for a nonparametric estimator of sample coverage ⋮ Simple dynamics for plurality consensus ⋮ Corrigendum to: ``Existence of a perfect matching in a random \((1+e^{-1})\)-out bipartite graph ⋮ On combinatorial testing problems ⋮ Walker-Breaker Games ⋮ Phase transition for the mixing time of the Glauber dynamics for coloring regular trees ⋮ A BK inequality for randomly drawn subsets of fixed size ⋮ Deterministic dynamic matching in worst-case update time ⋮ On Bollobás‐Riordan random pairing model of preferential attachment graph ⋮ Biased random k‐SAT ⋮ Haystack hunting hints and locker room communication ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ Thou shalt covet the average of thy neighbors' cakes ⋮ Sequential importance sampling for estimating expectations over the space of perfect matchings ⋮ On Sub-Gaussian Concentration of Missing Mass ⋮ Power of \(k\) choices in the semi-random graph process ⋮ Unnamed Item ⋮ Balanced allocation on hypergraphs ⋮ On the sub-Gaussianity of the missing mass ⋮ Dependence properties of order statistics ⋮ Linear classifiers are nearly optimal when hidden variables have diverse effects ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Random-index oblivious RAM ⋮ Mixing time for the repeated balls into bins dynamics ⋮ On the Power of Statistical Zero Knowledge ⋮ Conditionally negative association resulting from multinomial distribution ⋮ A Bernstein-von Mises theorem for discrete probability distributions ⋮ Less hashing, same performance: Building a better Bloom filter ⋮ Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP ⋮ A simple approach for adapting continuous load balancing processes to discrete settings ⋮ Further developments on sufficient conditions for negative dependence of random variables. ⋮ One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences ⋮ Combinatorial inference for graphical models ⋮ FKG (and Other Inequalities) from (Generalized and Approximate) FK Random Cluster Representation (and Iterated Folding) ⋮ Modified log-Sobolev inequalities for strongly log-concave distributions ⋮ Self-stabilizing repeated balls-into-bins ⋮ Negative Dependence and Srinivasan's Sampling Process ⋮ Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model ⋮ Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ Analysis of randomized protocols for conflict-free distributed access ⋮ Towards a theory of negative dependence ⋮ Complete partitions of graphs ⋮ Searchable Symmetric Encryption: Optimal Locality in Linear Space via Two-Dimensional Balanced Allocations ⋮ Unnamed Item ⋮ Randomized allocation processes ⋮ Asymptotic properties of Turing's formula in relative error ⋮ Bounded size biased couplings, log concave distributions and concentration of measure for occupancy models ⋮ A generalization of multiple choice balls-into-bins: tight bounds ⋮ Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures ⋮ Improved algorithms for latency minimization in wireless networks ⋮ Improved bounds on the sample complexity of learning ⋮ Dispersing hash functions ⋮ Negative correlation and log-concavity ⋮ Negative dependence in the balls and bins experiment with applications to order statistics ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ Negative dependence and the geometry of polynomials ⋮ Superfast coloring in CONGEST via efficient color sampling ⋮ On Erdős–Ko–Rado for random hypergraphs I ⋮ Diverse data selection via combinatorial quasi-concavity of distance covariance: a polynomial time global minimax algorithm ⋮ Negative association, ordering and convergence of resampling methods ⋮ Unnamed Item ⋮ Log concavity and concentration of Lipschitz functions on the Boolean hypercube ⋮ A non-increasing tree growth process for recursive trees and applications ⋮ On the Spread of Random Graphs ⋮ Singletons for simpletons revisiting windowed backoff with Chernoff bounds ⋮ Global lower mass-bound for critical configuration models in the heavy-tailed regime ⋮ Local uniformity properties for glauber dynamics on graph colorings ⋮ Efficient sampling of non-strict turnstile data streams ⋮ Topics and Techniques in Distribution Testing: A Biased but Representative Sample ⋮ Negative Dependence in Sampling ⋮ Tight approximation bounds for maximum multi-coverage ⋮ A model of random industrial SAT
This page was built for publication: Balls and bins: A study in negative dependence