Brendan Juba - Papers
Back to the main page.

Publications

O. Goldreich, B. Juba, and M. Sudan. A Theory of Goal-Oriented Communication. Journal of the ACM. 59(2), Article 8. 2012.
Previously appeared in Electronic Colloquium on Computational Complexity (ECCC) TR09-075. 2009. (PS|PDF)
Brief Announcement version in Proc. 30th PODC, 2011. (PS| PDF)

B. Juba. On Learning Finite-State Quantum Sources. Quantum Information & Computation. 12(1-2):105-118. 2012.
Preliminary version: arXiv:0910.3713v1 [quant-ph] (PS|PDF)

B. Juba, S. Vempala. Semantic Communication for Simple Goals is Equivalent to On-line Learning. In 22nd International Conference on Algorithmic Learning Theory. Espoo, Finland. LNAI 6925, Springer, 2011. (PDF|PS) Official version posted at www.springerlink.com

B. Juba, A. Kalai, S. Khanna, and M. Sudan. Compression Without a Common Prior: An Information-theoretic Justification for Ambiguity in Language. In 2nd Symposium on Innovations in Computer Science. Beijing, P.R. China. 2011. (PDF)

B. Juba and M. Sudan. Efficient Semantic Communication via Compatible Beliefs. In 2nd Symposium on Innovations in Computer Science. Beijing, P.R. China. 2011. (PS|PDF)

B. Juba and M. Sudan. Universal Semantic Communication I. In 40th ACM Symposium on Theory of Computing. Victoria (BC) Canada. 2008. (PS|PDF)
Previously appeared in Electronic Colloquium on Computational Complexity (ECCC) TR07-084. 2007. (PS|PDF)

B. Juba. Estimating relatedness via data compression. In 23rd International Conference on Machine Learning. Pittsburgh, PA. 2006. (PS|PDF)

Technical Reports, Theses, Course Projects, etc.

B. Juba. Universal Semantic Communication. Ph.D. thesis, Massachusetts Institute of Technology, 2010.
Springer, Berlin, 2011. Online version at http://dx.doi.org/10.1007/978-3-642-23297-8. (More information available at the official Springer website.)
The original, submitted version is also available on DSpace: http://hdl.handle.net/1721.1/62423

B. Juba. Brief Announcement: Reliable End-user Communication Under a Changing Packet Network Protocol. In Proc. 30th PODC, 2011. (PS|PDF)

B. Juba and M. Sudan. Universal Semantic Communication II: A Theory of Goal-Oriented Communication. Electronic Colloquium on Computational Complexity (ECCC) TR08-095. 2008. (PS|PDF) [This work is largely subsumed by the work with Oded Goldreich above; Chs. 3 and 5 of my thesis are an improved version of the rest --BJ]

B. Juba. On the role of computational complexity theory in the study of brain function. Thought (Carnegie Mellon University Undergraduate Research Journal) . 1:32-45. 2006. (PS|PDF)

B. Juba. On the Hardness of Simple Stochastic Games. Master's Thesis, Carnegie Mellon University, 2005. (PS|PDF)
A journal-style report focusing on the new contributions (joint with M. Blum and R. Williams) on the same topic is also available: (PS| PDF)

For a course project in 18.177 (Stochastic Processes), I wrote up a slightly simplified version of Mossel's Gaussian bounds for noise correlations and tight analysis of long codes, specialized to the parts necessary to obtain "Majority is most predictable:" (PDF)

Back to the main page.

MD 140 first initial last name at alum dot mit