2026 North American School of Information Theory
June 22-26, 2026 | Brigham Young University, Provo, UT
Program, Abstracts, & Slides
Explore the schedule and materials
Schedule
Talk Details, Abstracts & Materials
Privacy-Preserving and Secure Computation for Distributed and Cloud Environments
Modern data-driven applications increasingly rely on cloud computing infrastructures to store data and execute computationally intensive tasks. While cloud platforms offer unprecedented scalability, flexibility, and cost efficiency, they also introduce significant privacy and security challenges. In particular, users must often entrust sensitive data and computational workloads to third-party service providers that may be honest-but-curious or otherwise untrusted. Consequently, both the underlying data and the nature of the computation may be exposed to unauthorized parties, creating substantial risks to confidentiality and privacy.
We first focus on the area of Private Computation, a collection of techniques that enables users to compute functions over remotely stored datasets while concealing sensitive aspects of the request. Depending on the application, privacy requirements may include hiding the identities of the data items accessed, the functions being evaluated, or both. We discuss the fundamental principles underlying private computation and demonstrate how these techniques enable privacy-preserving data analytics, statistical inference, and machine learning over distributed and cloud-hosted datasets.
We then discuss the broader area of Secure Computation, which encompasses methods for securely outsourcing computational tasks and performing computations directly on protected or encrypted data. We present a range of algebraic, coding-theoretic, and information-theoretic techniques that provide rigorous privacy guarantees while maintaining practical computational and communication complexity. Particular emphasis is placed on approaches that leverage the structure of specific computational problems to achieve substantial efficiency gains.
Monday — 8:30-10:00
Monday — 10:30-12:00 and 1:30-3:00
Communicating Short Messages With and Without Feedback
Monday — 3:30-5:00
Quantum Low-Density Parity-Check Codes: Constructions and Decoders
Spurred by recent advances in quantum science and engineering, interest in quantum information theory and coding has been increasing at a rapid pace. Much of this interest is driven by the promise of quantum computing and its potential to solve key problems much faster than classical computers. One promising technology for fault-tolerant quantum computing is error-correction based on quantum low-density parity-check (QLDPC) codes. This talk gives an overview of QLDPC code constructions and decoders with some emphasis message-passing decoding. In particular, it will discuss why code degeneracy causes convergence issues and how decoder modifications, such as guided decimation, can improve performance.
Tuesday — 8:30-10:00
Theory and Practice of Diffusion Models
Tuesday — 10:30-12:00 and 1:30-3:00
Short Tutorial
Tuesday — 3:30-5:00
Improving Generalization, Robustness, and Reliability in Machine Learning: a Coding-Theoretic Approach
In this tutorial, we extend the role of coding and decoding beyond their classical use in reliable communication and storage, positioning them as fundamental tools for improving generalization, adversarial robustness, and system-level reliability in machine learning. This shift is enabled by rethinking code design through the lens of learning theory rather than classical algebraic coding, making coding a native component of modern ML architectures.
We then show how this framework advances the state of the art in three domains:
-
Generalization: The coding/decoding framework introduces an auxiliary data path alongside the original one. We prove that the inconsistency between these paths is proportional to higher-order gradients of the model, enabling this inconsistency to act as a smoothness regularizer during training. Perhaps surprisingly, this approach works for both supervised and unsupervised learning tasks. In particular, we demonstrate improvements in contrastive learning, where alternative mechanisms for encouraging smoothness remain limited.
-
Adversarial Robustness: We prove that data permutations in the process of encoding and decoding can provide gradient obfuscation, without sacrificing predictive performance, thereby improving robustness to adversarial perturbations at inference time. Using this approach, we improve robustness and surpass leading methods on adversarial defense benchmarks.
-
Reliability: In distributed machine learning settings, the framework improves resilience against stragglers and adversarial servers. We provide formal guarantees that bound approximation error as a function of the number of total and faulty servers, while outperforming the current state of the art.
Wednesday — 8:30-10:00 and 10:30-12:00
-
Computational-Statistical Gaps in High-dimensional Inference: Low-degree polynomials, AMP, and Their Connections
When does high-dimensional data contain enough information to recover a hidden signal, and when can that information be extracted efficiently? These two questions often have different answers. This lecture surveys the computational–statistical gap phenomenon in high-dimensional inference, with an emphasis on low-degree polynomial methods and approximate message passing. We will start with planted clique as a concrete example of a gap between statistical possibility and efficient computation, where exhaustive search succeeds at logarithmic clique size but known polynomial-time algorithms require clique size on the order of sqrt n. We then develop the low-degree method, first for detection through the low-degree likelihood ratio and then for estimation through low-degree MMSE and overlap. The second half of the lecture centers on spiked Wigner / rank-one matrix estimation, a model where low-degree estimation, PCA, Bayes estimation, and AMP can be compared cleanly. We will introduce AMP, explain the Onsager correction and state evolution, and discuss how AMP gives an algorithmic threshold. We conclude with the low-degree–AMP equivalence in rank-one matrix estimation, explaining how AMP can match the optimal constant-degree polynomial estimator and thereby provide a candidate computational threshold.
Thursday — 8:30-10:00
From Conformal Prediction to Verification and Uncertainty Quantification in Generative AI
Thursday — 10:30-12:00 and 1:30-3:00
Long Tutorial
Thursday — 3:30-5:00 and Friday — 8:30-10:00
Quickest Change Detection and its Application to Learning in Nonstationary Environments
Friday — 10:30-12:00