Concentration of Measure for the Analysis of Randomized Algorithms
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Even the easiest(?) Graph coloring problem is not easy in streaming!
- Triangle-covered graphs: algorithms, complexity, and structure
- Mutual inhibition with few inhibitory cells via nonlinear inhibitory synaptic interaction
- Exploring multi-layered networks through random walks: bridging offline optimization and online learning
- Randomized diffusion for indivisible loads
- Runtime analysis of probabilistic programs with unbounded recursion
- A note on a Bernstein-type inequality for the log-likelihood function of categorical variables with infinitely many levels
- scientific article; zbMATH DE number 5764927 (Why is no real title available?)
- Push is Fast on Sparse Random Graphs
- Direct search based on probabilistic descent
- Broadcasting competitively against adaptive adversary in multi-channel radio networks
- Softening the impact of collisions in contention resolution
- Tight Hamilton cycles with high discrepancy
- Full rainbow matchings in graphs and hypergraphs
- An analysis of the superiorization method via the principle of concentration of measure
- Distributed (+1)-coloring via ultrafast graph shattering
- Equilibria of greedy combinatorial auctions
- The number of collisions for the occupancy problem with unequal probabilities
- Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming
- Book review of: D. P. Dubhashi and A. Panconesi, Concentration of measure for the analysis of randomized algorithms.
- The cook-book approach to the differential equation method
- Knapsack secretary with bursty adversary
- Possible values for the nonlinearity of de Bruijn feedback functions
- Online load balancing with general reassignment cost
- Phase Transition of a Non-linear Opinion Dynamics with Noisy Interactions
- Parallel load balancing on constrained client-server topologies
- Online max-min fair allocation
- Learning hierarchically-structured concepts
- On the method of typical bounded differences
- Concentration of submodular functions and read-k families under negative dependence
- The Communication Complexity of Distributed epsilon-Approximations
- Global majority consensus by local majority polling on graphs of a given degree sequence
- The set of solutions of random XORSAT formulae
- Limit theory for the Gilbert graph
- Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations
- Concentration inequalities for nonlinear matroid intersection
- Tight time-space lower bounds for finding multiple collision pairs and their applications
- Malicious security for PIR (almost) for free
- Learning hurdles for sleeping experts
- Even faster knapsack via rectangular monotone min-plus convolution and balancing
- An optimal randomized algorithm for finding the saddlepoint
- Upper tails for arithmetic progressions in random subsets
- Superfast coloring in CONGEST via efficient color sampling
- Universality of random permutations
- Upper tail analysis of bucket sort and random tries
- Superfast coloring in CONGEST via efficient color sampling
- Upper tail analysis of bucket sort and random tries
- Rumor spreading: A trigger for proliferation or fading away
- Plus strategies are exponentially slower for planted optima of random height
- Increasing and other subsequence problems for random interval sequences
- Explosive percolation in Erdős-Rényi-like random graph processes
- Multiple random walks on graphs: mixing few to cover many
- Universality of random graphs and rainbow embedding
- On concentration inequalities and their applications for Gibbs measures in lattice systems
- Rademacher learning rates for iterated random functions
- Approximation of classifiers by deep perceptron networks
- Decremental matching in general weighted graphs
- Coin Flipping Cannot Shorten Arithmetic Computations
- Partial sorting problem on evolving data
- Supersaturation in posets and applications involving the container method
- Tight bounds for the subspace sketch problem with applications
- On the spread of influence in graphs
- An instance-based algorithm for deciding the bias of a coin
- Estimating the longest increasing sequence in polylogarithmic time
- The Kőnig graph process
- Bitcoin as a Transaction Ledger: A Composable Treatment
- Who are you? Secure identities in single hop ad hoc networks
- Average distance in a general class of scale-free networks
- Improved direct product theorems for randomized query complexity
- A simple ant colony optimizer for stochastic shortest path problems
- Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
- The loss of serving in the dark
- The communication complexity of set intersection and multiple equality testing
- Fast primal-dual distributed algorithms for scheduling and matching problems
- Secrecy results for compound wiretap channels
- Ultra-fast load balancing on scale-free networks
- A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
- An Improved Bound for Random Binary Search Trees with Concurrent Insertions
- Gaussian concentration bounds for probabilistic cellular automata
- scientific article; zbMATH DE number 7650078 (Why is no real title available?)
- Random walks in polytopes and negative dependence
- (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
- Topics and Techniques in Distribution Testing: A Biased but Representative Sample
- Input locality and hardness amplification
- Communication-efficient distributed covariance sketch, with application to distributed PCA
- Some implications of interval approach to dimension for network complexity
- Mutation, Sexual Reproduction and Survival in Dynamic Environments
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Revisiting frequency moment estimation in random order streams
- I/O-efficient similarity join
- Improved approximation of linear threshold functions
- Anomaly Detection and Classification for Streaming Data using PDEs
- Fraud detection for random walks
- Minimizing locality of one-way functions via semi-private randomized encodings
- Bottom-up rebalancing binary search trees by flipping a coin
- The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time
- Distributed coloring algorithms for triangle-free graphs
- Faster counting and sampling algorithms using colorful decision oracle
- Singletons for simpletons revisiting windowed backoff with Chernoff bounds
- Greedy matching: guarantees and limitations
This page was built for publication: Concentration of Measure for the Analysis of Randomized Algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896979)
