Copertina

Quality control in sublinear time: a case study via random graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Marcussen, Cassandra, Rubinfeld, Ronitt, Sudan, Madhu
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms Machine Learning Combinatorics Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Fast Coloring Oracle for Average Case Hypergraphs
di: Marcussen, Cassandra, et al.
Pubblicazione: (2025)

Finding the root in random nearest neighbor trees
di: Brandenberger, Anna, et al.
Pubblicazione: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
di: Eden, Talya, et al.
Pubblicazione: (2025)

Errors are Robustly Tamed in Cumulative Knowledge Processes
di: Brandenberger, Anna, et al.
Pubblicazione: (2023)

Optimal Algorithms for Augmented Testing of Discrete Distributions
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2024)

Beyond Worst Case Local Computation Algorithms
di: Biswas, Amartya Shankha, et al.
Pubblicazione: (2024)

Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
di: Aliakbarpour, Maryam, et al.
Pubblicazione: (2025)

Burning rooted graph products
di: Peca-Medlin, John
Pubblicazione: (2026)

Markov Chains with Rewinding
di: Azarmehr, Amir, et al.
Pubblicazione: (2026)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Locally computing edge orientations
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
di: Kunisky, Dmitriy
Pubblicazione: (2024)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
di: Dhawan, Abhishek, et al.
Pubblicazione: (2024)

Stochastic Matching via In-n-Out Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2024)

Efficiently matching random inhomogeneous graphs via degree profiles
di: Ding, Jian, et al.
Pubblicazione: (2023)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
di: Mitrović, Slobodan, et al.
Pubblicazione: (2026)

Cycle-factors of regular graphs via entropy
di: Christoph, Micha, et al.
Pubblicazione: (2025)

An Easy Proof of a Weak Version of Chernoff inequality
di: Har-Peled, Sariel
Pubblicazione: (2025)

Analysis of a Random Local Search Algorithm for Dominating Set
di: Higl, Hendrik
Pubblicazione: (2026)

The graph alignment problem: fundamental limits and efficient algorithms
di: Ganassali, Luca
Pubblicazione: (2024)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
di: Eden, Talya, et al.
Pubblicazione: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
di: Nadimpalli, Shivam, et al.
Pubblicazione: (2025)

Learning and Testing Convex Functions
di: Pinto Jr., Renato Ferreira, et al.
Pubblicazione: (2025)

Heights of butterfly trees
di: Peca-Medlin, John, et al.
Pubblicazione: (2025)

Overlap Analysis of the Shortest Path Problem: Local Search, Landscapes, and Franz--Parisi Potential
di: Koehler, Frederic, et al.
Pubblicazione: (2025)

Zero-Freeness is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region
di: Shao, Shuai, et al.
Pubblicazione: (2025)

The Horton-Strahler number of butterfly trees
di: Peca-Medlin, John
Pubblicazione: (2025)

Mixing on Generalized Associahedra
di: Chang, William, et al.
Pubblicazione: (2024)

Fast Mixing in Sparse Random Ising Models
di: Liu, Kuikui, et al.
Pubblicazione: (2024)

Minimal spanning arborescence
di: Ray, Gourab, et al.
Pubblicazione: (2024)

Polynomial-time sampling despite disorder chaos
di: Ma, Eric, et al.
Pubblicazione: (2025)

Finding the Root in Random Nearest Neighbor Trees
di: Anna Brandenberger, et al.
Pubblicazione: (2026)

From Zero-Freeness to Strong Spatial Mixing via a Christoffel-Darboux Type Identity
di: Shao, Shuai, et al.
Pubblicazione: (2024)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
di: Bansal, Nikhil, et al.
Pubblicazione: (2025)

Planted clique recovery in random geometric graphs
di: Avrachenkov, Konstantin, et al.
Pubblicazione: (2025)

Reconstruction of geometric random graphs with the Simple algorithm
di: Stegehuis, Clara, et al.
Pubblicazione: (2024)

Fitting an ellipsoid to a quadratic number of random points
di: Bandeira, Afonso S., et al.
Pubblicazione: (2023)

Fixed-magnetization Ising on random graphs up to reconstruction
di: Gheissari, Reza, et al.
Pubblicazione: (2025)

Statistical inference of a ranked community in a directed graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Correlation detection in trees for planted graph alignment
di: Ganassali, Luca, et al.
Pubblicazione: (2021)