Brendan Juba - Papers

Back to the main page. Note: Alphabetical author ordering indicates equal contribution unless otherwise stated. Refereed Publications (jump to unrefereed papers, unpublished manuscripts, etc.) L. Ge, B. Juba, K. Nilsson, and A. Shao. Implicit Learning for Reasoning in First-Order Probabilistic Logic. To appear in UAI 2026. (PDF) Preliminary version: arXiv:2602.14890 [cs.AI] Z. Deng and B. Juba. Stochastic Safe Action Model Learning. In Proceedings of the 39th Conference on Learning Theory PMLR 336:1715-1736, 2026. (PDF|code) Previously appeared in NeurIPS 2023 Workshop on Generalization in Planning. E. Grigorescu, B. Juba, K. Wimmer, and N. Xie. Hardness of Maximum Likelihood Learning of DPPs. To appear in Theory of Computing, 2026. Previously presented in COLT 2022. Preliminary full version: arXiv:2205.12377 [cs.CC] and ECCC TR22-083, 2022. A. Mordoch, O. Karat, L. Shmilovich, Y. Benyamin, B. Juba, and R. Stern. Safe Learning of Multi-Agent Action Models from Concurrent Joint Action Observations. Journal of Artificial Intelligence Research, 86, Article 1, 1-35, 2026. (PDF) An early version: A. Mordoch, R. Stern, and B. Juba. Collaborative Multi-Agent Planning with Black-Box Agents by Learning Action Models. In Workshop on Learning with Strategic Agents (LSA) at AAMAS 2022. (PDF) A. Mordoch, Y. Benyamin, S. S. Shperberg, B. Juba, and R. Stern. Online Learning of Numeric Action Models for Planning. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026), pages 1491-1499, 2026. (PDF) B. Juba and K. Meel. The Limitations and Power of NP-Oracle based Functional Synthesis Techniques. In Proceedings of the 40th AAAI Conference on Artificial Intelligence, volume 17, pages 14261-14268, 2026. (PDF) L. Ge, B. Juba, and K. Nilsson. Polynomial-Time Relational Probabilistic Inference in Open Universes. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2025), Main Track, pages 9058-9067, 2025. (PDF) Preliminary version: arXiv:2505.04115 [cs.AI] J. Huang and B. Juba. Distribution-Specific Agnostic Conditional Classification With Halfspaces. In Proceedings of the 13th International Conference on Learning Representations (ICLR 2025), 2025. (PDF) arXiv:2502.00172 P. Golia, B. Juba, and K. Meel. A Scalable Entropy Estimator. Formal Methods in System Design, 66(2):170-194, 2025. (Special issue on best papers from CAV'22) Previously appeared in CAV 2022. Preliminary version: arXiv:2206.00921 [cs.CR], 2022. A. Estornell, T. Zhang, S. Das, C.-J. Ho, B. Juba, and Y. Vorobeychik. The Impact of Features Used by Algorithms on Perceptions of Fairness. In Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024), pages 376-384, 2024. (PDF) D. Hsu, J. Huang, and B. Juba. Distribution-Specific Auditing for Subgroup Fairness. (Best Student Paper awarded to Jizhou Huang) In 5th Symposium on Foundations of Responsible Computing (FORC 2024), LIPIcs 295, pages 5:1-5:20, 2024. (PDF) A. Mordoch, R. Stern, E. Scala, and B. Juba. Safe Learning of PDDL Domains with Conditional Effects. In Proceedings of the 34th International Conference on Automated Planning and Scheduling (ICAPS 2024), pages 387-395, 2024. (PDF) Previously appeared in ICAPS workshop on Reliable Data-Driven Planning and Scheduling (RDDPS), 2023. A. Shaw, B. Juba, and K. Meel. An Approximate Skolem Function Counter. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), pages 8108-8116, 2024. (PDF) B. Juba, H. S. Le, and R. Stern. Learning Safe Action Models with Partial Observability. In Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024), pages 20159-20167, 2024. (PDF) Previously appeared in NeurIPS workshop on Generalization in Planning (GenPlan'23), 2023. S. Pendurkar, T. Huang, B. Juba, J. Zhang, S. Koenig, and G. Sharon. The (Un)Scalability of Informed Heuristic Function Estimation in NP-Hard Search Problems. Transactions on Machine Learning Research, 2023. (PDF) I. G. Mocanu, V. Belle, and B. Juba. Learnability with PAC Semantics for Multi-Agent Beliefs. Theory and Practice of Logic Programming, 2023 International Conference on Logic Programming, 23(4):730-747, 2023. (PDF) A. Mordoch, B. Juba, and R. Stern. Learning Safe Numeric Action Models. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 12079-12086, 2023. (PDF) A. Estornell, B. Juba, S. Das, and Y. Vorobeychik. Popularizing Fairness: Group Fairness and Individual Welfare. In Proceedings of the 37th AAAI Conference on Artificial Intelligence, pages 7485-7493, 2023. (PDF) B. Juba and L. Liang. Conditional Linear Regression for Heterogeneous Covariances. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022) Proceedings of Machine Learning Research (PMLR) 151:6182-6199, 2022. (PDF) Preliminary version: arXiv:2111.07834 [cs.LG] S. Devic, Z. Deng, and B. Juba. Polynomial Time Reinforcement Learning in Factored State MDPs with Linear Value Functions. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS 2022) Proceedings of Machine Learning Research (PMLR) 151:11280-11304, 2022. (PDF) Previously appeared as Polynomial Time Reinforcement Learning in Correlated FMDPs with Linear Value Functions. arXiv:2107.05187 [cs.LG] B. Juba and R. Stern. Learning Probably Approximately Complete and Safe Action Models for Stochastic Worlds. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI-22), 2022. (PDF). Supplemental material (a worked example): arXiv:2203.12499. B. Juba, H. S. Le, and R. Stern. Safe Learning of Lifted Action Models. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021), pages 379-389, 2021. (PDF) Full technical report version: arXiv:2107.04169 [cs.AI] Previously appeared in Bridging the Gap Between AI Planning and Reinforcement Learning (PRL) Workshop at ICAPS'20, 2020. (PDF) H. Zhang, B. Juba, and G. Van den Broeck. Probabilistic Generating Circuits. In Proceedings of the 38th International Conference on Machine Learning (ICML 2021), pages 12447-12457, 2021. arXiv:2102.09768 [cs.AI], 2021. A. P. Rader, I. G. Mocanu, V. Belle, and B. Juba. Learning Implicitly with Noisy Data in Linear Arithmetic. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), pages 1410-1417, 2021. (PDF) Extended version: arXiv:2010.12619 [cs.AI] Previously appeared in Knowledge Representation & Reasoning Meets Machine Learning (KR2ML) Workshop at NeurIPS'20, 2020. (PDF) A. Agarwala, A. Das, B. Juba, R. Panigrahy, V. Sharan, X. Wang, and R. Zhang. One network fits all? Modular versus monolithic task formulations in neural networks. In Ninth International Conference on Learning Representations (ICLR 2021), 2021. (PDF) An early version: V. Sharan, X. Wang, B. Juba, and R. Panigrahy. Understanding the capabilities and limitations of neural networks for multi-task learning. In Machine Learning with Guarantees workshop at NeurIPS'19, 2019. (PDF) M. Cheraghchi, E. Grigorescu, B. Juba, K. Wimmer, and N. Xie. List Learning with Attribute Noise. In 24th International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research (PMLR) 130:2215-2223, 2021. (PDF, supplementary material) T. Shahar, S. Shekhar, D. Atzmon, A. Saffifine, B. Juba, and R. Stern. Safe Multi-Agent Pathfinding with Time Uncertainty. Journal of Artificial Intelligence Research (JAIR), 70:923-954, 2021. (PDF) To appear in ICAPS 2021 journal track. G. Dehghanpoor, M. Frachetti, and B. Juba. A tensor decomposition method for unsupervised feature learning on satellite imagery. In IEEE International Geoscience and Remote Sensing Symposium (IGARSS) pages 1679-1682, 2020. (PDF) I. G. Mocanu, V. Belle, and B. Juba. Polynomial-time implicit learnability in SMT. In ECAI 2020 - 24th European Conference in Artificial Intelligence Frontiers in Artificial Intelligence and Applications 325, pages 1152-1158, 2020. (PDF) Previously appeared as PAC+SMT in Knowledge Representation & Reasoning Meets Machine Learning (KR2ML) workshop at NeurIPS'19, 2019. (PDF) D. Calderon, B. Juba, S. Li, Z. Li, and L. Ruan. Conditional Linear Regression. In 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research (PMLR) 108:2164-2173, 2020. (PDF) Supplemental material. Preliminary version: arXiv:1806.02326 [cs.LG] (PDF) B. Juba and H. Li. More Accurate Learning of k-DNF Reference Classes. In 34th AAAI Conference on Artificial Intelligence, New York, NY, USA, 2020. (PDF) V. Belle and B. Juba. Implicitly Learning to Reason in First-Order Logic. In Advances in Neural Information Processing Systems 32, 2019. (PDF) Previously appeared in 4th International Workshop on Declarative Learning Based Programming (DeLBP 2019) (co-awarded best paper and nominated for inclusion in the "Best of IJCAI workshops 2019" volume; unfortunately we had to decline the invitation on account of the NeurIPS submission.). (PDF) arXiv:1906.10106 [cs.AI] J. Hainline, B. Juba, H. S. Le, and D. Woodruff. Conditional sparse lp-norm regression with optimal probability. In 22nd International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research 89:1042--1050, 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. In 30th International Conference on Algorithmic Learning Theory (ALT), Proceedings of Machine Learning Research 98:369-382, 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. In 33rd AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 2019. (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. In 33rd AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 2019. (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. In 33rd AAAI Conference on Artificial Intelligence, Honolulu, HI, USA, 2019. (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. R. Stern, L. Lamanna, A. Mordoch, Y. Benyamin, P. Lauer, B. Juba, G. Behnke, C. Muise, P. Bercher, M. Vallati, K. Xi, O. Wattad, and O. Eliyahu. Evaluating Planning Model Learning Algorithms. In Workshop on Knowledge Engineering for Planning and Scheduling (KEPS) at ICAPS 2025, 2025. (PDF) J. Huang and B. Juba. Personalized prediction by learning halfspace reference classes under well-behaved distribution. arXiv:2509.15592 [cs.LG], 2025. L. Ge, B. Juba, and Y. Vorobeychik. Learning linear utility functions from pairwise comparison queries. arxiv:2405:02612 [cs.LG], 2024. Z. Deng, Z. Fryer, B. Juba, R. Panigrahy, and X. Wang. Provable Hierarchical Lifelong Learning with a Sketch-based Modular Architecture. arXiv:2112.10919 [cs.LG] B. Juba. Query-Driven PAC Learning for Reasoning. In 4th International Workshop on Declarative Learning Based Programming (DeLBP 2019). (PDF) arXiv:1906.10118 [cs.AI] 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. McKelvey 2010B