On testing expansion in bounded-degree graphs
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1559556 (Why is no real title available?)
- scientific article; zbMATH DE number 1418268 (Why is no real title available?)
- A sublinear bipartiteness tester for bounded degree graphs
- An Expansion Tester for Bounded Degree Graphs
- Eigenvalues and expanders
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
Cited in
(62)- Improving and extending the testing of distributions for shape-restricted properties
- An expansion tester for bounded degree graphs
- Self-Stabilizing and Self-Organizing Virtual Infrastructures for Mobile Networks
- Two Party Distribution Testing: Communication and Security
- Dynamic complexity of expansion
- Statistical fault attacks on nonce-based authenticated encryption schemes
- The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
- Testing the expansion of a graph
- Testing monotone high‐dimensional distributions
- Separating sublinear time computations by approximate diameter
- Zero-knowledge proofs of proximity
- An adaptivity hierarchy theorem for property testing
- Testing \(k\)-edge-connectivity of digraphs
- Testing small set expansion in general graphs
- Testing probability distributions using conditional samples
- Testing monotone continuous distributions on high-dimensional real cubes
- Sublinear algorithms in the external memory model
- Motif estimation via subgraph sampling: the fourth-moment phenomenon
- Hypothesis testing for densities and high-dimensional multinomials: sharp local minimax rates
- Separating Sublinear Time Computations by Approximate Diameter
- A two-sided error distributed property tester for conductance
- Testing Data Binnings
- Optimal stopping rules for sequential hypothesis testing
- Concentration of the collision estimator
- Learning and testing irreducible Markov chains via the k-cover time
- Testing product distributions: a closer look
- Quantum Chebyshev's Inequality and Applications
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- Orion: zero knowledge proof with linear prover time
- Sample efficient identity testing and independence testing of quantum states
- scientific article; zbMATH DE number 1775414 (Why is no real title available?)
- Proofs of proximity for distribution testing
- Sampling correctors
- Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
- Analysis of COVID-19 evolution based on testing closeness of sequential data
- Testing Expansion in Bounded-Degree Graphs
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- An automatic inequality prover and instance optimal identity testing
- Distributed Testing of Graph Isomorphism in the CONGEST Model.
- Sublinear time algorithms for earth mover's distance
- Invariance in property testing
- Property testing on \(k\)-vertex-connectivity of graphs
- Recovering structured probability matrices
- Well-mixing vertices and almost expanders
- Testing outerplanarity of bounded degree graphs
- Empirical distribution of equilibrium play and its testing application
- Bounds on the size of test sets for sorting and related networks
- Renyi entropy estimation revisited
- Testing distributional assumptions of learning algorithms
- Distribution-free connectivity testing for sparse graphs
- Distribution testing with a confused collector
- An Expansion Tester for Bounded Degree Graphs
- Estimating the number of connected components in a graph via subgraph sampling
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Every minor-closed property of sparse graphs is testable
- Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
- Testing shape restrictions of discrete distributions
- Improved bounds for high-dimensional equivalence and product testing using subcube queries
- Support testing in the huge object model
- Refining the adaptivity notion in the huge object model
- Quantum property testing for bounded-degree graphs
- scientific article; zbMATH DE number 7525446 (Why is no real title available?)
This page was built for publication: On testing expansion in bounded-degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088177)
