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
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
