On Testing Expansion in Bounded-Degree Graphs
From MaRDI portal
Publication:3088177
DOI10.1007/978-3-642-22670-0_9zbMath1343.68302OpenAlexW2271854143MaRDI QIDQ3088177
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_9
Related Items
Sampling Correctors, Well-mixing vertices and almost expanders, Motif estimation via subgraph sampling: the fourth-moment phenomenon, An adaptivity hierarchy theorem for property testing, Concentration of the collision estimator, Separating sublinear time computations by approximate diameter, Analysis of COVID-19 evolution based on testing closeness of sequential data, Estimating the number of connected components in a graph via subgraph sampling, The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution, Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu, Statistical Fault Attacks on Nonce-Based Authenticated Encryption Schemes, Unnamed Item, Orion: zero knowledge proof with linear prover time, Property testing on \(k\)-vertex-connectivity of graphs, Unnamed Item, Sublinear time algorithms for earth mover's distance, Testing shape restrictions of discrete distributions, An Automatic Inequality Prover and Instance Optimal Identity Testing, Empirical Distribution of Equilibrium Play and Its Testing Application, On the power of conditional samples in distribution testing, Distribution-free connectivity testing for sparse graphs, Recovering Structured Probability Matrices, Testing \(k\)-edge-connectivity of digraphs, Zero-Knowledge Proofs of Proximity, Proofs of Proximity for Distribution Testing, Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks, Quantum spectrum testing, Testing Data Binnings, Distributed Testing of Graph Isomorphism in the CONGEST Model., Every minor-closed property of sparse graphs is testable, Testing the expansion of a graph, Unnamed Item, Invariance in Property Testing, Testing Monotone Continuous Distributions on High-Dimensional Real Cubes, Sublinear Algorithms in the External Memory Model, Testing monotone high‐dimensional distributions, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Quantum Property Testing for Bounded-Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs, Two Party Distribution Testing: Communication and Security, Quantum Chebyshev's Inequality and Applications, Hypothesis testing for densities and high-dimensional multinomials: sharp local minimax rates, Improving and extending the testing of distributions for shape-restricted properties, Optimal Stopping Rules for Sequential Hypothesis Testing, Separating Sublinear Time Computations by Approximate Diameter, Testing Probability Distributions using Conditional Samples, Dynamic complexity of expansion
Cites Work
