Events

Abstract:The satisfiability threshold of a random constraint satisfaction problem (CSP) is the density of constraints at which a random CSP instance transitions from being satisfiable to unsatisfiable with high probability. Much of the research on well known CSPs, including the $k$-SAT problem, $k$-XORSAT problem, hypergraph colouring, and systems of linear equations, has focused on determining satisfiability thresholds.

In this talk we consider systems of linear equations over finite commutative rings as CSPs, and build on the work of Ayre, Coja-Oghlan, Gao, and Müller, who determined the satisfiability threshold for random linear equations over a finite field. We determine when the satisfiability threshold is linear in the number of variables, and show that any linear threshold over a principal ideal ring coincides with the (unique) linear threshold over fields. We also determine the satisfiability threshold for some examples of non-principal ideal rings.

This is joint work with Jane Gao.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.

Abstract:  Given copies of a quantum state, a shadow tomography protocol aims to learn all expectation values from a fixed set of observables, to within a given precision. We say that such a protocol is triply efficient if it is sample efficient, time efficient, and uses measurements that entangle a constant number of copies of the state at a time.   A natural family of shadow tomography protocols based on random single-copy Clifford measurements can be understood as arising from fractional colorings of a graph G that encodes the commutation structure of the set of observables. Here we describe a framework for two-copy shadow tomography that uses an initial round of Bell measurements to reduce to a fractional coloring problem in an induced subgraph of G with bounded clique number. This coloring problem can be addressed using techniques from graph theory known as chi-boundedness. Using this framework we give the first triply efficient  shadow tomography scheme for the set of local fermionic observables, which arise in a broad class of interacting fermionic systems in physics and chemistry. We also give a triply efficient scheme for the set of all -qubit Pauli observables. Our protocols for these tasks use two-copy measurements, which is necessary: sample-efficient schemes are provably impossible using only single-copy measurements. This is joint work with Robbie King, Robin Kothari, and Ryan Babbush.

Abstract: Around 1900 Young and Frobenius (independently, and through very different techniques) obtained a formula for the dimensions of the irreducible representations of the symmetric group. Some 53 years later, Frame, Robinson and Thrall noticed that the Young-Frobenius formula simplified into the now famous hook length formula. Nowadays there are many proofs, but the hook length formula remains something of a mystery, as if some deeper understanding lies just out of reach. One aspect of this mystery is that none of the proofs seem to indicate how one might come up with the formula in the first place, other than just guessing.

I will attempt to answer that question. It is an improbable tale that meanders through scenes of Young symmetrizers, Schur-Weyl duality, Weyl algebras, elementary combinatorics, and Plücker relations. All because Google's AI gave me a very obviously wrong answer when I was trying to find out the square of a Young symmetrizer.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.

Abstract: The Fujisaki-Okamoto (FO) transform is a fundamental building block in new post-quantum cryptography standards like NIST's ML-KEM, where it is used to convert a weakly secure public key encryption scheme into a key encapsulation mechanism (KEM) secure against active attackers. In this talk, we'll explore two approaches to add extra security and functionality to post-quantum KEMs by enhancing the FO transform. First, we see how a birthday-style collision argument lets an attacker who collects many ciphertexts halve the security of the FrodoKEM and HQC standards, and how extending the FO transform with public salts thwarts this multi-target attack. Second, we turn to implementation flaws: for 19 months, HQC's reference implementation effectively skipped a security-critical verification step, yet basic correctness tests still passed. We show how the principle of "verifiable verification", via an extension of the FO transform, ties security to functionality, so that an implementation which that skips it visibly breaks.

Abstract: The sign coherence of c-vectors is one of the fundamental theorems of cluster algebras with principal coefficients.  Gekhtman and Nakanishi posed the Asymptotic Sign Coherence Conjecture for cluster algebras with arbitrary coefficients, which says sign coherence should eventually hold in any sufficiently generic infinite mutation sequence.  We prove that for cluster algebras from quivers of arbitrary rank, their conjecture holds with probability 1 for a random mutation sequence.  Our results also establish the conjecture in full generality for many families of quivers.  This is joint work with Amanda Burcroff.

There will be a pre-seminar presenting relevant background at beginning graduate level starting at 1:30pm in MC 5417.