Image de couverture de livre

Equivalence Testing: The Power of Bounded Adaptivity

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Chakraborty, Diptarka, Chakraborty, Sourav, Kumar, Gunjan, Meel, Kuldeep S.
Format:	Preprint
Publié:	2024
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Distance Estimation for High-Dimensional Discrete Distributions
par: Kumar, Gunjan, et autres
Publié: (2023)

A faster FPRAS for #NFA
par: Meel, Kuldeep S., et autres
Publié: (2023)

Engineering an Efficient Approximate DNF-Counter
par: Soos, Mate, et autres
Publié: (2024)

Towards practical FPRAS for #NFA: Exploiting the Power of Dependence
par: Meel, Kuldeep S., et autres
Publié: (2025)

#CFG and #DNNF admit FPRAS
par: Meel, Kuldeep S., et autres
Publié: (2024)

An FPRAS for Model Counting for Non-Deterministic Read-Once Branching Programs
par: Meel, Kuldeep S., et autres
Publié: (2024)

Improved Rank Aggregation under Fairness Constraint
par: Chakraborty, Diptarka, et autres
Publié: (2025)

Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking
par: Chakraborty, Diptarka, et autres
Publié: (2026)

Clustering Permutations: New Techniques with Streaming Applications
par: Chakraborty, Diptarka, et autres
Publié: (2022)

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
par: Chakraborty, Sourav, et autres
Publié: (2024)

Approximating Queries on Probabilistic Graphs
par: Amarilli, Antoine, et autres
Publié: (2023)

Towards Fair Representation: Clustering and Consensus
par: Chakraborty, Diptarka, et autres
Publié: (2025)

Instance Dependent Testing of Samplers using Interval Conditioning
par: Bhattacharyya, Rishiraj, et autres
Publié: (2025)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
par: Balakrishnan, Girish, et autres
Publié: (2024)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
par: Adar, Tomer, et autres
Publié: (2024)

Structural Parameterization of Locating-Dominating Set and Test Cover
par: Chakraborty, Dipayan, et autres
Publié: (2024)

Clustering with Label Consistency
par: Chakraborty, Diptarka, et autres
Publié: (2025)

Explaining Rankings with Hidden Group Bonuses
par: Yan, Alvin Hong Yao, et autres
Publié: (2026)

Online facility location with weights and congestion
par: Chakraborty, Arghya, et autres
Publié: (2022)

RSVP: Beyond Weisfeiler Lehman Graph Isomorphism Test
par: Dutta, Sourav, et autres
Publié: (2024)

Maximizing Diversity in (near-)Median String Selection
par: Chakraborty, Diptarka, et autres
Publié: (2026)

Computational Explorations of Total Variation Distance
par: Bhattacharyya, Arnab, et autres
Publié: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
par: Bhattacharyya, Arnab, et autres
Publié: (2025)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
par: Chakraborty, Dipayan, et autres
Publié: (2024)

Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
par: Chakraborty, Shantanav
Publié: (2023)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
par: Yoshida, Yuichi
Publié: (2026)

Succinct Data Structures for Baxter Permutation and Related Families
par: Chakraborty, Sankardeep, et autres
Publié: (2024)

Fast exact algorithms via the Matrix Tree Theorem
par: Arvind, V., et autres
Publié: (2025)

CNFs and DNFs with Exactly $k$ Solutions
par: Chandran, L. Sunil, et autres
Publié: (2025)

Calculation of the Comparative Efficiency of Algorithms Using a Single Metric
par: Chakraborty, Arya
Publié: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
par: Chakraborty, Dibyayan, et autres
Publié: (2024)

Bi-Criteria Metric Distortion
par: Banihashem, Kiarash, et autres
Publié: (2024)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
par: Balakrishnan, Girish, et autres
Publié: (2023)

Tight Static Lower Bounds for Non-Adaptive Data Structures
par: Persiano, Giuseppe, et autres
Publié: (2020)

A Distribution Testing Approach to Clustering Distributions
par: Kumar, Gunjan, et autres
Publié: (2025)

Tight Bounds for Low-Error Frequency Moment Estimation and the Power of Multiple Passes
par: Green-Maimon, Naomi, et autres
Publié: (2025)

Variations on the Problem of Identifying Spectrum-Preserving String Sets
par: Chakraborty, Sankardeep, et autres
Publié: (2026)

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

Fault-Equivalent Lowest Common Ancestors
par: Petruschka, Asaf
Publié: (2024)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
par: Atalig, Sunny, et autres
Publié: (2024)