{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T06:55:47Z","timestamp":1777100147062,"version":"3.51.4"},"reference-count":49,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"10","license":[{"start":{"date-parts":[[2014,10,1]],"date-time":"2014-10-01T00:00:00Z","timestamp":1412121600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"}],"funder":[{"name":"Singapore Ministry of Education Tier 3 Grant"},{"name":"Core Grants of the Centre for Quantum Technologies, Singapore"},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007631","name":"Canadian Institute for Advanced Research, Toronto, ON, Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007631","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Early Researcher Award, Province of Ontario, Canada"},{"name":"QuantumWorks"},{"name":"MITACS, Calgary, AB, Canada"},{"name":"Army Research Office, Adelphi, MD, USA"},{"name":"Government of Canada through Industry Canada"},{"name":"Ministry of Research and Innovation of Ontario Province"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2014,10]]},"DOI":"10.1109\/tit.2014.2339859","type":"journal-article","created":{"date-parts":[[2014,7,17]],"date-time":"2014-07-17T14:32:03Z","timestamp":1405607523000},"page":"6646-6668","source":"Crossref","is-referenced-by-count":9,"title":["The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited"],"prefix":"10.1109","volume":"60","author":[{"given":"Rahul","family":"Jain","sequence":"first","affiliation":[]},{"given":"Ashwin","family":"Nayak","sequence":"additional","affiliation":[]}],"member":"263","reference":[{"key":"ref39","first-page":"209","article-title":"Some complexity questions related to distributive computing","author":"yao","year":"1979","journal-title":"Proc Ann ACM Symp Theory of Computing (STOC)"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.896888"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1038\/nature08400"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_24"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1002\/0471200611"},{"key":"ref36","author":"le cam","year":"1990","journal-title":"Asymptotics in Statistics Some Basic Concepts"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.107.030402"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1126\/science.1192065"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970140004X"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581773"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"ref2","first-page":"118","article-title":"Computer programming and formal languages","author":"chomsky","year":"1963","journal-title":"The Algebraic Theory of Context-Free Languages"},{"key":"ref1","doi-asserted-by":"crossref","DOI":"10.1561\/9781933019604","volume":"1","author":"muthukrishnan","year":"2005","journal-title":"Data Streams Algorithms and Applications (Foundations and Trends in Theoretical Computer Science)"},{"key":"ref20","first-page":"67","article-title":"Exponential separation of quantum and classical online space complexity","author":"le gall","year":"2006","journal-title":"Proc 18th Annu ACM Symp Parallelism Algorithms Archit (SPAA)"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2292135"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1137\/070706550"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/2518131"},{"key":"ref23","first-page":"583","article-title":"Quantum fingerprints that keep secrets","volume":"13","author":"gavinsky","year":"2013","journal-title":"Quantum Inf Comput"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"ref25","author":"kushilevitz","year":"1997","journal-title":"Communication Complexity"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509963"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780640"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238196"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568323"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1113-7"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/100816481"},{"key":"ref17","article-title":"The space complexity of recognizing well-parenthesized expressions","author":"jain","year":"2010","journal-title":"Electronic Colloq on Computational Complexity"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.44"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22935-0_38"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806727"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/322017.322031"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814608"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301347"},{"key":"ref8","first-page":"1190","article-title":"Lower bounds for sparse recovery","author":"do ba","year":"2010","journal-title":"Proc Annu ACM-SIAM Symp Discrete Algorithms (SODA)"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.93"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9097-3"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959901"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.016"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"ref48","first-page":"454","article-title":"Streaming complexity of checking priority queues","author":"fran\u00e7ois","year":"2013","journal-title":"Proc 30th Int Symp Theoretical Aspects Comput Sci"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.71"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/100811969"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2013.12"},{"key":"ref44","first-page":"352","article-title":"Quantum circuit complexity","author":"yao","year":"1993","journal-title":"Proc 34th IEEE Symp Foundations of Computer Science"},{"key":"ref43","author":"nielsen","year":"2000","journal-title":"Quantum Computation and Quantum Information"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/6895347\/06858012.pdf?arnumber=6858012","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,12]],"date-time":"2022-01-12T11:51:19Z","timestamp":1641988279000},"score":1,"resource":{"primary":{"URL":"http:\/\/ieeexplore.ieee.org\/document\/6858012\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":49,"journal-issue":{"issue":"10"},"URL":"https:\/\/doi.org\/10.1109\/tit.2014.2339859","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}