scientific article
From MaRDI portal
Publication:3210157
zbMath0722.68028MaRDI QIDQ3210157
Publication date: 1991
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Specification and verification (program logics, model checking, etc.) (68Q60) Theory of software (68N99)
Related Items (41)
Fast approximate probabilistically checkable proofs ⋮ An information-theoretic treatment of random-self-reducibility ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Probabilistically checkable proofs and their consequences for approximation algorithms ⋮ Masking traveling beams: optical solutions for NP-complete problems, trading space for time ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Decoding of Reed Solomon codes beyond the error-correction bound ⋮ Can we locally compute sparse connected subgraphs? ⋮ Checking properties of polynomials ⋮ Linear-size constant-query IOPs for delegating computation ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Checking the correctness of memories ⋮ Unnamed Item ⋮ Erasures versus errors in local decoding and property testing ⋮ Approximate testing with error relative to input size. ⋮ Unnamed Item ⋮ A note on the self-witnessing property of computational problems ⋮ On derandomizing Yao's weak-to-strong OWF construction ⋮ Locality and checkability in wait-free computing ⋮ Foundations of Homomorphic Secret Sharing ⋮ Program result checking: A new approach to making programs more reliable ⋮ Constructing concrete hard instances of the maximum independent set problem ⋮ Locally random reductions: Improvements and applications ⋮ Computing the partition function of the Sherrington-Kirkpatrick model is hard on average ⋮ Self-correcting for function fields of finite transcendental degree ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ On games of incomplete information ⋮ Highly resilient correctors for polynomials ⋮ Pipelined algorithms to detect cheating in long-term grid computations ⋮ On the autoreducibility of functions ⋮ Pseudorandom generators without the XOR lemma ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ Locality and Checkability in Wait-Free Computing ⋮ Spot-checkers ⋮ Self-testing/correcting with applications to numerical problems ⋮ Randomness vs time: Derandomization under a uniform assumption ⋮ PSPACE is provable by two provers in one round
This page was built for publication: