Cover Image

Complexity of learning matchings and half graphs via edge queries

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mande, Nikhil S., Sanyal, Swagato, Zamaraev, Viktor
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Discrete Mathematics Combinatorics 68Q04, 68Q12
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Finding cliques and dense subgraphs using edge queries
by: Csóka, Endre, et al.
Published: (2023)

Trifferent codes with small lengths
by: Kurz, Sascha
Published: (2023)

Kolmogorov complexity as a combinatorial tool
by: Shen, Alexander
Published: (2024)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Mim-Width is paraNP-complete
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

On balanceable and simply balanceable regular graphs
by: Ahanjideh, Milad, et al.
Published: (2024)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Results on three problems on isolation of graphs
by: Borg, Peter, et al.
Published: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Vanishing of Schubert Coefficients
by: Pak, Igor, et al.
Published: (2024)

Positivity of Schubert Coefficients
by: Pak, Igor, et al.
Published: (2024)

WalkSAT is linear on random 2-SAT
by: Berenbrink, Petra, et al.
Published: (2024)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
by: Meusel, Julia, et al.
Published: (2025)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
by: Ghosh, Soumyadip, et al.
Published: (2024)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Concurrency Constrained Scheduling with Tree-Like Constraints
by: Bodlaender, Hans L., et al.
Published: (2025)

$k$-edge geodetic graphs
by: Guragain, Satyam, et al.
Published: (2024)

Circularity and repetitiveness in non-injective DF0L systems
by: Goulet-Ouellet, Herman, et al.
Published: (2025)

Quantum Algorithm for Estimating Gibbs Free Energy and Entropy via Energy Derivatives
by: Guo, Shangjie, et al.
Published: (2025)

Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)

The random $k$-SAT Gibbs uniqueness threshold revisited
by: Chatterjee, Arnab, et al.
Published: (2025)

Quantum Lower Bounds by Sample-to-Query Lifting
by: Wang, Qisheng, et al.
Published: (2023)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models
by: Gayral, Léo, et al.
Published: (2023)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)

Quantum circuits for permutation matrices
by: Hanson, Jason
Published: (2025)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Complexity of chess domination problems
by: Langlois-Rémillard, Alexis, et al.
Published: (2022)

Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
by: Pak, Igor, et al.
Published: (2025)

Vanishing of Schubert coefficients in probabilistic polynomial time
by: Pak, Igor, et al.
Published: (2025)

From Historical Puzzles to Grammatical Constraints: Circular Partitions, Generalized Run-Length Encodings, and Polynomial-Time Decidability
by: Khormali, Omid, et al.
Published: (2026)

Fault-tolerant mutual-visibility: complexity and solutions for grid-like networks
by: Cicerone, Serafino, et al.
Published: (2025)

Hardness of Finding Kings and Strong Kings
by: Alaoui, Ziad Ismaili, et al.
Published: (2025)