Fetching the paper…
Reading the bibliography…
We show an Omega(sqrt{n}/T) lower bound for the space required by any unidirectional constant-error randomized T-pass streaming algorithm that recognizes whether an expression over two types of parenthesis is well-parenthesized.
Computer programming and formal languages
Noam Chomsky and M. P. Schotzenberger · 1963
Earlier work this paper cites.
Word problems solvable in logspace
Richard J. Lipton and Yechezkel Zalcstein · 1977
Earlier work this paper cites.
Some complexity questions related to distributive computing
Andrew Chi-Chih Yao · 1979
Earlier work this paper cites.
Asymptotics in Statistics: Some Basic Concepts
Lucien Marie Le Cam and Grace Lo Yang · 1990
Earlier work this paper cites.
Elements of Information Theory
Thomas M. Cover and Joy A. Thomas · 1991
Earlier work this paper cites.
Private vs. common random bits in communication complexity
Ilan Newman · 1991
Earlier work this paper cites.
Quantum circuit complexity
Andrew Chi-Chih Yao · 1993
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh V. Vazirani · 1997
Earlier work this paper cites.
Communication Complexity
Eyal Kushilevitz and Noam Nisan · 1997
Earlier work this paper cites.
On data structures and asymmetric communication complexity
Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and Avi Wigderson · 1998
Earlier work this paper cites.
Dense quantum coding and a lower bound for 1-way quantum automata
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani · 1999
Earlier work this paper cites.
On randomized one-round communication complexity
Ilan Kremer, Noam Nisan, and Dana Ron · 1999
Earlier work this paper cites.
Optimal lower bounds for quantum automata and random access codes
Ashwin Nayak · 1999
Earlier work this paper cites.
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang · 2000
Earlier work this paper cites.
Informational complexity and the direct sum problem for simultaneous message complexity
Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew C.-C. Yao · 2001
Earlier work this paper cites.
Dense quantum coding and quantum finite automata
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, and Umesh Vazirani · 2002
Earlier work this paper cites.
An information statistics approach to data stream and communication complexity
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2002
Earlier work this paper cites.
Space lower bounds for distance approximation in the data stream model
Michael Saks and Xiaodong Sun · 2002
Cited alongside, same era.
A lower bound for the bounded round quantum communication complexity of Set Disjointness
Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen · 2003
Cited alongside, same era.
Two applications of information complexity
T. S. Jayram, Ravi Kumar, and D. Sivakumar · 2003
Cited alongside, same era.
Exponential lower bound for 2-query locally decodable codes
Iordanis Kerenidis and Ronald de Wolf · 2003
Cited alongside, same era.
The sketching complexity of pattern matching
Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar · 2004
Cited alongside, same era.
Quantum and approximate privacy
Hartmut Klauck · 2004
Cited alongside, same era.
Information cost tradeoffs for Augmented Index and streaming language recognition
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor · 2010
Closest in time.
Lower bounds for sparse recovery
Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff · 2010
Closest in time.
The space complexity of recognizing well-parenthesized expressions
Rahul Jain and Ashwin Nayak · 2010
Closest in time.
On the exact space complexity of sketching and streaming small norms
Daniel M. Kane, Jelani Nelson, and David P. Woodruff · 2010
Closest in time.
Recognizing well-parenthesized expressions in the streaming model
Frédéric Magniez, Claire Mathieu, and Ashwin Nayak · 2010
Closest in time.
The uncertainty principle determines the nonlocality of quantum mechanics
Jonathan Oppenheim and Stephanie Wehner · 2010
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Data Streams: Algorithms and Applications
S. Muthukrishnan · 2005
Cited alongside, same era.
Exponential separation of quantum and classical online space complexity
François Le Gall · 2006
Cited alongside, same era.
The learnability of quantum states
Scott Aaronson · 2007
Cited alongside, same era.
One-way communication complexity and the Nečiporuk lower bound on formula size
Hartmut Klauck · 2007
Cited alongside, same era.
Interaction in quantum communication
Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, and David Zuckerman · 2007
Cited alongside, same era.
Exponential separation for one-way quantum communication complexity, with applications to cryptography
Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf · 2008
Cited alongside, same era.
Everywhere-tight information cost tradeoffs for Augmented Index
Amit Chakrabarti and Ranganath Kondapally · 2011
Closest in time.
Does ignorance of the whole imply ignorance of the parts? Large violations of noncontextuality in quantum theory
Thomas Vidick and Stephanie Wehner · 2011
Closest in time.
New limits to classical and quantum instance compression
Andrew Drucker · 2012
Closest in time.
How to compress interactive communication
Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao · 2013
Closest in time.
Towards a reverse Newman’s theorem in interactive information complexity
Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, and Nikolay Vereshchagin · 2013
Closest in time.
Information cost tradeoffs for augmented index and streaming language recognition
Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor · 2013
Closest in time.
From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking
Omar Fawzi, Patrick Hayden, and Pranab Sen · 2013
Closest in time.
Streaming complexity of checking priority queues
Nathanaël François and Frédéric Magniez · 2013
Closest in time.
Quantum fingerprints that keep secrets
Dmitry Gavinsky and Tsuyoshi Ito · 2013
Closest in time.
Streaming universal distortion-free entanglement concentration
Robin Blume-Kohout, Sarah Croke, and Daniel Gottesman · 2014
Closest in time.