scientific article; zbMATH DE number 1256636

zbMath0977.68539MaRDI QIDQ4230322

Mario Szegedy, Sanjeev Arora, Madhu Sudan, Carstent Lund, Rajeev Motwani

Publication date: 17 January 2002

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Theory of programming languages (68N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On decision and optimization (\(k\),\(l\))-graph sandwich problems, RNC-approximation algorithms for the steiner problem, Probabilistic proof systems — A survey, Improved approximations of independent sets in bounded-degree graphs, Recent results in hardness of approximation, Hard graphs for randomized subgraph exclusion algorithms, Some recent strong inapproximability results, Parallel and sequential approximation of shortest superstrings, The computational complexity of approximating the minimal perturbation scaling to achieve instability in an interval matrix, On approximation properties of the Independent set problem for degree 3 graphs, Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles), Interactive Oracle Proofs, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : formalisme unifié et classes d'approximation, On the longest circuit in an alterable digraph, Random walks on colored graphs, The complexity of approximating a nonlinear program, ZK-PCPs from leakage-resilient secret sharing, A constrained edit distance between unordered labeled trees, PALO: a probabilistic hill-climbing algorithm, NP-completeness: A retrospective, Checking properties of polynomials, The minimum color sum of bipartite graphs, A primal-dual approach to approximation of node-deletion problems for matroidal properties, Simulating BPP using a general weak random source, Approximation algorithms for tree alignment with a given phylogeny, A class of spectral bounds for max \(k\)-cut, On the approximability of some maximum spanning tree problems, Graph layout problems, Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties, Structure in approximation classes, Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms, A geometric approach to betweenness, Succinct classical verification of quantum computation, Unnamed Item, Approximating minimum keys and optimal substructure screens, Unnamed Item, Max NP-completeness made easy, Improved non-approximability results for minimum vertex cover with density constraints, Maximum renamable Horn sub-CNFs, Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP, The approximation of maximum subgraph problems, Polynomially bounded minimization problems which are hard to approximate, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, On the approximation of shortest common supersequences and longest common subsequences, Multiway cuts in directed and node weighted graphs, Approximation algorithms for maximum cut with limited unbalance, Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, Fast Reed-Solomon Interactive Oracle Proofs of Proximity, Metafinite model theory, MNP: A class of NP optimization problems, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs, Minimization of decision trees is hard to approximate, Bottleneck Steiner tree with bounded number of Steiner vertices, A generalization of maximal independent sets, Reductions, completeness and the hardness of approximability, On approximating the longest path in a graph, The ferry cover problem, On maximum planar induced subgraphs, Completeness in approximation classes beyond APX, A PTAS for the minimization of polynomials of fixed degree over the simplex, Partitioning problems in dense hypergraphs, Approximate evaluations of characteristic polynomials of Boolean functions, Hardness and methods to solve CLIQUE, Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles), On the complexity of comparing evolutionary trees, Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits, Simple heuristics for unit disk graphs, Worst-case performance of approximation algorithms for tool management problems, Travelling on graphs with small highway dimension, Unnamed Item, A \(2^{|E|/4}\)-time algorithm for MAX-CUT, On weighted vs unweighted versions of combinatorial optimization problems, Bounded queries, approximations, and the Boolean hierarchy, Randomness in distribution protocols, Lattice-Based SNARGs and Their Application to More Efficient Obfuscation, Primal-dual approximation algorithms for a packing-covering pair of problems, Annealed replication: A new heuristic for the maximum clique problem, The complexity of minimizing and learning OBDDs and FBDDs, The hardness of approximation: Gap location, A short note on the approximability of the maximum leaves spanning tree problem, A note on approximating graph genus, On the power of multi-prover interactive protocols, Theorems for a price: Tomorrow's semi-rigorous mathematical culture, The death of proof? Semi-rigorous mathematics? You've got to be kidding!, Probabilistically checkable proofs and their consequences for approximation algorithms, On the Steiner ratio in 3-space, Weighted fractional and integral \(k\)-matching in hypergraphs, On approximation algorithms for the minimum satisfiability problem, On an approximation measure founded on the links between optimization and polynomial approximation theory, Inferring a tree from walks, The hardness of approximate optima in lattices, codes, and systems of linear equations, On fixed-parameter tractability and approximability of NP optimization problems, Measure on \(P\): Strength of the notion, The complexity and approximability of finding maximum feasible subsystems of linear relations, MNP: A class of NP optimization problems, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, Ramsey theory and integrality gap for the independent set problem, The complexity of minimum partial truth assignments and implication in negation-free formulae, Rounding algorithms for covering problems, Approximating the independence number via the \(\vartheta\)-function, Hardness results and spectral techniques for combinatorial problems on circulant graphs, On chromatic sums and distributed resource allocation, A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem, On the approximability of some Maximum Spanning Tree Problems, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Approximate testing with error relative to input size., On the approximability of the Steiner tree problem., Short undeniable signatures based on group homomorphisms, A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach, Approximate solution of NP optimization problems, Local search, reducibility and approximability of NP-optimization problems, Alignment of trees -- an alternative to tree edit, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, Complexities of efficient solutions of rectilinear polygon cover problems, Unrelated parallel machine scheduling -- perspectives and progress, Primal-dual approximation algorithms for integral flow and multicut in trees, Randomized approximation of bounded multicovering problems, Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION, On approximating the longest path in a graph, A series of approximation algorithms for the acyclic directed Steiner tree problem, Greed is good: Approximating independent sets in sparse and bounded-degree graphs, The Steiner tree problem on graphs: inapproximability results, A note on the descriptive complexity of maximization problems, Approximating the minimum maximal independence number, Maximizing business value by optimal assignment of jobs to resources in grid computing, Approximating the tree and tour covers of a graph, A well-characterized approximation problem, The ideal membership problem and polynomial identity testing, Quantifiers and approximation, Pseudo-Boolean optimization, Minimization of ordered, symmetric half-products, Minimal multicut and maximal integer multiflow: a survey, A survey on tree edit distance and related problems, Order consolidation for batch processing, The complexity of Boolean constraint satisfaction local search problems, On the complexity of finding emerging patterns, On the approximability of an interval scheduling problem, An algorithm for finding a maximum clique in a graph, An adaptive, multiple restarts neural network algorithm for graph coloring, Hierarchically specified unit disk graphs, A unified approximation algorithm for node-deletion problems, On a scheduling problem of time deteriorating jobs, Alphabet indexing for approximating features of symbols, On the approximation of protein threading, Differential approximation algorithms for some combinatorial optimization problems, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, On the hardness of approximating shortest integer relations among rational numbers, Bounding queries in the analytic polynomial-time hierarchy, A new lower bound on approximability of the ground state problem for tridimensional Ising spin glasses, Integer programming as a framework for optimization and approximability, Zero knowledge and the chromatic number, Class Steiner trees and VLSI-design, On approximation algorithms for the terminal Steiner tree problem, A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios, Computational experience with approximation algorithms for the set covering problem, On the approximability of the Steiner tree problem in phylogeny, On the complexity of the approximation of nonplanarity parameters for cubic graphs, Alarm placement in systems with fault propagation, An improved approximation algorithm of MULTIWAY CUT., An effective local search for the maximum clique problem, APX-hardness of domination problems in circle graphs, Distance graphs and the \(T\)-coloring problem, Approximating minimum feedback vertex sets in hypergraphs, Derandomized graph products, Clique is hard to approximate within \(n^{1-\epsilon}\), Extracting randomness: A survey and new constructions, Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems, The inapproximability of non-NP-hard optimization problems., Tight bound on Johnson's algorithm for maximum satisfiability, The complexity of the max word problem and the power of one-way interactive proof systems, A 2-approximation algorithm for the minimum weight edge dominating set problem, Which problems have strongly exponential complexity?, The maximum clique problem, Some MAX SNP-hard results concerning unordered labeled trees, Maximum bounded \(H\)-matching is Max SNP-complete, Two results in negation-free logic