 |
|
What people are saying - Write a reviewWe haven't found any reviews in the usual places. Related books
Contents
Common terms and phrasesaforementioned approximation assertion average-case binary Boolean circuits coin tosses Complexity Theory computational problems consider constant construction corresponding cryptography decision problems defined Definition denoted derandomization deterministic distinguisher edges efficient emulation encoding encryption error probability Exercise exists foregoing Furthermore given graph G Guideline holds input instances integer interactive proof system iteration Karp-reduction Lemma length linear log-space log2 logarithmic mapping model of computation no-instances non-deterministic non-uniform Note notion NP-complete NP-proof obtain one-way functions oracle machine output P/poly pairwise independent parties PCP Theorem polynomial polynomial-time reduction probabilistic polynomial-time algorithm probability ensembles procedure promise problem proof of Theorem Proposition protocol prove pseudorandom queries query complexity randomized algorithm Recall reduction refers resp satisfies search problem Section sequence solution solvable solving space complexity Specifically steps strings Turing machine uniform uniformly distributed upper-bounded verifier vertex vertices whereas yes-instances yields zero-knowledge proofs Popular passagesPage 1 - When you start on your journey to Ithaca, then pray that the road is long, full of adventure, full of knowledge. References to this bookFrom other booksFrom Google ScholarAlgorithmic Information Theoretic Issues in Quantum Mechanics2004 - Arxiv preprint quant-ph/0110018 Most quantum states are too entangled to be useful as ...David Gross, Steven T Flammia, Jens Eisert Undirected Connectivity in Log-SpaceOMER REINGOLD - Journal of the ACM Bibliographic information
|