Cover Image

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Black, Hadley, Mazumdar, Arya, Saha, Barna, Xu, Yinzhan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Information Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Learning Partitions with Optimal Query and Round Complexities
by: Black, Hadley, et al.
Published: (2025)

Clustering with Non-adaptive Subset Queries
by: Black, Hadley, et al.
Published: (2024)

Actively Learning Halfspaces without Synthetic Data
by: Black, Hadley, et al.
Published: (2025)

Random Subgraph Detection Using Queries
by: Huleihel, Wasim, et al.
Published: (2021)

Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
by: Matsumoto, Namiko, et al.
Published: (2022)

The I/O Complexity of Attention, or How Optimal is Flash Attention?
by: Saha, Barna, et al.
Published: (2024)

Learning sparse generalized linear models with binary outcomes via iterative hard thresholding
by: Matsumoto, Namiko, et al.
Published: (2025)

Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time
by: Li, Xiaxin, et al.
Published: (2025)

Graph Reconstruction from Noisy Random Subgraphs
by: McGregor, Andrew, et al.
Published: (2024)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
by: Chakraborty, Diptarka, et al.
Published: (2026)

Noisy Nonadaptive Group Testing with Binary Splitting: New Test Design and Improvement on Price-Scarlett-Tan's Scheme
by: Li, Xiaxin, et al.
Published: (2024)

Deterministic Monotone Min-Plus Product and Convolution
by: Jin, Ce, et al.
Published: (2026)

Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions
by: Black, Hadley
Published: (2023)

Sample-Optimal Private Regression in Polynomial Time
by: Anderson, Prashanti, et al.
Published: (2025)

Local Fragments, Global Gains: Subgraph Counting using Graph Neural Networks
by: Roy, Shubhajit, et al.
Published: (2023)

A Framework for Searching in Graphs in the Presence of Errors
by: Dereniowski, Dariusz, et al.
Published: (2018)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
by: Kociumaka, Tomasz, et al.
Published: (2014)

PTF Testing Lower Bounds for Non-Gaussian Component Analysis
by: Diakonikolas, Ilias, et al.
Published: (2025)

Planted Bipartite Graph Detection
by: Rotenberg, Asaf, et al.
Published: (2023)

Optimal high-precision shadow estimation
by: Chen, Sitan, et al.
Published: (2024)

Optimal Differentially Private Sampling of Unbounded Gaussians
by: Iverson, Valentio, et al.
Published: (2025)

Learning DNF through Generalized Fourier Representations
by: Heidari, Mohsen, et al.
Published: (2025)

The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm
by: Chen, Jiale, et al.
Published: (2025)

Testing with Non-identically Distributed Samples
by: Garg, Shivam, et al.
Published: (2023)

The SMART approach to instance-optimal online learning
by: Banerjee, Siddhartha, et al.
Published: (2024)

Subsampling Suffices for Adaptive Data Analysis
by: Blanc, Guy
Published: (2023)

Smoothed Score Queries and the Complexity of Sampling
by: Liu, Jingbo
Published: (2026)

Learning multivariate Gaussians with imperfect advice
by: Bhattacharyya, Arnab, et al.
Published: (2024)

Entropy Coding of Unordered Data Structures
by: Kunze, Julius, et al.
Published: (2024)

New Algorithmic Directions in Optimal Transport and Applications for Product Spaces
by: Beigi, Salman, et al.
Published: (2025)

SpecTr: Fast Speculative Decoding via Optimal Transport
by: Sun, Ziteng, et al.
Published: (2023)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
by: Li, Gen, et al.
Published: (2023)

New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
by: Fischer, Nick, et al.
Published: (2024)

Optimal and Near-Optimal Adaptive Vector Quantization
by: Ben-Basat, Ran, et al.
Published: (2024)

Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages
by: Asi, Hilal, et al.
Published: (2024)

Incremental Strongly Connected Components with Predictions
by: Deng, Ronald, et al.
Published: (2026)

Rooting Out Entropy: Optimal Tree Extraction for Ultra-Succinct Graphs
by: Alaoui, Ziad Ismaili, et al.
Published: (2026)

Compact Conformal Subgraphs
by: Gollapudi, Sreenivas, et al.
Published: (2026)