Bounded queries, approximations, and the Boolean hierarchy (Q1854449): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1006/inco.2000.2884
+Normal rank
@@ Property / OpenAlex ID @@
+W2031104867
@@ Property / OpenAlex ID: W2031104867 / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomized graph products
@@ Property / cites work: Derandomized graph products / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230322
@@ Property / cites work: Q4230322 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4230321
@@ Property / cites work: Q4230321 / rank @@
+Normal rank
@@ Property / cites work @@
+A relationship between difference hierarchies and relativized polynomial hierarchies
+Normal rank
@@ Property / cites work @@
+Q3996675
@@ Property / cites work: Q3996675 / rank @@
+Normal rank
@@ Property / cites work @@
+Bounded queries to SAT and the Boolean hierarchy
@@ Property / cites work: Bounded queries to SAT and the Boolean hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258567
@@ Property / cites work: Q4258567 / rank @@
+Normal rank
@@ Property / cites work @@
+Quantitative Relativizations of Complexity Classes
+Normal rank
@@ Property / cites work @@
+Q3773331
@@ Property / cites work: Q3773331 / rank @@
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy I: Structural Properties
@@ Property / cites work: The Boolean Hierarchy I: Structural Properties / rank @@
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy II: Applications
@@ Property / cites work: The Boolean Hierarchy II: Applications / rank @@
+Normal rank
@@ Property / cites work @@
+On Bounded Queries and Approximation
@@ Property / cites work: On Bounded Queries and Approximation / rank @@
+Normal rank
@@ Property / cites work @@
+Q4318988
@@ Property / cites work: Q4318988 / rank @@
+Normal rank
@@ Property / cites work @@
+On the query complexity of clique size and maximum satisfiability
+Normal rank
@@ Property / cites work @@
+On computing Boolean connectives of characteristic functions
+Normal rank
@@ Property / cites work @@
+The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
+Normal rank
@@ Property / cites work @@
+Q4470516
@@ Property / cites work: Q4470516 / rank @@
+Normal rank
@@ Property / cites work @@
+The strong exponential hierarchy collapses
@@ Property / cites work: The strong exponential hierarchy collapses / rank @@
+Normal rank
@@ Property / cites work @@
+A Downward Collapse within the Polynomial Hierarchy
+Normal rank
@@ Property / cites work @@
+The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+The complexity of optimization problems
@@ Property / cites work: The complexity of optimization problems / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity-Restricted Advice Functions
@@ Property / cites work: Complexity-Restricted Advice Functions / rank @@
+Normal rank
@@ Property / cites work @@
+On Restricting the Size of Oracles Compared with Restricting Access to Oracles
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, <i>k</i>-MST, and Related Problems
+Normal rank
@@ Property / cites work @@
+Q3221403
@@ Property / cites work: Q3221403 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of facets (and some facets of complexity)
+Normal rank
@@ Property / cites work @@
+Bounded Query Classes
@@ Property / cites work: Bounded Query Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Some consequences of non-uniform conditions on uniform classes
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1854449