Probabilistic checking of proofs
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Cryptography with constant input locality
- APX-hardness of domination problems in circle graphs
- Testing algebraic geometric codes
- Approximating maximum independent sets by excluding subgraphs
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- Probabilistically checkable proofs and their consequences for approximation algorithms
- Quantum multi-prover interactive proof systems with limited prior entanglement.
- Spot-checkers
- Interactive and probabilistic proof-checking
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The hunting of the SNARK
- A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems
- PSPACE has constant-round quantum interactive proof systems
- 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
- Efficient checking of polynomials and proofs and the hardness of approximation problems
- Exponential inapproximability of selecting a maximum volume sub-matrix
- 2-transitivity is insufficient for local testability
- Max NP-completeness made easy
- The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
- The Chinese deliveryman problem
- Smooth and strong PCPs
- Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
- 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
- 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
- A PCP theorem for interactive proofs and applications
- Zero-knowledge IOPs with linear-time prover and polylogarithmic-time verifier
- The maximum independent union of cliques problem: complexity and exact approaches
- Succinct arguments in the quantum random oracle model
- Linear-size constant-query IOPs for delegating computation
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Combinatorial algorithms for distributed graph coloring
- Hardness results for approximate pure Horn CNF formulae minimization
- Probably bounded suboptimal heuristic search
- Rank-one quantum games
- The PCP theorem for NP over the reals
- Quantum de Finetti theorems under local measurements with applications
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- An algebraic proof of the real number PCP theorem
- Low-degree test with polynomially small error
- Non-black-box simulation in the fully concurrent setting, revisited
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- On the severity of Braess's paradox: designing networks for selfish users is hard
- 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
- Column subset selection problem is UG-hard
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Tight security bounds for Micali's SNARGs
- 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
- Corrigendum to: ``Efficient probabilistic checkable proofs and applications to approximation
- PCP characterizations of NP: towards a polynomially-small error-probability
- Distance-based clique relaxations in networks: s-clique and s-club
- A combinatorial characterization of smooth LTCs and applications
- Quantum XOR games
- Input-oblivious proof systems and a uniform complexity perspective on P/poly
- On fast heuristic non-deterministic algorithms and short heuristic proofs
- Strong inapproximability of the shortest reset word
- An Algebraic Proof of the Real Number PCP Theorem
- QMA with subset state witnesses
- Stronger methods of making quantum interactive proofs perfectly complete
- A PCP characterization of AM
- Testing low-degree polynomials over prime fields
- Inapproximability of b-matching in k-uniform hypergraphs
- Satisfying degree-\(d\) equations over \(\mathrm{GF}[2]^{n}\)
- Nearly optimal NP-hardness of vertex cover on k-uniform k-partite hypergraphs
- On Sums of Locally Testable Affine Invariant Properties
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- Short locally testable codes and proofs
- Bravely, moderately: a common theme in four recent works
- Randomness and computation
- Almost transparent short proofs for \(\mathrm{NP}_{\mathbb R}\)
- Combinatorial algorithms for distributed graph coloring
- Self-correctors for cryptographic modules
- Formation Potential Field for Trajectory Tracking Control of Multi-Agents in Constrained Space
- Proof verification and the hardness of approximation problems
- Interactive oracle proofs
- A query efficient non-adaptive long code test with perfect completeness
- On the complexity of the minimum independent set partition problem
- New hardness results for routing on disjoint paths
- Sparse approximation is provably hard under coherent dictionaries
- Simultaneous approximation of constraint satisfaction problems
- Interactive proofs with approximately commuting provers
- Quantum locally testable codes
- Complexity and Algorithms for Well-Structured k-SAT Instances
- Succinct NP Proofs from an Extractability Assumption
- More efficient queries in PCPs for NP and improved approximation hardness of maximum CSP
This page was built for publication: Probabilistic checking of proofs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3841041)
