Copertina

Testing Properties of Edge Distributions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Fei, Yumou
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
di: Fei, Yumou
Pubblicazione: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
di: Fei, Yumou, et al.
Pubblicazione: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
di: Putterman, Aaron, et al.
Pubblicazione: (2026)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Computational Complexity in Property Testing
di: Pinto Jr., Renato Ferreira, et al.
Pubblicazione: (2025)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

Matching and Edge Cover in Temporal Graphs
di: Cioni, Lapo, et al.
Pubblicazione: (2025)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
di: Bilò, Davide, et al.
Pubblicazione: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2026)

On the Inapproximability of Finding Minimum Monitoring Edge-Geodetic Sets
di: Bilò, Davide, et al.
Pubblicazione: (2024)

On Optimal Testing of Linearity
di: Arora, Vipul, et al.
Pubblicazione: (2024)

Improved Algorithm for Permutation Testing
di: Zhang, Xiaojin
Pubblicazione: (2020)

Lower Bounds for Convexity Testing
di: Chen, Xi, et al.
Pubblicazione: (2024)

Testing noisy low-degree polynomials for sparsity
di: Bao, Yiqiao, et al.
Pubblicazione: (2025)

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
di: Li, Qian, et al.
Pubblicazione: (2025)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
di: Firbas, Alexander, et al.
Pubblicazione: (2024)

Efficient and Private Property Testing via Indistinguishability
di: Dwork, Cynthia, et al.
Pubblicazione: (2025)

Differentially Private Verification of Distribution Properties
di: Du, Elbert, et al.
Pubblicazione: (2026)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
di: Arvind, V., et al.
Pubblicazione: (2023)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
di: Döring, Simon, et al.
Pubblicazione: (2024)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
di: Yoshida, Yuichi, et al.
Pubblicazione: (2025)

Quantum Property Testing for Bounded-Degree Directed Graphs
di: Peng, Pan, et al.
Pubblicazione: (2026)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
di: de Berg, Mark, et al.
Pubblicazione: (2025)

Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
di: Khadiev, Kamil, et al.
Pubblicazione: (2024)

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
di: Chen, Xi, et al.
Pubblicazione: (2024)

Characterizing and Testing Principal Minor Equivalence of Matrices
di: Chatterjee, Abhranil, et al.
Pubblicazione: (2024)

A General Framework for Low Soundness Homomorphism Testing
di: Mittal, Tushant, et al.
Pubblicazione: (2025)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
di: Aute, Shubhada, et al.
Pubblicazione: (2026)

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
di: Gilani, Amin Shiraz, et al.
Pubblicazione: (2024)

Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
di: Ruszil, Jakub, et al.
Pubblicazione: (2026)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
di: Johnson, Matthew, et al.
Pubblicazione: (2022)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Lazy Kronecker Product
di: Song, Zhao
Pubblicazione: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
di: Nederlof, Jesper
Pubblicazione: (2026)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
di: Jiang, Cheng, et al.
Pubblicazione: (2026)

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
di: Ducoffe, Guillaume
Pubblicazione: (2026)