Proof verification and the hardness of approximation problems
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Packing trees in communication networks
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Approximation algorithms for the weighted independent set problem in sparse graphs
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- Cryptography with constant input locality
- On the hardness of approximating max-satisfy
- Testing algebraic geometric codes
- Approximating maximum independent sets by excluding subgraphs
- Probabilistically checkable proofs and their consequences for approximation algorithms
- Non-approximability of weighted multiple sequence alignment.
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- Spot-checkers
- Interactive and probabilistic proof-checking
- A randomized approximation scheme for metric MAX-CUT
- Bottleneck bichromatic full Steiner trees
- A quadratic time exact algorithm for continuous connected 2-facility location problem in trees
- The traveling salesman problem on grids with forbidden neighborhoods
- The hunting of the SNARK
- Sparsification and subexponential approximation
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- Fast approximate PCPs for multidimensional bin-packing problems
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- Submodular unsplittable flow on trees
- Steiner trees in uniformly quasi-bipartite graphs.
- Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems.
- Differential approximation for optimal satisfiability and related problems
- One complexity theorist's view of quantum computing
- Algebraic testing and weight distributions of codes.
- Towards optimal lower bounds for clique and chromatic number.
- On the approximability of clique and related maximization problems
- Fast approximate probabilistically checkable proofs
- Inapproximability results for equations over finite groups
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Exponential inapproximability of selecting a maximum volume sub-matrix
- A case of depth-3 identity testing, sparse factorization and duality
- 2-transitivity is insufficient for local testability
- Connected facility location via random facility sampling and core detouring
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- The Chinese deliveryman problem
- Smooth and strong PCPs
- On succinct arguments and witness encryption from groups
- Spartan: efficient and general-purpose zkSNARKs without trusted setup
- A PCP of proximity for real algebraic polynomials
- Subquadratic SNARGs in the random oracle model
- On regularity of Max-CSPs and Min-CSPs
- Bayesian agency: linear versus tractable contracts
- Succinct non-interactive arguments via linear interactive proofs
- Preprocessing succinct non-interactive arguments for rank-1 constraint satisfiability from holographic proofs
- Real-time, constant-space, constant-randomness verifiers
- Approximation algorithms for clustering with dynamic points
- A PCP theorem for interactive proofs and applications
- Succinct arguments in the quantum random oracle model
- Linear-size constant-query IOPs for delegating computation
- On the (In)security of Kilian-based SNARGs
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Hardness results for approximate pure Horn CNF formulae minimization
- The Euclidean bottleneck full Steiner tree problem
- A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem
- On full Steiner trees in unit disk graphs
- Rank-one quantum games
- The PCP theorem for NP over the reals
- Quantum de Finetti theorems under local measurements with applications
- Logic minimization techniques with applications to cryptology
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- On constructing an optimal consensus clustering from multiple clusterings
- An algebraic proof of the real number PCP theorem
- Low-degree test with polynomially small error
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Computing the differential of a graph: hardness, approximability and exact algorithms
- Network design with a discrete set of traffic matrices
- Testing of matrix-poset properties
- Constrained sequence alignment: A general model and the hardness results
- From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization
- Finding edge-disjoint paths in networks: an ant colony optimization algorithm
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Inapproximability results for the lateral gene transfer problem
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Complexity results on restricted instances of a paint shop problem for words
- TSP with bounded metrics
- On the severity of Braess's paradox: designing networks for selfish users is hard
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- What can be efficiently reduced to the Kolmogorov-random strings?
- Combinatorial PCPs with short proofs
- Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
- Satisfiability with index dependency
- Column subset selection problem is UG-hard
- Genus characterizes the complexity of certain graph problems: Some tight results
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Tight security bounds for Micali's SNARGs
- Complexity and approximability of quantified and stochastic constraint satisfaction problems
- scientific article; zbMATH DE number 1670809 (Why is no real title available?)
- Components in time-varying graphs
- Quasi-linear size zero knowledge from linear-algebraic PCPs
- QMA with subset state witnesses
- Bounds on 2-query locally testable codes with affine tests
- Three-player entangled XOR games are NP-hard to approximate
- Jacobian hits circuits: hitting sets, lower bounds for depth-D occur-k formulas and depth-3 transcendence degree-k circuits
- Distance-based clique relaxations in networks: s-clique and s-club
This page was built for publication: Proof verification and the hardness of approximation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158513)
