On limited nondeterminism and the complexity of the V-C dimension
From MaRDI portal
Publication:1816725
DOI10.1006/JCSS.1996.0058zbMath0859.68031OpenAlexW2177603603WikidataQ29037933 ScholiaQ29037933MaRDI QIDQ1816725
Mihalis Yannakakis, Christos H. Papadimitriou
Publication date: 31 March 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1996.0058
Related Items (43)
On the complexity of approximating the VC dimension. ⋮ Solving large FPT problems on coarse-grained parallel machines ⋮ An improved fixed-parameter algorithm for vertex cover ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Fixed-parameter approximation: conceptual framework and approximability results ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows ⋮ Strong computational lower bounds via parameterized complexity ⋮ The VC-dimension of graphs with respect to \(k\)-connected subgraphs ⋮ On fixed-parameter tractability and approximability of NP optimization problems ⋮ Narrow sieves for parameterized paths and packings ⋮ Boundary classes for graph problems involving non-local properties ⋮ NP-completeness: A retrospective ⋮ Induced subgraph isomorphism: are some patterns substantially easier than others? ⋮ Finding connected secluded subgraphs ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ From undecidability of non-triviality and finiteness to undecidability of learnability ⋮ A note on hardness of computing recursive teaching dimension ⋮ Computing generating sets of minimal size in finite algebras ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ The Bounded and Precise Word Problems for Presentations of Groups ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Confronting intractability via parameters ⋮ The Complexity of Finding (Approximate Sized) Distance-d Dominating Set in Tournaments ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Non-interactive proofs of proximity ⋮ Aggregate operators in constraint query languages ⋮ Random ubiquitous transformation semigroups ⋮ On the computational hardness based on linear fpt-reductions ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ Unnamed Item ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ Margin of victory for tournament solutions ⋮ Finding kings in tournaments ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ Bounding the trace function of a hypergraph with applications ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Deciding the Vapnik-Červonenkis dimension is \(\Sigma_3^p\)-complete ⋮ On the complexity of database queries ⋮ Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ The minimum equivalent DNF problem and shortest implicants
This page was built for publication: On limited nondeterminism and the complexity of the V-C dimension
