Academic literature on the topic 'Arthur-Merlin'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Arthur-Merlin.'
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.
Journal articles on the topic "Arthur-Merlin"
Santha, Miklos. "Relativized Arthur-Merlin versus Merlin-Arthur games." Information and Computation 80, no. 1 (January 1989): 44–49. http://dx.doi.org/10.1016/0890-5401(89)90022-9.
Full textMorimae, Tomoyuki, Masahito Hayashi, Harumichi Nishimura, and Keisuke Fujii. "Quantum Merlin-Arthur with Clifford Arthur." Quantum Information and Computation 15, no. 15&16 (November 2015): 1420–30. http://dx.doi.org/10.26421/qic15.15-16-10.
Full textMarriott, Chris, and John Watrous. "Quantum Arthur–Merlin games." computational complexity 14, no. 2 (June 2005): 122–52. http://dx.doi.org/10.1007/s00037-005-0194-x.
Full textGur, Tom, and Ran Raz. "Arthur–Merlin streaming complexity." Information and Computation 243 (August 2015): 145–65. http://dx.doi.org/10.1016/j.ic.2014.12.011.
Full textCAI, JIN-YI, DENIS CHARLES, A. PAVAN, and SAMIK SENGUPTA. "ON HIGHER ARTHUR-MERLIN CLASSES." International Journal of Foundations of Computer Science 15, no. 01 (February 2004): 3–19. http://dx.doi.org/10.1142/s0129054104002273.
Full textVINODCHANDRAN, N. V. "NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES." International Journal of Foundations of Computer Science 16, no. 06 (December 2005): 1297–308. http://dx.doi.org/10.1142/s0129054105003819.
Full textKobayashi, Hirotada, François Le Gall, and Harumichi Nishimura. "Generalized Quantum Arthur--Merlin Games." SIAM Journal on Computing 48, no. 3 (January 2019): 865–902. http://dx.doi.org/10.1137/17m1160173.
Full textChakaravarthy, Venkatesan T., and Sambuddha Roy. "Arthur and Merlin as Oracles." computational complexity 20, no. 3 (August 5, 2011): 505–58. http://dx.doi.org/10.1007/s00037-011-0015-3.
Full textWatson, Thomas. "Quadratic Simulations of Merlin–Arthur Games." ACM Transactions on Computation Theory 12, no. 2 (May 14, 2020): 1–11. http://dx.doi.org/10.1145/3389399.
Full textSanthanam, Rahul. "Circuit Lower Bounds for Merlin–Arthur Classes." SIAM Journal on Computing 39, no. 3 (January 2009): 1038–61. http://dx.doi.org/10.1137/070702680.
Full textDissertations / Theses on the topic "Arthur-Merlin"
Drucker, Andrew Donald. "PCPs for Arthur-Merlin games and communication protocols." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/60160.
Full textIncludes bibliographical references (p. 59-62).
Probabilistically Checkable Proofs (PCPs) are an important class of proof systems that have played a key role in computational complexity theory. In this thesis we study the power of PCPs in two new settings: Arthur-Merlin games and communication protocols. In the first part of the thesis, we give a 'PCP characterization' of AM analogous to the PCP Theorem for NP. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, and for PSPACE; however, we suggest that the result for AM might be of particular significance for attempts to derandomnize this class. To test this notion, we pose some 'Randomized Optimization Hypotheses' related to our stochastic CSPs that (in light of our result) would imply collapse results for AM. Unfortunately, the hypotheses appear over-strong, and we present evidence against them. In the process we show that. if some language in NP is hard-on-average against circuits of size 2 [omega](n), en there exist hard-on-average optimization problems of a particularly elegant form. In the second part of the thesis, we study PCPs in the setting of communication protocols. Using techniques inspired by Dinur's proof of the PCP Theorem. we show that functions f (X, y) with nondeterministic circuits of size i have -distributed PCP protocols' of proof length O(poly(m)) in which each verifier looks at a constant number of proof positions. We show a complementary negative result: a distributed PCP protocol using a proof of length f, in which Alice and Bob look at k bits of the proof while exchanging t bits of communication, can be converted into a PCP-free randomized protocol with communication bounded by In both parts of the thesis, our proofs make use of a powerful form of PCPs known as Probabilistically Checkable Proofs of Proximity. and demonstrate their versatility. In our work on Arthur-Merlin games, we also use known results on randomness-efficient soundness- and hardness-amplification. In particular, we make essential use of the Impagliazzo-Wigderson generator; our analysis relies on a recent Chernoff-type theorem for expander walks.
by Andrew Donald Drucker.
S.M.
Cretoiu, Elena. "La Suite du Roman de Merlin éditée d'après un manuscrit du XVe siècle : (Paris, BNF, fr. 112)." Thesis, Strasbourg, 2014. http://www.theses.fr/2014STRAC001.
Full textThe fragment of the Suite du Roman de Merlin that we edited is preserved in four manuscripts (London manuscript, British Library, Additional 38117, the Cambridge University Library manuscript, Additional 7071, the BNF 112 manuscript, which is the main manuscript of our edition, and the Imola manuscript, Biblioteca Comunale, ms. 135 AA25 n° 9 (7)). Comparing to the other three already existing editions of the Suite (O. Sommer, Die Abenteuer Gawains Ywains und Le Morholts mit Den Drei Jungfrauen (Zeitschrift für Romanische Philologie, Beiheft 47, 1913), P. C. Smith (Les enchantemenz de Bretagne, Chapel Hill, 1977), edition based upon the Cambridge manuscript, and G. Roussineau (La Suite du Roman de Merlin, Droz, 1996), edition mainly based upon the London manuscript), the aim of our edition is to offer a text of the Suite du Roman de Merlin based upon the BNF 112 manuscript, according to the modern principles applied in the transcription of the medieval texts. We offered a great number of variants given by the other manuscritpts of the Suite and limited our interference with the text only for corrections which we considered strictly necessary. The text of our edition is followed by notes, a glossary and an index of names. On the linguistic level, we noted regional caracteristics that lead us to consider that our manuscript belongs to the North domain (conseilh ; karoloient, etc.), modern structures comparing to the other manuscripts of the Suite and a certain number of termes (baudel ; pourvillier) which can improve the DMF (Dictionnaire du Moyen Français) basis
Santha, Miklos. "Contributions à l'étude des structures aléatoires et des méthodes probabilistes." Paris 11, 1988. http://www.theses.fr/1988PA112057.
Full textThis thesis contains a few contributions to the study of randomness and probabilistic methods in theoretical computer science. Some of them deal with random sequences and probabilistic complexity classes, the others with concrete problems. We introduce a new mathematical model of imperfect physical sources of randomness and we show how to convert the output of these sources into quasi-random sequences which are indistinguish able from truly random ones in a strong sense. We show the existence of pseudo-random number generators which can reduce efficiently the error probability in probabilistic algorithms. We present a separation result for the relativized interactive probabilistic proof-systems. We study in a probabilistic model the optimal distribution of processors in a network, when they are subject to failure. We compute the radius of certain graphs on alphabets and we obtain tight bounds on the parallel complexity of the searching problem in multi-dimensional cubes by using proba bilistic arguments
Chardonnens, Noémie. "L'autre du même : emprunts et répétitions dans le Roman de Perceforest." Thesis, Paris 3, 2014. http://www.theses.fr/2014PA030066.
Full textThe Roman de Perceforest, the longest known text from the Middle Ages, aims to describe the life of Arthur's pre-christian ancestors and knights, presenting them as descendants of Alexander the Great. Along the storytelling, a genuine poetics of external and internal repetition takes place: the Perceforest's authors multiply the references to previous texts belonging to several materials, integrating sometimes entire parts of other texts. Furthermore the narrative reproduces its own patterns and particular sequences in different places of the text. Throughout this research, we consider the influence of such repetition aesthetics on the literary genre definition, on its construction as well as on the reader's reception. In this dissertation, we explore a specific category of repetitions where pre-existing sequences are embedded in a narrative context that differs from the original context of occurrence, which we called emprunt(s). Reviewing the species of inter- and intra-textual recurrences occurring within the text, we reveal some overlooked aspects of the consistency, the specificity of the Perceforest and its author's idea of writing, striving to groundwork on general theory of «emprunts» that shall thereby be laid
Bacon, Edwin Bruce. "Confronting eternity : strange (im)mortalities, and states of undying in popular fiction." Thesis, University of Canterbury. English, 2014. http://hdl.handle.net/10092/9680.
Full textBlier, Hugue. "Preuves interactives classiques." Thèse, 2006. http://hdl.handle.net/1866/16728.
Full textBlier, Hugue. "Preuves interactives quantiques." Thèse, 2009. http://hdl.handle.net/1866/3567.
Full textThis thesis is devoted to complexity theory based on the interactive proof paradigm. All classes defined in this way involve one or many infinitely powerful provers attempting to convince a verifier of limited power that a string belongs to a certain language. We will consider the classical model, in which the various participants are Turing machines, as well as the quantum model, in which they are quantum circuits. The literature review included in this thesis assume that the reader is familiar with the basics of complexity theory and quantum computing. This thesis presents the original result that the class NP can be characterized by a class of quantum interactive proofs of logarithmic size. The various classes are presented in an order that facilitates the treatment of interactive classes. The first chapter is devoted to the basic complexity classes; these will be useful points of comparison for classes presented subsequently. Chapters two and three respectively present classes with one and many provers. The presentation of the result mentioned above is the object of chapter four.
Books on the topic "Arthur-Merlin"
Thouard, Jean-Louis, and Viviane Koenig. La légende de Merlin l'enchanteur et du roi Arthur. Paris: La Martinière jeunesse, 2009.
Find full textBruchési, Louise. Viens voir Merlin (légende du Roi Arthur): Hamlet (exercices). Laval, QC: Théâtre d'art du Québec, 2011.
Find full textNames from the dawn of British legend: Taliesin, Aneirin, Myrddin/Merlin, Arthur. Felinfach, Lampeter, Dyfed, Wales: Llanerch Publishers, 1994.
Find full textThomas, Malory. The Book Of Merlin, The Book Of Sir Balin From Malory's King Arthur With Caxton's Preface. Whitefish, Montana: Kessinger Publishing, LLC, 2007.
Find full textThomas, Malory. The Book Of Merlin, The Book Of Sir Balin From Malory's King Arthur With Caxton's Preface. Whitefish, Montana: Kessinger Publishing, LLC, 2007.
Find full textBlair, J. M. C. The Pendragon murders: A Merlin investigation. New York: Berkley Pub. Group, 2010.
Find full textBook chapters on the topic "Arthur-Merlin"
Santha, Miklos. "Relativized Arthur-Merlin versus Merlin-Arthur games." In Lecture Notes in Computer Science, 435–42. Berlin, Heidelberg: Springer Berlin Heidelberg, 1987. http://dx.doi.org/10.1007/3-540-18625-5_66.
Full textGur, Tom, and Ran Raz. "Arthur-Merlin Streaming Complexity." In Automata, Languages, and Programming, 528–39. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-39206-1_45.
Full textCai, Jin-Yi, Denis Charles, A. Pavan, and Samik Sengupta. "On Higher Arthur-Merlin Classes." In Lecture Notes in Computer Science, 18–27. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45655-4_4.
Full textWatson, Thomas. "Quadratic Simulations of Merlin–Arthur Games." In LATIN 2018: Theoretical Informatics, 864–72. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-77404-6_62.
Full textFraigniaud, Pierre, Pedro Montealegre, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. "On Distributed Merlin-Arthur Decision Protocols." In Structural Information and Communication Complexity, 230–45. Cham: Springer International Publishing, 2019. http://dx.doi.org/10.1007/978-3-030-24922-9_16.
Full textLu, Chi-Jen. "Derandomizing Arthur-Merlin Games under Uniform Assumptions." In Algorithms and Computation, 302–12. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-40996-3_26.
Full textDiehl, Scott. "Lower Bounds for Swapping Arthur and Merlin." In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 449–63. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. http://dx.doi.org/10.1007/978-3-540-74208-1_33.
Full textSelvam, Vyas Ram. "The Two Queries Assumption and Arthur-Merlin Classes." In Mathematical Foundations of Computer Science 2014, 601–12. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44465-8_51.
Full textKobayashi, Hirotada, Keiji Matsumoto, and Tomoyuki Yamakami. "Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?" In Algorithms and Computation, 189–98. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-24587-2_21.
Full textTorán, Jacobo. "Arthur-Merlin Games and the Problem of Isomorphism Testing." In New Computational Paradigms, 495–506. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11494645_61.
Full textConference papers on the topic "Arthur-Merlin"
Klauck, Hartmut. "On Arthur Merlin Games in Communication Complexity." In 2011 IEEE Annual Conference on Computational Complexity (CCC). IEEE, 2011. http://dx.doi.org/10.1109/ccc.2011.33.
Full textSanthanam, Rahul. "Circuit lower bounds for Merlin-Arthur classes." In the thirty-ninth annual ACM symposium. New York, New York, USA: ACM Press, 2007. http://dx.doi.org/10.1145/1250790.1250832.
Full textPass, Rafael, and Muthuramakrishnan Venkitasubramaniam. "An efficient parallel repetition theorem for Arthur-Merlin games." In the thirty-ninth annual ACM symposium. New York, New York, USA: ACM Press, 2007. http://dx.doi.org/10.1145/1250790.1250853.
Full textGöös, Mika, Toniann Pitassi, and Thomas Watson. "Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication." In ITCS'15: Innovations in Theoretical Computer Science. New York, NY, USA: ACM, 2015. http://dx.doi.org/10.1145/2688073.2688074.
Full textAydinlioglu, Baris, and Dieter van Melkebeek. "Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games." In 2012 IEEE Conference on Computational Complexity (CCC). IEEE, 2012. http://dx.doi.org/10.1109/ccc.2012.32.
Full textGutfreund, Dan, and Akinori Kawachi. "Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds." In 2010 IEEE 25th Annual Conference on Computational Complexity (CCC). IEEE, 2010. http://dx.doi.org/10.1109/ccc.2010.13.
Full textHarrow, Aram W., and Ashley Montanaro. "An Efficient Test for Product States with Applications to Quantum Merlin-Arthur Games." In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2010. http://dx.doi.org/10.1109/focs.2010.66.
Full text