Quantum Chebyshev's Inequality and Applications

DOI10.4230/LIPIcs.ICALP.2019.69OpenAlexW4394788937MaRDI QIDQ5091227

Yassine Hamoudi, Frédéric Magniez

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1807.06456

zbMATH Keywords

Monte Carlo methodquantum algorithmsapproximation algorithmsstreaming algorithmssubgraph countingsublinear-time algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items (1)

Quantum algorithms for learning Walsh spectra of multi-output Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exponential separation of quantum and classical online space complexity
• Pseudorandom quantum states
• Random generation of combinatorial structures from a uniform distribution
• The space complexity of approximating the frequency moments
• Quantum summation with an application to integration.
• The quantum query complexity of approximating the median and related statistics
• Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
• A Tight Lower Bound for High Frequency Moment Estimation with Small Error
• The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• On Testing Expansion in Bounded-Degree Graphs
• Counting Stars and Other Small Subgraphs in Sublinear-Time
• Taylor Polynomial Estimator for Estimating Frequency Moments
• Adaptive simulated annealing: A near-optimal connection between sampling and counting
• Approximating average parameters of graphs
• Time/Space Trade-Offs for Reversible Computation
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Approximately Counting Triangles in Sublinear Time
• Tight Bounds for Testing Bipartiteness in General Graphs
• An Optimal Algorithm for Monte Carlo Estimation
• A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
• Augmented Index and Quantum Streaming Algorithms for DYCK(2)
• Recognizing Well-Parenthesized Expressions in the Streaming Model
• On approximating the number of k-cliques in sublinear time
• Testing conditional independence of discrete distributions
• Quantum Algorithms for Testing Properties of Distributions
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Quantum speedup of Monte Carlo methods
• Introduction to Property Testing
• Optimal Algorithms for Testing Closeness of Discrete Distributions
• Testing Closeness of Discrete Distributions
• Tight bounds for distributed functional monitoring
• Adiabatic Quantum State Generation
• On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
• Streaming Algorithms via Precision Sampling

This page was built for publication: Quantum Chebyshev's Inequality and Applications