Relevant bibliographies by topics / Interactive proofs / Journal articles
To see the other types of publications on this topic, follow the link: Interactive proofs.

Journal articles on the topic 'Interactive proofs'

Author: Grafiati
Published: 4 June 2021
Last updated: 15 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Interactive proofs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Bellare, Mihir, Oded Goldreich, and Shafi Goldwasser. "Randomness in interactive proofs." Computational Complexity 3, no. 4 (December 1993): 319–54. http://dx.doi.org/10.1007/bf01275487.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Ayala-Rincón, Mauricio, and Thaynara Arielly de Lima. "Teaching Interactive Proofs to Mathematicians." Electronic Proceedings in Theoretical Computer Science 328 (October 30, 2020): 1–17. http://dx.doi.org/10.4204/eptcs.328.1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Boyar, Joan, Ivan Damgård, and René Peralta. "Short Non-Interactive Cryptographic Proofs." Journal of Cryptology 13, no. 4 (August 10, 2000): 449–72. http://dx.doi.org/10.1007/s001450010011.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Gur, Tom, and Ron D. Rothblum. "Non-interactive proofs of proximity." computational complexity 27, no. 1 (June 3, 2016): 99–207. http://dx.doi.org/10.1007/s00037-016-0136-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Cormode, Graham, Justin Thaler, and Ke Yi. "Verifying computations with streaming interactive proofs." Proceedings of the VLDB Endowment 5, no. 1 (September 2011): 25–36. http://dx.doi.org/10.14778/2047485.2047488.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Nishimura, Harumichi, and Tomoyuki Yamakami. "Interactive proofs with quantum finite automata." Theoretical Computer Science 568 (February 2015): 1–18. http://dx.doi.org/10.1016/j.tcs.2014.11.030.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

STRECKER, MARTIN. "Interactive and automated proofs for graph transformations." Mathematical Structures in Computer Science 28, no. 8 (July 27, 2018): 1333–62. http://dx.doi.org/10.1017/s096012951800021x.

Full text
Abstract:
This article explores methods to provide computer support for reasoning about graph transformations. We first define a general framework for representing graphs, graph morphisms and single graph rewriting steps. This setup allows for interactively reasoning about graph transformations. In order to achieve a higher degree of automation, we identify fragments of the graph description language in which we can reduce reasoning about global graph properties to reasoning about local properties, involving only a bounded number of nodes, which can be decided by Boolean satisfiability solving or even by deterministic computation of low complexity.
APA, Harvard, Vancouver, ISO, and other styles
8

Ben-Or, Michael, Avinatan Hassidim, and Haran Pilpel. "Quantum Multiprover Interactive Proofs with Communicating Provers." SIAM Journal on Computing 43, no. 3 (January 2014): 987–1011. http://dx.doi.org/10.1137/090777724.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Babai, László. "Bounded Round Interactive Proofs in Finite Groups." SIAM Journal on Discrete Mathematics 5, no. 1 (February 1992): 88–111. http://dx.doi.org/10.1137/0405008.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Galil, Zvi, Stuart Haber, and Moti Yung. "Minimum-Knowledge Interactive Proofs for Decision Problems." SIAM Journal on Computing 18, no. 4 (August 1989): 711–39. http://dx.doi.org/10.1137/0218049.

Full text
APA, Harvard, Vancouver, ISO, and other styles
11

Boppana, Ravi B., Johan Hastad, and Stathis Zachos. "Does co-NP have short interactive proofs?" Information Processing Letters 25, no. 2 (May 1987): 127–32. http://dx.doi.org/10.1016/0020-0190(87)90232-8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
12

Goldreich, Oded, Salil Vadhan, and Avi Wigderson. "On interactive proofs with a laconic prover." Computational Complexity 11, no. 1-2 (June 1, 2002): 1–53. http://dx.doi.org/10.1007/s00037-002-0169-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
13

Bledin, Justin. "Challenging epistemology: Interactive proofs and zero knowledge." Journal of Applied Logic 6, no. 4 (December 2008): 490–501. http://dx.doi.org/10.1016/j.jal.2008.09.002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
14

Watanabe, Yasunari, Kiran Gopinathan, George Pîrlea, Nadia Polikarpova, and Ilya Sergey. "Certifying the synthesis of heap-manipulating programs." Proceedings of the ACM on Programming Languages 5, ICFP (August 22, 2021): 1–29. http://dx.doi.org/10.1145/3473589.

Full text
Abstract:
Automated deductive program synthesis promises to generate executable programs from concise specifications, along with proofs of correctness that can be independently verified using third-party tools. However, an attempt to exercise this promise using existing proof-certification frameworks reveals significant discrepancies in how proof derivations are structured for two different purposes: program synthesis and program verification. These discrepancies make it difficult to use certified verifiers to validate synthesis results, forcing one to write an ad-hoc translation procedure from synthesis proofs to correctness proofs for each verification backend. In this work, we address this challenge in the context of the synthesis and verification of heap-manipulating programs. We present a technique for principled translation of deductive synthesis derivations (a.k.a. source proofs) into deductive target proofs about the synthesised programs in the logics of interactive program verifiers. We showcase our technique by implementing three different certifiers for programs generated via SuSLik, a Separation Logic-based tool for automated synthesis of programs with pointers, in foundational verification frameworks embedded in Coq: Hoare Type Theory (HTT), Iris, and Verified Software Toolchain (VST), producing concise and efficient machine-checkable proofs for characteristic synthesis benchmarks.
APA, Harvard, Vancouver, ISO, and other styles
15

Krebbers, Robbert, Amin Timany, and Lars Birkedal. "Interactive proofs in higher-order concurrent separation logic." ACM SIGPLAN Notices 52, no. 1 (May 11, 2017): 205–17. http://dx.doi.org/10.1145/3093333.3009855.

Full text
APA, Harvard, Vancouver, ISO, and other styles
16

Feige, Uriel, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. "Interactive proofs and the hardness of approximating cliques." Journal of the ACM 43, no. 2 (March 1996): 268–92. http://dx.doi.org/10.1145/226643.226652.

Full text
APA, Harvard, Vancouver, ISO, and other styles
17

Chlipala, Adam, Gregory Malecha, Greg Morrisett, Avraham Shinnar, and Ryan Wisnesky. "Effective interactive proofs for higher-order imperative programs." ACM SIGPLAN Notices 44, no. 9 (August 31, 2009): 79–90. http://dx.doi.org/10.1145/1631687.1596565.

Full text
APA, Harvard, Vancouver, ISO, and other styles
18

Kempe, Julia, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick. "Using Entanglement in Quantum Multi-Prover Interactive Proofs." computational complexity 18, no. 2 (June 2009): 273–307. http://dx.doi.org/10.1007/s00037-009-0275-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
19

Ito, Tsuyoshi. "Parallelization of entanglement-resistant multi-prover interactive proofs." Information Processing Letters 114, no. 10 (October 2014): 579–83. http://dx.doi.org/10.1016/j.ipl.2014.05.005.

Full text
APA, Harvard, Vancouver, ISO, and other styles
20

Yamakami, Tomoyuki. "Constant-space quantum interactive proofs against multiple provers." Information Processing Letters 114, no. 11 (November 2014): 611–19. http://dx.doi.org/10.1016/j.ipl.2014.05.012.

Full text
APA, Harvard, Vancouver, ISO, and other styles
21

AlTawy, Riham, and Guang Gong. "Mesh: A Supply Chain Solution with Locally Private Blockchain Transactions." Proceedings on Privacy Enhancing Technologies 2019, no. 3 (July 1, 2019): 149–69. http://dx.doi.org/10.2478/popets-2019-0041.

Full text
Abstract:
Abstract A major line of research on blockchains is geared towards enhancing the privacy of transactions through anonymity using generic non-interactive proofs. However, there is a good cluster of application scenarios where complete anonymity is not desirable and accountability is in fact required. In this work, we utilize non-interactive proofs of knowledge of elliptic curve discrete logarithms to present membership and verifiable encryption proof, which offers plausible anonymity when combined with the regular signing process of the blockchain transactions. The proof system requires no trusted setup, both its communication and computation complexities are linear in the number of set members, and its security relies on the discrete logarithm assumption. As a use-case for this scenario, we present Mesh which is a blockchain-based framework for supply chain management using RFIDs. Finally, the confidentiality of the transacted information is realized using a lightweight key chaining mechanism implemented on RFIDs. We formally define and prove the main security features of the protocol, and report on experiments for evaluating the performance of the modified transactions for this system.
APA, Harvard, Vancouver, ISO, and other styles
22

Goldreich, Oded, and Johan Håstad. "On the complexity of interactive proofs with bounded communication." Information Processing Letters 67, no. 4 (August 1998): 205–14. http://dx.doi.org/10.1016/s0020-0190(98)00116-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
23

Kobayashi, Hirotada, François Le Gall, and Harumichi Nishimura. "Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete." SIAM Journal on Computing 44, no. 2 (January 2015): 243–89. http://dx.doi.org/10.1137/140971944.

Full text
APA, Harvard, Vancouver, ISO, and other styles
24

Bitansky, Nir. "Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs." Journal of Cryptology 33, no. 2 (September 4, 2019): 459–93. http://dx.doi.org/10.1007/s00145-019-09331-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
25

Andrews, Peter B., and Chad E. Brown. "TPS: A hybrid automatic-interactive system for developing proofs." Journal of Applied Logic 4, no. 4 (December 2006): 367–95. http://dx.doi.org/10.1016/j.jal.2005.10.002.

Full text
APA, Harvard, Vancouver, ISO, and other styles
26

Tang, ChunMing, DingYi Pei, XiaoFeng Wang, and ZhuoJun Liu. "Delegateable signatures based on non-interactive witness indistinguishable and non-interactive witness hiding proofs." Science in China Series F: Information Sciences 51, no. 2 (February 2008): 128–44. http://dx.doi.org/10.1007/s11432-008-0003-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
27

Pham, Tuan Minh, and Yves Bertot. "A Combination of a Dynamic Geometry Software With a Proof Assistant for Interactive Formal Proofs." Electronic Notes in Theoretical Computer Science 285 (September 2012): 43–55. http://dx.doi.org/10.1016/j.entcs.2012.06.005.

Full text
APA, Harvard, Vancouver, ISO, and other styles
28

Lee, Youngkyung, Dong Hoon Lee, and Jong Hwan Park. "Revisiting NIZK-Based Technique for Chosen-Ciphertext Security: Security Analysis and Corrected Proofs." Applied Sciences 11, no. 8 (April 8, 2021): 3367. http://dx.doi.org/10.3390/app11083367.

Full text
Abstract:
Non-interactive zero-knowledge (NIZK) proofs for chosen-ciphertext security are generally considered to give an impractical construction. An interesting recent work by Seo, Abdalla, Lee, and Park (Information Sciences, July 2019) proposed an efficient semi-generic conversion method for achieving chosen-ciphertext security based on NIZK proofs in the random oracle model. The recent work by Seo et al. demonstrated that the semi-generic conversion method transforms a one-way (OW)-secure key encapsulation mechanism (KEM) into a chosen-ciphertext secure KEM while preserving tight security reduction. This paper shows that the security analysis of the semi-generic conversion method has a flaw, which comes from the OW security condition of the underlying KEM. Without changing the conversion method, this paper presents a revised security proof under the changed conditions that (1) the underlying KEM must be chosen-plaintext secure in terms of indistinguishability and (2) an NIZK proof derived from the underlying KEM via the Fiat–Shamir transform must have the properties of zero-knowledge and simulation soundness. This work extended the security proof strategy to the case of identity-based KEM (IBKEM) and also revise the security proof for IBKEM of previous method by Seo et al. Finally, this work gives a corrected security proof by applying the new proofs to several existing (IB)KEMs.
APA, Harvard, Vancouver, ISO, and other styles
29

Babai, László, and Shlomo Moran. "Proving properties of interactive proofs by a generalized counting technique." Information and Computation 82, no. 2 (August 1989): 185–97. http://dx.doi.org/10.1016/0890-5401(89)90053-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
30

Pavan, A., Alan L. Selman, Samik Sengupta, and N. V. Vinodchandran. "Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy." Theoretical Computer Science 385, no. 1-3 (October 2007): 167–78. http://dx.doi.org/10.1016/j.tcs.2007.06.013.

Full text
APA, Harvard, Vancouver, ISO, and other styles
31

Hayden, Patrick, Kevin Milner, and Mark M. Wilde. "Two-message quantum interactive proofs and the quantum separability problem." Quantum Information and Computation 14, no. 5&6 (May 2014): 384–416. http://dx.doi.org/10.26421/qic14.5-6-2.

Full text
Abstract:
Suppose that a polynomial-time mixed-state quantum circuit, described as a sequence of local unitary interactions followed by a partial trace, generates a quantum state shared between two parties. One might then wonder, does this quantum circuit produce a state that is separable or entangled? Here, we give evidence that it is computationally hard to decide the answer to this question, even if one has access to the power of quantum computation. We begin by exhibiting a two-message quantum interactive proof system that can decide the answer to a promise version of the question. We then prove that the promise problem is hard for the class of promise problems with "quantum statistical zero knowledge" QSZK proof systems by demonstrating a polynomial-time Karp reduction from the QSZK-complete promise problem "quantum state distinguishability" to our quantum separability problem. By exploiting Knill's efficient encoding of a matrix description of a state into a description of a circuit to generate the state, we can show that our promise problem is NP-hard with respect to Cook reductions. Thus, the quantum separability problem (as phrased above) constitutes the first nontrivial promise problem decidable by a two-message quantum interactive proof system while being hard for both NP and QSZK. We also consider a variant of the problem, in which a given polynomial-time mixed-state quantum circuit accepts a quantum state as input, and the question is to decide if there is an input to this circuit which makes its output separable across some bipartite cut. We prove that this problem is a complete promise problem for the class QIP of problems decidable by quantum interactive proof systems. Finally, we show that a two-message quantum interactive proof system can also decide a multipartite generalization of the quantum separability problem.
APA, Harvard, Vancouver, ISO, and other styles
32

Berger, Ulrich, Alison Jones, and Monika Seisenberger. "Program extraction applied to monadic parsing." Journal of Logic and Computation 29, no. 4 (June 6, 2019): 487–518. http://dx.doi.org/10.1093/logcom/exv078.

Full text
Abstract:
Abstract This article outlines a proof-theoretic approach to developing correct and terminating monadic parsers. Using modified realizability, we extract formally verified and terminating programs from formal proofs. By extracting both primitive parsers and parser combinators, it is ensured that all complex parsers built from these are also correct, complete and terminating for any input. We demonstrate the viability of our approach by means of two case studies: we extract (i) a small arithmetic calculator and (ii) a non-deterministic natural language parser. The work is being carried out in the interactive proof system Minlog.
APA, Harvard, Vancouver, ISO, and other styles
33

Zhou, Fucai, Yuxi Li, Qingshi Zhou, Jingwei Miao, and Jian Xu. "The electronic cash system based on non-interactive zero-knowledge proofs." International Journal of Computer Mathematics 93, no. 2 (July 15, 2014): 239–57. http://dx.doi.org/10.1080/00207160.2014.933816.

Full text
APA, Harvard, Vancouver, ISO, and other styles
34

Kramer, Simon. "Logic of Intuitionistic Interactive Proofs (Formal Theory of Perfect Knowledge Transfer)." ACM Transactions on Computational Logic 16, no. 4 (November 19, 2015): 1–32. http://dx.doi.org/10.1145/2811263.

Full text
APA, Harvard, Vancouver, ISO, and other styles
35

Kramer, Simon. "Logic of Negation-Complete Interactive Proofs (Formal Theory of Epistemic Deciders)." Electronic Notes in Theoretical Computer Science 300 (January 2014): 47–70. http://dx.doi.org/10.1016/j.entcs.2013.12.011.

Full text
APA, Harvard, Vancouver, ISO, and other styles
36

Baartse, Martijn, and Klaus Meer. "Interactive proofs and a Shamir-like result for real number computations." computational complexity 28, no. 3 (November 7, 2018): 437–69. http://dx.doi.org/10.1007/s00037-018-0174-6.

Full text
APA, Harvard, Vancouver, ISO, and other styles
37

WANG, B., and Z. SONG. "A non-interactive deniable authentication scheme based on designated verifier proofs." Information Sciences 179, no. 6 (March 1, 2009): 858–65. http://dx.doi.org/10.1016/j.ins.2008.11.011.

Full text
APA, Harvard, Vancouver, ISO, and other styles
38

Barendregt, Henk, and Freek Wiedijk. "The challenge of computer mathematics." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 363, no. 1835 (September 12, 2005): 2351–75. http://dx.doi.org/10.1098/rsta.2005.1650.

Full text
Abstract:
Progress in the foundations of mathematics has made it possible to formulate all thinkable mathematical concepts, algorithms and proofs in one language and in an impeccable way. This is not in spite of, but partially based on the famous results of Gödel and Turing. In this way statements are about mathematical objects and algorithms, proofs show the correctness of statements and computations, and computations are dealing with objects and proofs. Interactive computer systems for a full integration of defining, computing and proving are based on this. The human defines concepts, constructs algorithms and provides proofs, while the machine checks that the definitions are well formed and the proofs and computations are correct. Results formalized so far demonstrate the feasibility of this ‘computer mathematics’. Also there are very good applications. The challenge is to make the systems more mathematician-friendly, by building libraries and tools. The eventual goal is to help humans to learn, develop, communicate, referee and apply mathematics.
APA, Harvard, Vancouver, ISO, and other styles
39

Krebbers, Robbert, Jacques-Henri Jourdan, Ralf Jung, Joseph Tassarotti, Jan-Oliver Kaiser, Amin Timany, Arthur Charguéraud, and Derek Dreyer. "MoSeL: a general, extensible modal framework for interactive proofs in separation logic." Proceedings of the ACM on Programming Languages 2, ICFP (July 30, 2018): 1–30. http://dx.doi.org/10.1145/3236772.

Full text
APA, Harvard, Vancouver, ISO, and other styles
40

Kim, Myungsun, and Hyung Tae Lee. "Experimenting With Non-Interactive Range Proofs Based on the Strong RSA Assumption." IEEE Access 7 (2019): 117505–16. http://dx.doi.org/10.1109/access.2019.2936210.

Full text
APA, Harvard, Vancouver, ISO, and other styles
41

Coquand, Thierry. "A semantics of evidence for classical arithmetic." Journal of Symbolic Logic 60, no. 1 (March 1995): 325–37. http://dx.doi.org/10.2307/2275524.

Full text
Abstract:
If it is difficult to give the exact significance of consistency proofs from a classical point of view, in particular the proofs of Gentzen [2, 6], and Novikoff [14], the motivations of these proofs are quite clear intuitionistically. Their significance is then less to give a mere consistency proof than to present an intuitionistic explanation of the notion of classical truth. Gentzen for instance summarizes his proof as follows [6]: “Thus propositions of actualist mathematics seem to have a certain utility, but no sense. The major part of my consistency proof, however, consists precisely in ascribing a finitist sense to actualist propositions.” From this point of view, the main part of both Gentzen's and Novikoff's arguments can be stated as establishing that modus ponens is valid w.r.t. this interpretation ascribing a “finitist sense” to classical propositions.In this paper, we reformulate Gentzen's and Novikoff's “finitist sense” of an arithmetic proposition as a winning strategy for a game associated to it. (To see a proof as a winning strategy has been considered by Lorenzen [10] for intuitionistic logic.) In the light of concurrency theory [7], it is tempting to consider a strategy as an interactive program (which represents thus the “finitist sense” of an arithmetic proposition). We shall show that the validity of modus ponens then gets a quite natural formulation, showing that “internal chatters” between two programs end eventually.We first present Novikoff's notion of regular formulae, that can be seen as an intuitionistic truth definition for classical infinitary propositional calculus. We use this in order to motivate the second part, which presents a game-theoretic interpretation of the notion of regular formulae, and a proof of the admissibility of modus ponens which is based on this interpretation.
APA, Harvard, Vancouver, ISO, and other styles
42

Martín-Fernández, Francisco, Pino Caballero-Gil, and Cándido Caballero-Gil. "Authentication Based on Non-Interactive Zero-Knowledge Proofs for the Internet of Things." Sensors 16, no. 1 (January 7, 2016): 75. http://dx.doi.org/10.3390/s16010075.

Full text
APA, Harvard, Vancouver, ISO, and other styles
43

Goldreich, Oded, and Tom Gur. "Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP." Theoretical Computer Science 878-879 (July 2021): 83–101. http://dx.doi.org/10.1016/j.tcs.2021.05.030.

Full text
APA, Harvard, Vancouver, ISO, and other styles
44

el Mimouni, Sanae, and Mohamed Bouhdadi. "Event Based Formalization of Communication Properties for an E-Commerce Protocol: An Event-B Approach." International Journal of Engineering Research in Africa 37 (August 2018): 78–90. http://dx.doi.org/10.4028/www.scientific.net/jera.37.78.

Full text
Abstract:
The objective of this paper aims at modeling and analysis of communication properties of an E-commerce protocol with the Event-B language. NetBill protocol is developed for selling and buying of information and goods through the Internet. In this approach, we have used Event-B as proof-based development method which integrates proof techniques for writing specifications and building the model systematically using refinement, the key point is to start with a very abstract model of the system under development. Step by step details are added to this first model by building a series of more concrete ones. This strategy eases the proof of the correctness of requirements because only a small number of proof obligations are generated at each step. The aims are constructing a model with a clear and accurate formulation of the communication protocol properties and discharge of all proof obligations. The outcome of this procedure was that we achieved a very high degree of automatic proof. We reached a good degree of automatic proof. All interactive proofs involved a small number of steps and were straightforward to reach.
APA, Harvard, Vancouver, ISO, and other styles
45

STRUTH, GEORG. "Hoare Semigroups." Mathematical Structures in Computer Science 28, no. 6 (April 4, 2017): 775–99. http://dx.doi.org/10.1017/s096012951700007x.

Full text
Abstract:
A semigroup-based setting for developing Hoare logics and refinement calculi is introduced together with procedures for translating between verification and refinement proofs. A new Hoare logic for multirelations and two minimalist generic verification and refinement components, implemented in an interactive theorem prover, are presented as applications that benefit from this generalisation.
APA, Harvard, Vancouver, ISO, and other styles
46

Yuan Zhou and Haifeng Qian. "Practical round-optimal blind signatures without random oracles or non-interactive zero-knowledge proofs." Security and Communication Networks 5, no. 7 (September 1, 2011): 764–75. http://dx.doi.org/10.1002/sec.371.

Full text
APA, Harvard, Vancouver, ISO, and other styles
47

Lee, Ciarán M., and Matty J. Hoban. "Bounds on the power of proofs and advice in general physical theories." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 472, no. 2190 (June 2016): 20160076. http://dx.doi.org/10.1098/rspa.2016.0076.

Full text
Abstract:
Quantum theory presents us with the tools for computational and communication advantages over classical theory. One approach to uncovering the source of these advantages is to determine how computation and communication power vary as quantum theory is replaced by other operationally defined theories from a broad framework of such theories. Such investigations may reveal some of the key physical features required for powerful computation and communication. In this paper, we investigate how simple physical principles bound the power of two different computational paradigms which combine computation and communication in a non-trivial fashion: computation with advice and interactive proof systems. We show that the existence of non-trivial dynamics in a theory implies a bound on the power of computation with advice. Moreover, we provide an explicit example of a theory with no non-trivial dynamics in which the power of computation with advice is unbounded. Finally, we show that the power of simple interactive proof systems in theories where local measurements suffice for tomography is non-trivially bounded. This result provides a proof that Q M A is contained in P P , which does not make use of any uniquely quantum structure—such as the fact that observables correspond to self-adjoint operators—and thus may be of independent interest.
APA, Harvard, Vancouver, ISO, and other styles
48

Wang, Hong, and Shi Min Wei. "Public Watermark Detection Resistant to Sensitivity Attacks." Key Engineering Materials 474-476 (April 2011): 1865–68. http://dx.doi.org/10.4028/www.scientific.net/kem.474-476.1865.

Full text
Abstract:
A public watermark detection scheme using verifiable secret sharing is proposed. It removes the expensive zero-knowledge interactive proofs and replaces the traditional trusted third party with a group of proxies. Moreover, the scheme is secure against sensitivity attacks and very efficient in terms of computation cost, the number of rounds and bandwidth required in the communications.
APA, Harvard, Vancouver, ISO, and other styles
49

MIMRAM, SAMUEL. "The structure of first-order causality." Mathematical Structures in Computer Science 21, no. 1 (January 24, 2011): 65–110. http://dx.doi.org/10.1017/s0960129510000459.

Full text
Abstract:
Game semantics describe the interactive behaviour of proofs by interpreting formulas as games on which proofs induce strategies. Such a semantics is introduced here for capturing dependencies induced by quantifications in first-order propositional logic. One of the main difficulties that has to be faced during the elaboration of this kind of semantics is to characterise definable strategies, that is, strategies that actually behave like a proof. This is usually done by restricting the model to strategies satisfying subtle combinatorial conditions, whose preservation under composition is often difficult to show. In this paper we present an original methodology to achieve this task, which requires a combination of advanced tools from game semantics, rewriting theory and categorical algebra. We introduce a diagrammatic presentation of the monoidal category of definable strategies of our model using generators and relations: these strategies can be generated from a finite set of atomic strategies, and the equality between strategies admits a finite axiomatisation, and this equational structure corresponds to a polarised variation of the bialgebra notion. The work described in this paper thus forms a bridge between algebra and denotational semantics in order to reveal the structure of dependencies induced by first-order quantifiers, and lays the foundations for a mechanised analysis of causality in programming languages.
APA, Harvard, Vancouver, ISO, and other styles
50

Bourke, Timothy, Paul Jeanmaire, Basile Pesin, and Marc Pouzet. "Verified Lustre Normalization with Node Subsampling." ACM Transactions on Embedded Computing Systems 20, no. 5s (October 31, 2021): 1–25. http://dx.doi.org/10.1145/3477041.

Full text
Abstract:
Dataflow languages allow the specification of reactive systems by mutually recursive stream equations, functions, and boolean activation conditions called clocks. Lustre and Scade are dataflow languages for programming embedded systems. Dataflow programs are compiled by a succession of passes. This article focuses on the normalization pass which rewrites programs into the simpler form required for code generation. Vélus is a compiler from a normalized form of Lustre to CompCert’s Clight language. Its specification in the Coq interactive theorem prover includes an end-to-end correctness proof that the values prescribed by the dataflow semantics of source programs are produced by executions of generated assembly code. We describe how to extend Vélus with a normalization pass and to allow subsampled node inputs and outputs. We propose semantic definitions for the unrestricted language, divide normalization into three steps to facilitate proofs, adapt the clock type system to handle richer node definitions, and extend the end-to-end correctness theorem to incorporate the new features. The proofs require reasoning about the relation between static clock annotations and the presence and absence of values in the dynamic semantics. The generalization of node inputs requires adding a compiler pass to ensure the initialization of variables passed in function calls.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Interactive proofs' for other source types:
Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography