%% Theory of Computing
%% File: v016a013.bib
%% Publication date: November 9, 2020
%% Authors: Ankit Garg, Mika Goos, Pritish Kamath, and Dmitry Sokolov

@preamble{"\newcommand{\prelim}{Preliminary version in\ }"}
%
@string{acm      = "ACM Press"}
@string{ieee     = "IEEE Comp. Soc."}
@string{siam     = "SIAM"}
@string{drops    = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik"}
@string{ams      = "Amer. Math. Soc."}
@string{cup      = "Cambridge Univ. Press"}
@string{oup      = "Oxford Univ. Press"}
@string{springer = "Springer"}
@string{elsevier = "Elsevier"}
@string{dover    = "Dover Publ."}
%%
@string{eccc="Electron. Colloq. Comput. Complexity"}
%
@string{jacm="J. ACM"}
%
@string{sicomp="SIAM J. Comput."}
%
@string{jcss="J. Comput. System Sci."}
%
@string{tcs   = "Theoret. Comput. Sci."}
%
@string{toc  = "Theory of Computing"}
%
@string{ccomplex = "Comput. Complexity"}
%
@string{cca    = "Combinatorica"}
%
@string{sidma = "SIAM J. Discr. Math."}
%
@string{monthly = "Amer. Math. Monthly"}
%
@string{jsl = "J. Symbolic Logic"}
%
@string{AnnPureApplLogic =" Ann. Pure Appl. Logic"}
%
@string{discrappmath="Discr. Appl. Math."}
%
@string{doklady  = "Dokl. Akad. Nauk SSSR (Russian)"}
%
@string{doklmath  = "Dokl. Math."}
%
@string{izvestiya = "Izvestiya Russ. Akad. Nauk Ser. Math. (Russian)"}
%
@string{izvmath = "Izvestiya Math."}
%
@Article{alon87monlower,
  author =  {Noga Alon and Ravi B. Boppana},
  title =   {The monotone circuit complexity of Boolean functions},
  journal = cca,
  year =    {1987},
  volume =  {7},
  number =  {1},
  pages =   {1--22},
  doi =     {10.1007/BF02579196}
}

@Article{amano04approxbottle,
  author =  {Kazuyuki Amano and Akira Maruoka},
  title =   {The Potential of the Approximation Method},
  journal = sicomp,
  year =    {2004},
  volume =  {33},
  number =  {2},
  pages =   {433--447},
  doi =     {10.1137/S009753970138445X}
}

@ARTICLE{andreev1985monlower,
    author = {Alexander E. Andreev},
    title = {On a method for obtaining lower bounds for the complexity of individual monotone functions},
    journal = doklmath,
    year = {1985},
    volume = {282},
    number = {5},
    pages = {1033--1037},
    note = {Link at \href{http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=9107&option_lang=eng}{Math-Net.ru}},
}

@ARTICLE{andreev1985monlower-russian,
    author = {Alexander E. Andreev},
    title = {On a method for obtaining lower bounds for the complexity of individual monotone functions},
    journal = doklady,
    year = {1985 (in Russian)},
    volume = {281},
    number = {2},
    issn = {0869-5652},
    pages = {1033--1037},
}

@Article{atserias08combinatorial,
  author =  {Albert Atserias and V{\'\i}ctor Dalmau},
  title =   {A combinatorial characterization of resolution width},
  journal = jcss,
  year =    {2008},
  volume =  {74},
  number =  {3},
  pages =   {323--334},
  doi =     {10.1016/j.jcss.2007.06.025}
}

@InProceedings{beame10hardness,
  author =    {Beame, Paul and Huynh, Trinh and Pitassi, Toniann},
  title =     {Hardness Amplification in Proof Complexity},
  crossref  = {pstoc10},
  pages =     {87--96},
  doi =       {10.1145/1806689.1806703}
}

@InCollection{beame01propositional,
  author =    {Beame, Paul and Pitassi, Toniann},
  title =     {Propositional Proof Complexity: Past, Present, and Future},
  booktitle = {Current Trends in Theoretical Computer Science: Entering the 21st Century},
  publisher = {World Scientific},
  year =      {2001},
  pages =     {42--70},
  doi =       {10.1142/9789812810403\_0001},
  eprint  =   {eccc:TR98-067},
}

@Article{beame07lower,
  author =    {Paul Beame and Toniann Pitassi and Nathan Segerlind},
  title =     {Lower Bounds for {L}ov{\'a}sz--{S}chrijver Systems and Beyond Follow from Multiparty Communication Complexity},
  journal =   sicomp,
  year =      {2007},
  volume =    {37},
  number =    {3},
  pages =     {845--869},
  doi =       {10.1137/060654645},
}

@Article{ben-sasson01short,
  author =     {Ben{-}Sasson, Eli and Wigderson, Avi},
  title =      {Short Proofs Are Narrow---Resolution Made Simple},
  journal =    jacm,
  year =       {2001},
  volume =     {48},
  number =     {2},
  pages =      {149--169},
  doi =        {10.1145/375827.375835},
}

@Article{berg99approxbottle,
  author =  {Christer Berg and Staffan Ulfberg},
  title =   {Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers},
  journal = ccomplex,
  year =    {1999},
  volume =  {8},
  number =  {1},
  pages =   {1--20},
  doi =     {10.1007/s000370050017}
}

@Article{bonet97lower,
  author =  {Maria Luisa Bonet and Toniann Pitassi and Ran Raz},
  title =   {Lower Bounds for Cutting Planes Proofs with Small Coefficients},
  journal = jsl,
  year =    {1997},
  volume =  {62},
  number =  {3},
  pages =   {708--728},
  doi =     {10.2307/2275569}
}

@article{chattopadhyay17simulation,
  author =      {Arkadev Chattopadhyay and Michal Kouck{\'{y}} and Bruno Loff and Sagnik Mukhopadhyay},
  title =       {Simulation Theorems via Pseudo-random Properties},
  journal =     ccomplex,
  year =        {2019},
  volume  =     {28},
  pages   =     {617--659},
   doi    =     {10.1007/s00037-019-00190-7},
  eprint =      {1704.06807}
}

@TechReport{chattopadhyay17simulation-arxiv,
  author =      {Arkadev Chattopadhyay and Michal Kouck{\'{y}} and Bruno Loff and Sagnik Mukhopadhyay},
  title =       {Simulation Theorems via Pseudorandom Properties},
  year =        {2017},
  eprint =      {1704.06807}
}

@Article{cook87complexity,
  author =  {William Cook and Collette Coullard and Gy{\"o}rgy Tur{\'a}n},
  title =   {On the complexity of cutting-plane proofs},
  journal = discrappmath,
  year =    {1987},
  volume =  {18},
  number =  {1},
  pages =   {25--38},
  doi =     {10.1016/0166-218X(87)90039-4}
}

@InProceedings{fleming17randomcnf,
  author =    {Noah Fleming and Denis Pankratov and Toniann Pitassi and Robert Robere},
  title =     {Random {$\Theta(\log n)$}-{CNF}s are Hard for Cutting Planes},
  crossref =  {pfocs17},
  year =      {2017},
  pages =     {109--120},
  doi   =     {10.1109/FOCS.2017.19},
note = {Update: \href{https://eccc.weizmann.ac.il/report/2017/045/}{ECCC TR17-045}.},
}

@Article{gal01characterization,
  author =  {Anna G{\'a}l},
  title =   {A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs},
  journal = ccomplex,
  year =    {2001},
  volume =  {10},
  number =  {4},
  pages =   {277--296},
  doi =     {10.1007/s000370100001}
}

@article{goos17pnp,
  author =    {Mika G{\"o}{\"o}s and Pritish Kamath and Toniann Pitassi and Thomas Watson},
  title =    {Query-to-Communication Lifting for {$\textrm{P}^{\textrm{NP}}$}},
  journal   = ccomplex,
  volume    = {28},
  number    = {1},
  pages     = {113--144},
  year      = {2019},
  doi       = {10.1007/s00037-018-0175-5},
  note  = {\prelim \href{https://doi.org/10.4230/LIPIcs.CCC.2017.12}{CCC'17}},
}                  

@InProceedings{goos17pnp-conf,
  author =    {Mika G{\"o}{\"o}s and Pritish Kamath and Toniann Pitassi and Thomas Watson},
  title =    {Query-to-Communication Lifting for {$\textrm{P}^{\textrm{NP}}$}},
  crossref  = {pccc17},
  year =      {2017},
  pages =     {12:1--12:16},
  doi =       {10.4230/LIPIcs.CCC.2017.12}
}

@InProceedings{goos19monotone,
  author =    {Mika G{\"o}{\"o}s and Pritish Kamath and Robert Robere and Dmitry Sokolov},
  title =     {Adventures in Monotone Complexity and {TFNP}},
  crossref  = {pitcs19},
  year =      {2019},
  pages =     {38:1--38:19},
  doi =       {10.4230/LIPIcs.ITCS.2019.38}
}

@Article{goos16rectangles,
  author  = {Mika G{\"o}{\"o}s and Shachar Lovett and Raghu Meka and Thomas Watson and David Zuckerman},
  title   = {Rectangles Are Nonnegative Juntas},
  journal = sicomp,
  year    = {2016},
  volume  = {45},
  number  = {5},
  pages   = {1835--1869},
  doi     = {10.1137/15M103145X},
}

@article{goos14cbs,
  author =    {Mika G{\"o}{\"o}s and Toniann Pitassi},
  title =     {Communication Lower Bounds via Critical Block Sensitivity},
  journal  =  sicomp,
  year     =  {2018},
  volume   =  {47},
  number   =  {5},
  pages    =  {1778--1806},
  doi   =     {10.1137/16M1082007},
  note  = {\prelim \href{https://doi.org/10.1145/2591796.2591838}{STOC'14}},
}

@InProceedings{goos14cbs-conf,
  author =    {Mika G{\"o}{\"o}s and Toniann Pitassi},
  title =     {Communication Lower Bounds via Critical Block Sensitivity},
  crossref  = {pstoc14},
  pages =     {847--856},
  doi =       {10.1145/2591796.2591838}
}

@article{goos15deterministic,
  author =    {Mika G{\"o}{\"o}s and Toniann Pitassi and Thomas Watson},
  title =     {Deterministic Communication vs. Partition Number},
  journal   = sicomp,                
  year =      {2018},
  volume    = {47},
  number    = {6},
  pages =     {2435--2450},
  doi       = {10.1137/16M1059369},
  note = {\prelim \href{https://doi.org/10.1109/FOCS.2015.70}{FOCS'15}},
}

@InProceedings{goos15deterministic-conf,
  author =    {Mika G{\"o}{\"o}s and Toniann Pitassi and Thomas Watson},
  title =     {Deterministic Communication vs. Partition Number},
  crossref  = {pfocs15},
  year =      {2015},
  pages =     {1077--1088},
  doi =       {10.1109/FOCS.2015.70}
}

@article{goos17bpp,
  author =    {Mika G{\"o}{\"o}s and Toniann Pitassi and Thomas Watson},
  title =     {Query-to-Communication Lifting for {BPP}},
  journal   = sicomp,
  year      = {2020},
  volume    = {49},
  number    = {4},
  pages     = {132--143},
  doi       = {10.1137/17M115339X},
  note  = {\prelim \href{https://doi.org/10.1109/FOCS.2017.21}{FOCS'17}},
}

@InProceedings{goos17bpp-conf,
  author =    {Mika G{\"o}{\"o}s and Toniann Pitassi and Thomas Watson},
  title =     {Query-to-Communication Lifting for {BPP}},
  crossref  = {pfocs17},
  pages =     {132--143},
  doi =       {10.1109/FOCS.2017.21}
}

@InProceedings{garg18monotone,
  author =    {Garg, Ankit and G\"{o}\"{o}s, Mika and Kamath, Pritish and Sokolov, Dmitry},
  title =     {Monotone Circuit Lower Bounds from Resolution},
  crossref   = {pstoc18},
  pages =     {902--911},
  doi =       {10.1145/3188745.3188838}
}


@InProceedings{haken95bottleneck,
  author =    {Armin Haken},
  title =     {Counting Bottlenecks to Show Monotone {P} {$\neq$} {NP}},
  crossref  = {pfocs95},
  pages =     {36--40},
  doi =       {10.1109/SFCS.1995.492460}
}

@Article{haken99exponential,
  author =  {Armin Haken and Stephen A. Cook},
  title =  {An Exponential Lower Bound for the Size of Monotone Real Circuits},
  journal = jcss,
  year =    {1999},
  volume =  {58},
  number =  {2},
  pages =   {326--335},
  doi =     {10.1006/jcss.1998.1617}
}

@InProceedings{harnik00higher,
  author =    {Harnik, Danny and Raz, Ran},
  title =     {Higher Lower Bounds on Monotone Size},
  crossref  = {pstoc00},
  pages =     {378--387},
  doi =       {10.1145/335305.335349}
}

@article{hrubes17note,
  author =      {Pavel Hrube{\v{s}} and Pavel Pudl{\'a}k},
  title =       {A note on monotone real circuits},
  journal  =    ipl,
  year =        {2018},
  volume  =     {131},
  pages   =     {15--19},
  doi     =     {10.1016/j.ipl.2017.11.002},
  eprint  =     {eccc:TR17-048},
}

@article{hrubes17note-eccc,
  author =      {Pavel Hrube{\v{s}} and Pavel Pudl{\'a}k},
  title =       {A note on monotone real circuits},
  journal  =    eccc,
  year =        {2017},
  volume  =     {TR17-048},
  eprint      = {ecccprimary:TR17-048},
}

@InProceedings{hrubes17randomformulas,
  author =    {Pavel Hrube{\v{s}} and Pavel Pudl{\'a}k},
  title =     {Random Formulas, Monotone Circuits, and Interpolation},
  crossref  = {pfocs17},
  pages =     {121--131},
  doi =       {10.1109/FOCS.2017.20}
}

@InProceedings{huynh12virtue,
  author =    {Trinh Huynh and Jakob Nordstr{\"o}m},
  title =     {On the Virtue of Succinct Proofs: Amplifying Communication Complexity Hardness to Time--Space Trade-Offs in Proof Complexity},
  crossref  = {pstoc12},                  
  pages =     {233--248},
  doi =       {10.1145/2213977.2214000},
}

@InProceedings{itsykson14lower,
  author =    {Itsykson, Dmitry and Sokolov, Dmitry},
  title =     {Lower Bounds for Splittings by Linear Combinations},
  crossref =  {pmfcs14},
  pages =     {372--383},
  doi =       {10.1007/978-3-662-44465-8\_32}
}

@InProceedings{jukna97finitelimits,
  author =    {Stasys Jukna},
title= {Finite Limits and Monotone Computations: {T}he Lower Bounds Criterion},
  crossref  = {pccc97},
  pages =     {302--313},
  doi =       {10.1109/CCC.1997.612325},
}

@BOOK{jukna12boolean,
  author = {Stasys Jukna},                  
  title = {Boolean Function Complexity: Advances and Frontiers},
  publisher = springer,
  year = {2012},
  volume = {27},
  series = {Algorithms and Combinatorics},
  doi   =  {10.1007/978-3-642-24508-4},
}

@article{karchmer88monotone,
  author =    {Karchmer, Mauricio and Wigderson, Avi},
title =   {Monotone circuits for connectivity require super-logarithmic depth},
   journal = sidma,
   year = {1990},
   volume = {3},
   number = {2},
   pages = {255--265},
   doi = {10.1137/0403021},  
   note  = {\prelim \href{https://doi.org/10.1145/62212.62265}{STOC'88}},
}

@InProceedings{karchmer88monotone-conf,
  author =    {Karchmer, Mauricio and Wigderson, Avi},
title =   {Monotone circuits for connectivity require super-logarithmic depth},
  crossref = {pstoc88},
  pages =     {539--550},
  doi =       {10.1145/62212.62265},
}

@Article{krajicek97interpolation,
  author =  {Jan Kraj{\'{\i}}{\v{c}}ek},
  title =   {Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic},
  journal = jsl,
  year =    {1997},
  volume =  {62},
  number =  {2},
  pages =   {457--486},
  doi =     {10.2307/2275541}
}

@Article{krajicek98discretely,
  author =    {Jan Kraj{\'{\i}}{\v{c}}ek},
  title =     {Discretely ordered modules as a first-order extension of the cutting planes proof system},
  journal =   jsl,
  year =      {1998},
  volume =    {63},
  number =    {4},
  pages =     {1582--1596},
  doi =       {10.2307/2586668},
  publisher = cup,
}

@BOOK{kushilevitz97communication,
  author = {Eyal Kushilevitz and Noam Nisan},
  title = {Communication Complexity},
  year = {1997},                  
  publisher = cup,
  doi   = {10.1017/CBO9780511574948},
}

@Article{lovasz95search,
  author =    {L{\'a}szl{\'o} Lov{\'a}sz and Moni Naor and Ilan Newman and Avi Wigderson},
  title =     {Search Problems in the Decision Tree Model},
  journal =   sidma,
  year =      {1995},
  volume =    {8},
  number =    {1},
  pages =     {119--132},
  doi =       {10.1137/S0895480192233867},
}

@Article{mulmuley87fast,
  author =  {Mulmuley, Ketan},
  title =   {A fast parallel algorithm to compute the rank of a matrix over an arbitrary field},
  journal = cca,
  year =    {1987},
  volume =  {7},
  number =  {1},
  pages =   {101--104},
  doi =     {10.1007/BF02579205}
}

@Article{pudlak97lower,
  author =  {Pavel Pudl{\'a}k},
  title =   {Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations},
  journal = jsl,
  year =    {1997},
  volume =  {62},
  number =  {3},
  pages =   {981--998},
  doi =     {10.2307/2275583}
}

@Article{pudlak00proofs,
  author =    {Pavel Pudl{\'a}k},
  title =     {Proofs as Games},
  journal =   monthly,
  year =      {2000},
  volume =    {107},
  number =    {6},
  pages =     {541--550},
  doi =       {10.2307/2589349},
}

@InProceedings{pudlak10extracting,
  author =    {Pavel Pudl{\'a}k},
  title =   {On extracting computations from propositional proofs (a survey)},
  crossref = {pfsttcs10},
  year =      {2010},
  pages =     {30--41},
  doi =       {10.4230/LIPIcs.FSTTCS.2010.30}
}

@Book{rao17communication,
  author = {Anup Rao and Amir Yehudayoff},
  title =  {Communication Complexity and Applications},
  year =   {2020},
  publisher =  cup,
  doi  =  {10.1017/9781108671644},
}

@Article{raz99separation,
  author =    {Raz, Ran and McKenzie, Pierre},
  title =     {Separation of the Monotone {NC} Hierarchy},
  journal =   cca,
  year =      {1999},
  volume =    {19},
  number =    {3},
  pages =     {403--435},
  doi =       {10.1007/s004930050062},
}

@Article{raz08resolution,
  author =  {Ran Raz and Iddo Tzameret},
  title =   {Resolution over linear equations and multilinear proofs},
  journal =  AnnPureApplLogic,
  year =    {2008},
  volume =  {155},
  number =  {3},
  pages =   {194--224},
  doi =     {10.1016/j.apal.2008.04.001},
}

@ARTICLE{razborov85monlower,
  author  = {Alexander A. Razborov},
 title = {Lower bounds on the monotone complexity of some {Boolean} functions},
  journal = doklmath,
  year    = {1985},
  volume  = {31},
  pages   = {354-357},
  number  = {4},
  note = {Link at \href{http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=dan&paperid=9192&option_lang=eng}{Math-Net.ru}},
}

@ARTICLE{razborov85monlower-russian,
  author  = {Alexander A. Razborov},
  journal =  doklady,
  pages   = {798--801},
 title = {Lower bounds on the monotone complexity of some {Boolean} functions},
  volume  = {281},
  number  = {4},
  year    = {1985},
}

@InProceedings{razborov89onthemethod,
  author =    {Alexander A. Razborov},
  title =     {On the Method of Approximations},
  crossref  = {pstoc89},
  pages =     {167--176},
  doi =       {10.1145/73007.73023}
}

@Article{razborov95unprovability,
  author =  {Alexander A. Razborov},
  title =   {Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic},
  journal =  izvmath,
  year =    {1995},
  vol =     {59},
  number =  {1},
  pages =   {205--227},
  note  = {Link at \href{http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=9&option_lang=eng}{Math-Net.ru}},
}

@Article{razborov95unprovability-russian,
  author =  {Alexander A. Razborov},
  title =   {Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic},
  journal =  izvestiya,
  year =    {1995 (in Russian)},
  pages =   {201--224},
  issue =   {1},
  vol =     {59},
}

@InCollection{razborov97generalapprox,
  author =    {Alexander A. Razborov},
  title =     {On Small Size Approximation Models},
  booktitle = {The Mathematics of Paul Erd{\"o}s I},
  publisher = springer,
  year =      {1997},
  pages =     {385--392},
  doi =       {10.1007/978-3-642-60408-9\_28}
}

@Article{razborov16new,
  author =    {Razborov, Alexander A.},
  title =     {A New Kind of Tradeoffs in Propositional Proof Complexity},
  journal =    jacm,
  year =      {2016},
  volume =    {63},
  number =    {2},
  pages =     {16:1--16:14},
  doi =       {10.1145/2858790},
}

@Article{razborov16proof,
  author =    {Razborov, Alexander A.},
  title =     {Proof Complexity and Beyond},
  journal =   {SIGACT News},
  year =      {2016},
  volume =    {47},
  number =    {2},
  pages =     {66--86},
  doi =       {10.1145/2951860.2951875},
}

@InProceedings{rezende16limited,
  author =    {de Rezende, Susanna F. and Nordstr{\"o}m, Jakob and Vinyals, Marc},
  title =     {How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)},
  crossref  =  {pfocs16},
  pages =     {295--304},
  doi =       {10.1109/FOCS.2016.40}
}

@Article{rossman14monotone,
  author =  {Benjamin Rossman},
  title =   {The Monotone Complexity of $k$-Clique on Random Graphs},
  journal = sicomp,
  year =    {2014},
  volume =  {43},
  number =  {1},
  pages =   {256--279},
  doi =     {10.1137/110839059}
}

@article{simon97approxbottle,
  author  = {Janos Simon and Shi{-}Chun Tsai},
  title   = {On the Bottleneck Counting Argument},
  journal = tcs,                  
   year   = {2000},
   volume = {237},
   number = {1--2},
   pages  = {429--437},
   doi    = {10.1016/S0304-3975(99)00321-7},
   note   = {\prelim \href{https://doi.org/10.1109/CCC.1997.612324}{CCC'97}},
}

@InProceedings{simon97approxbottle-conf,
  author =    {Janos Simon and Shi{-}Chun Tsai},
  title =     {A Note on the Bottleneck Counting Argument},
  crossref  =  {pccc97},
  pages =     {297--301},
  doi =       {10.1109/CCC.1997.612324}
}

@InProceedings{sokolov17dag,
  author =    {Dmitry Sokolov},
  title =     {Dag-Like Communication and Its Applications},
  crossref =  {pcsr17},
  pages =     {294--307},
  publisher = {Springer},
  doi =       {10.1007/978-3-319-58747-9\_26},
  isbn =      {978-3-319-58747-9}
}

@Article{tardos88gap,
  author =  {Tardos, {\'E}va},
  title =   {The gap between monotone and non-monotone circuit complexity is exponential},
  journal =  cca,
  year =    {1988},
  volume =  {8},
  number =  {1},
  pages =   {141--142},
  doi =     {10.1007/BF02122563}
}

@Article{urquhart87hard,
	author =    {Alasdair Urquhart},
	title =     {Hard examples for resolution},
	journal =    jacm,
	year =      {1987},
	volume =    {34},
	number =    {1},
	pages =     {209--219},
	doi =       {10.1145/7531.8928},
}

@InCollection{wigderson93thefusion,
  author =    {Avi Wigderson},
  title =     {The Fusion Method for Lower Bounds in Circuit Complexity},
  booktitle = {Combinatorics, Paul Erd{\H{o}}s is Eighty},
  publisher = {J{\'a}nos Bolyai Math. Soc., Budapest},
  year =      {1993},
  pages =     {453--468},
  vol =       {1},
}

@article{wu17raz,
  author =      {Xiaodi Wu and Penghui Yao and Henry Yuen},
  title =       {{R}az--{M}c{K}enzie Simulation with the Inner Product Gadget},
  journal  =    eccc,
  year =        {2017},
  volume   =    {TR17-010},
  eprint   =    {ecccprimary:TR17-010},
}
%
@string{focs89="Proc. 30th FOCS"}
@proceedings{pfocs89,
booktitle = focs89,
year = {1989},
publisher = ieee,
}

@string{focs95="Proc. 36th FOCS"}
@proceedings{pfocs95,
booktitle = focs95,
year = {1995},
publisher = ieee,
}

@string{focs10="Proc. 51st FOCS"}
@proceedings{pfocs10,
booktitle = focs10,
year = {2010},
publisher = ieee,
}

@string{focs15="Proc. 56th FOCS"}
@proceedings{pfocs15,
booktitle = focs15,
year = {2015},
publisher = ieee,
}

@string{focs16="Proc. 57th FOCS"}
@proceedings{pfocs16,
booktitle = focs16,
year = {2016},
publisher = ieee,
}

@string{focs17="Proc. 58th FOCS"}
@proceedings{pfocs17,
booktitle = focs17,
year = {2017},
publisher = ieee,
}

@string{itcs = " Innovations in Theoret. Comp. Sci."}
@string{itcs19 = "Proc. 10th " # itcs # " (ITCS'19)"}
@proceedings{pitcs19,
  booktitle	= itcs19,
  year		= {2019},
  publisher	= drops,
}

@string{stoc88="Proc. 20th STOC"}
@proceedings{pstoc88,
booktitle = stoc88,
year = {1988},
publisher = acm,
}

@string{stoc89="Proc. 21st STOC"}
@proceedings{pstoc89,
booktitle = stoc89,
year = {1989},
publisher = acm,
}

@string{stoc00="Proc. 32nd STOC"}
@proceedings{pstoc00,
booktitle = stoc00,
year = {2000},
publisher = acm,
}

@string{stoc10="Proc. 42nd STOC"}
@proceedings{pstoc10,
booktitle = stoc10,
year = {2010},
publisher = acm,
}

@string{stoc12="Proc. 44th STOC"}
@proceedings{pstoc12,
booktitle = stoc12,
year = {2012},
publisher = acm,
}

@string{stoc14="Proc. 46th STOC"}
@proceedings{pstoc14,
booktitle = stoc14,
year = {2014},
publisher = acm,
}

@string{stoc18="Proc. 50th STOC"}
@proceedings{pstoc18,
booktitle = stoc18,
year = {2018},
publisher = acm,
}

@string{cccieee = " IEEE Conf. on Comput. Complexity"}
@string{ccc97 = "Proc. 12th " # cccieee # " (CCC'97)"}
@proceedings{pccc97,
  booktitle	= ccc97,
  year		= {1997},
  publisher	= ieee,
}

@string{cccdrops = " Comput. Complexity Conf."}
@string{ccc17 = "Proc. 32nd " # cccdrops # " (CCC'17)"}
@proceedings{pccc17,
  booktitle	= ccc17,
  year		= {2017},
  publisher	= drops,
}

@string{csr  = " Comp. Sci. Symp. in Russia"}
@string{csr17 = "Proc. 12th " # csr # " (CSR'17)"}
@proceedings{pcsr17,
  booktitle	= csr17,
  year		= {2017},
  publisher	= springer,
}

@string{fsttcs  = " Found. Software Techn. Theoret. Comp. Sci."}
@string{fsttcs10 = "Proc. 30th " # fsttcs # " (FSTTCS'10)"}
@proceedings{pfsttcs10,                  
  booktitle = fsttcs10,
  year =      {2010},
  publisher = drops,
}

@string{mfcs = " Math. Found. Comp. Sci."}
@string{mfcs14 = " Proc. 39th " # mfcs # " (MFCS'14)"}
@proceedings{pmfcs14,
  booktitle = mfcs14,
  year  = {2014},
  publisher = springer,
}
