{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,29]],"date-time":"2024-10-29T17:10:38Z","timestamp":1730221838558,"version":"3.28.0"},"reference-count":27,"publisher":"IEEE","license":[{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1109\/focs54457.2022.00065","type":"proceedings-article","created":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T18:48:42Z","timestamp":1672253322000},"page":"624-635","source":"Crossref","is-referenced-by-count":1,"title":["Randomised Composition and Small-Bias Minimax"],"prefix":"10.1109","author":[{"given":"Shalev","family":"Ben-David","sequence":"first","affiliation":[{"name":"University of Waterloo"}]},{"given":"Eric","family":"Blais","sequence":"additional","affiliation":[{"name":"University of Waterloo"}]},{"given":"Mika","family":"Goos","sequence":"additional","affiliation":[{"name":"EPFL"}]},{"given":"Gilbert","family":"Maystre","sequence":"additional","affiliation":[{"name":"EPFL"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"key":"ref2","first-page":"10:1","article-title":"A composition theorem for randomized query complexity","volume":"93","author":"Anshu","year":"2018","journal-title":"Proceedings of the 37th Foundations of Software Technology and Theoretical Computer Science (FSTTCS)"},{"key":"ref3","first-page":"4:1","article-title":"Nearly optimal separations between communication (or query) complexity and partitions","volume-title":"Proceedings of the 31st Computational Complexity Conference (CCC)","author":"Ambainis"},{"key":"ref4","first-page":"29:1","article-title":"Optimal separation and strong direct sum for randomized query complexity","volume-title":"Proceedings of the 34th Computational Complexity Conference (CCC)","author":"Blais"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/focs46700.2020.00045"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/focs46700.2020.00031"},{"key":"ref7","doi-asserted-by":"crossref","DOI":"10.1109\/FOCS54457.2022.00065","volume-title":"Randomised composition and small-bias minimax","author":"Ben-David","year":"2022"},{"key":"ref8","first-page":"9:1","article-title":"The power of many samples in query complexity","volume":"168","author":"Bassilakis","year":"2020","journal-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP)"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/s0304-3975(01)00144-x"},{"key":"ref10","first-page":"28:1","article-title":"When is amplification necessary for composition in randomized query complexity?","volume-title":"Proceedings of the 24h International Conference on Randomization and Computation (RANDOM)","volume":"176","author":"Ben-David"},{"key":"ref11","first-page":"60:1","article-title":"Randomized query complexity of sabotaged and composed functions","volume":"55","author":"Ben-David","year":"2016","journal-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP)"},{"volume-title":"A strong XOR lemma for randomized query complexity","year":"2020","author":"Brody","key":"ref12"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114177"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/3170711"},{"key":"ref15","first-page":"64:1","article-title":"A composition theorem for randomized query complexity via max-conflict complexity","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP)","volume":"132","author":"Gavinsky"},{"key":"ref16","first-page":"18:1","article-title":"A majority lemma for randomised query complexity","volume-title":"Proceedings of the 36th Computational Complexity Conference (CCC)","volume":"200","author":"G\u00f6\u00f6s"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3189-x"},{"key":"ref18","first-page":"39:1","article-title":"Fourier Growth of Parity Decision Trees","volume-title":"Proceedings of the 36th Computational Complexity Conference (CCC)","volume":"200","author":"Girish"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.020"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.12.038"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/focs.2011.75"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.44"},{"key":"ref23","article-title":"On determinism versus unambiquous nondeterminism for decision trees","volume-title":"Technical Report TR02-009, Electronic Colloquium on Computational Complexity (ECCC)","author":"Savick\u00fd","year":"2002"},{"issue":"8","key":"ref24","doi-asserted-by":"crossref","first-page":"197","DOI":"10.4086\/toc.2012.v008a008","article-title":"The communication complexity of gap hamming distance","volume":"8","author":"Sherstov","year":"2012","journal-title":"Theory of Computing"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422485"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/s0304-3975(98)00071-1"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/sfcs.1977.24"}],"event":{"name":"2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)","start":{"date-parts":[[2022,10,31]]},"location":"Denver, CO, USA","end":{"date-parts":[[2022,11,3]]}},"container-title":["2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/9996589\/9996592\/09996704.pdf?arnumber=9996704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T11:48:48Z","timestamp":1709380128000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9996704\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":27,"URL":"https:\/\/doi.org\/10.1109\/focs54457.2022.00065","relation":{},"subject":[],"published":{"date-parts":[[2022,10]]}}}