%% Theory of Computing
%% File: v018a013.bib
%% Publication date: June 7, 2022
%% Authors: Maya Leshkowitz
%
%
%
%


@inproceedings{B,
	author		=	{Babai, L\'aszl\'o},
	title		= 	{Trading Group Theory for Randomness},
	crossref 	= 	{pstoc85},
	pages		= 	{421--429},
	doi		=	{10.1145/22145.22192},
}


@article{BGG,
	author    = {Bellare, Mihir and Goldreich, Oded and Goldwasser, Shafi},
	title     = {Randomness in interactive proofs},
	journal   = ccomplex,
	number    = {4},
	volume    = {3},
	pages     = {319--354},
	year      = {1993},
	doi	  = {10.1007/BF01275487},
}


@article{BM,
	author	=	{Babai, L\'aszl\'o and Moran, Shlomo},
	title	=	{Arthur--{M}erlin games: {A} randomized proof system and a hierarchy of complexity classes},
	journal = 	jcss,
	volume	=	{36},
	number	=	{2},
	pages	=	{254--276},
	year	= 	{1988},
	doi	=	{10.1016/0022-0000(88)90028-1},
}

@incollection{FGMSZ,
	author    = {Martin F{\"{u}}rer and Oded Goldreich and Yishay Mansour and Michael Sipser and Stathis Zachos},
title     = {On Completeness and Soundness in Interactive Proof Systems},
  booktitle     = {Randomness and Computation},
  series        = AdvComputRes,
  volume        = {5},
  publisher     = {JAI Press},
  editor        = {Silvio Micali},
  pages         = {429--442},
  year          = {1989},
note = {\href{https://www.wisdom.weizmann.ac.il/~oded/PSX/fgmsz.pdf}{Author's website}},
}


@book{G:cc,
	author    = {Goldreich, Oded},
title     = {Computational {C}omplexity - {A} {C}onceptual {P}erspective},
	publisher = {Cambridge {U}niversity {P}ress},
	year      = {2008},
	addresses = {Cambridge},
	doi	  = {10.1017/CBO9780511804106},
}

@article{GL-eccc,
	author    = {Goldreich, Oded and Leshkowitz, Maya},
title     = {On {E}mulating {I}nteractive {P}roofs with {P}ublic {C}oins},
	journal   = eccc,
	volume    = {TR16-066},                  
	year      = {2016},
        eprint    = {ecccprimary:TR16-066},
}

@incollection{GL,
	author    = {Goldreich, Oded and Leshkowitz, Maya},
	editor 	  = {Goldreich, Oded},
title     = {On Emulating Interactive Proofs with Public Coins},
	booktitle = {Computational {C}omplexity and {P}roperty {T}esting: {O}n the {I}nterplay {B}etween {R}andomness and {C}omputation},
	publisher = springer,
	pages     = {178--198},
	year      = {2020},
	doi       = {10.1007/978-3-030-43662-9\_12},
        eprint    = {eccc:TR16-066},
}


@article{GMW,
	author    = {Goldreich, Oded and Micali, Silvio and Wigderson, Avi},
	title     = {Proofs that Yield Nothing But Their Validity or All Languages in {NP} Have Zero-Knowledge Proof Systems},
	journal   = jacm,
	volume    = {38},
	number    = {3},
	pages     = {690--728},
	year      = {1991},
note = {\prelim \href{https://doi.org/10.1109/SFCS.1986.47}{FOCS'86}},
	doi	  = {10.1145/116825.116852},
}


@article{GVW,
	author    = {Goldreich, Oded and Vadhan, Salil P. and Wigderson, Avi},
	title     = {On interactive proofs with a laconic prover},
	journal   = ccomplex,
	volume    = {11},
	number    = {1--2},
	pages     = {1--53},
	year      = {2002},
	doi	  = {10.1007/s00037-002-0169-0},
}


@article{GMR,
author    = {Goldwasser, Shafi and Micali, Silvio and Rackoff, Charles},
title     = {The knowledge complexity of interactive proof systems},
	journal   = sicomp,
	volume    = {18},
	number    = {1},
	pages     = {186--208},
	year      = {1989},
note  = {\prelim \href{https://doi.org/10.1145/22145.22178}{STOC'85}},
	doi	  = {10.1137/0218012},
}

@incollection{GS,
  title = {Private coins versus public coins in interactive proof systems},
  author= {Goldwasser, Shafi and Sipser, Michael},
  booktitle     = {Randomness and Computation},
  series        = AdvComputRes,
  volume        = {5},
  publisher     = {JAI Press},
  editor        = {Silvio Micali},
  year          = {1989},
  pages         = {73--90},
  note  = {\prelim \href{https://doi.org/10.1145/12130.12137}{STOC'86}},
}

@article{GS-orig,
	author    = {Goldwasser, Shafi and Sipser, Michael},
title  = {Private Coins versus Public Coins in Interactive Proof Systems},
	journal   = AdvComputRes,
	volume    = {5},
	pages     = {73--90},
	year      = {1989},
	note 	  = {Extended abstract in {\em 18th STOC}, 1986},
	doi       = {10.1145/12130.12137},
}


@article{KM,
	author    = {Klivans, Adam R. and Melkebeek, Dieter van},
	title     = {Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses},
	journal   = sicomp,
	volume    = {31},
	number    = {5},
	pages     = {1501--1526},
	year      = {2002},
	doi	  = {10.1137/S0097539700389652},
}

@article{LFKN,
author = {Lund, Carsten and Fortnow, Lance and Karloff, Howard J. and Nisan, Noam},
	title     = {Algebraic methods for interactive proof systems},
	journal   = jacm,
	volume    = {39},
	number    = {4},
	pages     = {859--868},
	year      = {1992},
	doi	  = {10.1145/146585.146605},
 note = {\prelim \href{http://doi.org/10.1109/FSCS.1990.89518}{FOCS'90}},
}

@InProceedings{conf-version,
	author =	{Leshkowitz, Maya},
title =	{Round Complexity Versus Randomness Complexity in Interactive Proofs},
	crossref =	{prandom18},
	pages =		{49:1--16},
	doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.49},
}


@article{SU,
	author    = {Shaltiel, Ronen and Umans, Christopher},
title = {Low-End Uniform Hardness versus Randomness Tradeoffs for {AM}},
	journal   = sicomp,
	volume    = {39},
	number    = {3},
	pages     = {1006--1037},
	year      = {2009},
	doi	  = {10.1137/070698348}
}


@article{S90,
	author    = {Shamir, Adi},
	title     = {{IP} = {PSPACE}},
	journal   = jacm,
	volume    = {39},
	number    = {4},
	pages     = {869--877},
	year      = {1992},
note = {\prelim \href{https://doi.org/10.1109/FSCS.1990.89519}{FOCS'90}},
	doi       = {10.1145/146585.146609},
}
