Brendan Juba - Papers
Back to the main page.

Refereed Publications (jump to unrefereed papers, unpublished manuscripts, etc.)

J. Hainline, B. Juba, H. S. Le, and D. Woodruff. Conditional sparse lp-norm regression with optimal probability. To appear in AISTATS, 2019. (PDF)
Preliminary version: arXiv:1806.10222 [cs.LG]

A. Durgin and B. Juba. Hardness of improper one-sided learning of conjunctions for all uniformly falsifiable CSPs. To appear in ALT, 2019. (PDF)
Previously appeared in Electronic Colloquium on Computational Complexity (ECCC) TR18-118. 2018. (PDF)

M. Braverman and B. Juba. The Price of Uncertain Priors in Source Coding. IEEE Transactions on Information Theory, 65(2):1165-1171, 2019.
Preprint: arXiv:1811.08976 [cs.IT]
Previously appeared as The Price of Uncertainty in Communication. In 53rd Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA. 2015. (PDF)

B. Juba. Polynomial-time probabilistic reasoning with partial observations via implicit learning in probability logics. To appear in AAAI'19. (PDF)
Previously appeared in Eighth International Workshop on Statistical Relational AI (StarAI 2018), arXiv:1806.11204 [cs.AI], 2018. (PDF)

R. Stern and B. Juba. Safe partial diagnosis from normal observations. To appear in AAAI'19. (PDF)
Previously appeared in 29th International Workshop on Principles of Diagnosis (DX'18), 2018. (PDF)

B. Juba and H. S. Le. Precision-recall versus accuracy and the role of large data sets. To appear in AAAI'19. (PDF)
Previously appeared in Extreme Classification 2017: NIPS Workshop on Multi-class and Multi-label Learning in Extremely Large Label Spaces in NIPS 2017, Long Beach, CA. (PDF)

M. Cheraghchi, E. Grigorescu, B. Juba, K. Wimmer, and N. Xie. AC0(MOD2) Lower Bounds for the Boolean Inner Product. Journal of Computer and System Sciences, 97:45-59, 2018.
Previously appeared in 43rd International Colloquium on Automata, Languages, and Programming, Rome, Italy, 2016. (PDF)
and Electronic Colloquium on Computational Complexity (ECCC) TR15-030, 2015. (PDF)

D. Qi, J. Arfin, M. Zhang, T. Mathew, R. Pless, and B. Juba. Anomaly Explanation Using Meta-data. In 2018 IEEE Winter Conference on Applications of Computer Vision (WACV'18), Lake Tahoe, NV, USA, 2018. (PDF)

B. Juba, Z. Li, and E. Miller. Learning Abduction under Partial Observability. In 32nd AAAI Conference on Artificial Intelligence, New Orleans, LA, USA, 2018. (PDF)
Note: the proceedings version contained an error that is corrected in the above version of the paper
Previously appeared in 6th Workshop on Automated Knowledge Base Construction (AKBC 2017) at NIPS 2017; available as arXiv:1711.04438 [cs.AI]. (PDF)

R. Stern and B. Juba. Efficient, Safe, and Probably Approximately Complete Learning of Action Models. In 26th International Joint Conference on Artificial Inteligence (IJCAI'17), Melbourne, VIC, Australia, 2017. (PDF)
Previously appeared as "Model-free conformant planning" in ICAPS 2017 Workshop on Generalized Planning (GenPlan'17)

M. Chakraborty, K. P. Chua, S. Das, and B. Juba. Coordinated Versus Decentralized Exploration In Multi-Agent Multi-Armed Bandits. In 26th International Joint Conference on Artificial Inteligence (IJCAI'17), Melbourne, VIC, Australia, 2017.
Previously appeared in Workshop on Learning, Inference, and Control of Multi-Agent Systems (MALIC) in NIPS 2016. (PDF)

M. Zhang, T. Mathew, and B. Juba. An improved algorithm for learning to perform exception-tolerant abduction. In 31st AAAI Conference on Artificial Intelligence (AAAI'17), pages 1257-1265, San Francisco, CA, USA, 2017. (PDF)

B. Juba. Conditional Sparse Linear Regression. In 8th Innovations in Theoretical Computer Science, LIPIcs volume 67, Article 45:1-14, Berkeley, CA, USA, 2017. (PDF)
Preliminary version: arXiv:1608.05152 [cs.LG] (PDF)

B. Juba. Integrated Common Sense Learning and Planning in POMDPs. Journal of Machine Learning Research. 17(96):1-37, 2016. (PDF)

B. Juba. Learning abductive reasoning using random examples. In 30th AAAI Conference on Artificial Intelligence (AAAI'16), Phoenix, AZ, USA, 2016. (PDF)
Previously appeared in IJCAI 2015 Workshop on Cognitive Knowledge Acquisition and Applications (Cognitum'15), 2015. (PDF)
Partially subsumes: Conditional Distribution Search. Manuscript, 2014. (PDF)

B. Juba, C. Musco, F. Long, S. Sidiroglou-Douskos, and M. Rinard. Principled Sampling for Anomaly Detection. In 2015 Network and Distributed System Security Symposium, San Diego, CA, USA. 2015. (PDF)

B. Juba. Restricted Distribution Automatizability in PAC-Semantics. In 6th ACM Conference on Innovations in Theoretical Computer Science, Rehovot, Israel. 2015. (PDF|PS)
Draft full version. (PDF) Combines and largely subsumes:
On Non-automatizability in PAC-Semantics. Electronic Colloquium on Computational Complexity (ECCC) TR13-094. 2013. (PS|PDF)
PAC Quasi-automatizability of Resolution over Restricted Distributions. arXiv:1304.4633 [cs.DS]. (PS|PDF)

B. Juba. Implicit Learning of Common Sense for Reasoning. In 23rd International Joint Conference on Artificial Intelligence, Beijing, P.R. China. 2013. (PS|PDF)
Preliminary version: Learning implicitly in reasoning in PAC-Semantics. arXiv:1209.0056v1 [cs.AI] (PS|PDF)

B. Juba and R. Williams. Massive Online Teaching to Bounded Learners. In 4th ACM Conference on Innovations in Theoretical Computer Science, Berkeley, CA, USA. 2013.
Previously appeared in Electronic Colloquium on Computational Complexity (ECCC) TR12-107. 2012. (PS|PDF)

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, USA. 2006. (PS|PDF)

Workshop Papers, Invited Contributions, Technical Reports, Theses, Course Projects, etc.

D. Calderon, B. Juba, S. Li, Z. Li, and L. Ruan. Conditional Linear Regression. arXiv:1806.02326 [cs.LG] (PDF)

B. Juba. Computational complexity and the Function-Structure-Environment Loop of the Brain. In Closed-Loop Neuroscience, A. El Hady, editor. Academic Press, 2016. (PDF)
An older version: 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. Compatibility among Diversity: Foundations, lessons, and directions of semantic communication. (Invited paper) In 5th International Workshop on Information Quality and Quality of Service for Pervasive Computing, San Diego, CA, USA. 2013. (PDF)

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 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.

Jolley 508 first initial last name at wustl