webnotice

Abstract: We discuss the challenging problem of finding pairs of consecutive smooth integers, which we refer to as a smooth twin. In other words the largest prime factor in the twin is relatively small. This computational number theoretic problem has appeared in the context of isogeny-based cryptography whereby a select number of cryptosystems use such twins as part of their parameter setup. The challenging part to the problem is finding smooth twins whose largest prime factor is as small as possible. Prior to this work, twins of this nature have at most 74-bits which is much too small for cryptographic relevance. We bridge this gap by presenting a new method that finds significantly larger smooth twins with as small as possible smoothness bound. The idea of our algorithm is based on the well known and studied problem of finding short vectors in a well constructed lattice. We report a 196-bit smooth twin which falls in this regime as well as a few larger twins that have small (but not the smallest) smoothness bounds.

Abstract: 

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

Abstract: The (parallel) pebbling game is a useful abstraction for analyzing the resources (e.g., space, space-time, amortized space-time) needed to evaluate a function f with a static data-dependency graph G on a (parallel) computer. The underlying question is purely combinatorial: what tradeoffs does a directed acyclic graph (DAG) force between storing intermediate values and recomputing them? This viewpoint has been particularly influential in cryptography, where many “Memory-Hard Function” (MHF) constructions can be modeled by evaluating a fixed DAG.

Abstract:Twin-width is a graph and matrix parameter introduced in 2021 by Bonnet, Kim, Thomassé, and Watrigant as essentially a measure of the 'error' between vertex neighbourhoods over a series of vertex contractions. This talk covers some graph classes with unbounded twin-width. We present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. For a graph G on n vertices, we show that if such a partition exists, then the twin-width of G is at worst sub-linear with respect to n. We use this to obtain an upper bound on the twin-width of interval graphs and of graphs with bounded VC dimension. The latter implies that hereditary classes have sub-linear twin-width if and only if they have bounded VC dimension.

Abstract: A k-colouring of a graph is an assignment of at most k colours to its vertices so that the ends of each edge get different colours. We consider two types of “reconfiguration steps” for transforming a given k-colouring into a target k-colouring. The first is to change the colour of a vertex to a colour which does not appear on any of the vertices it is adjacent to. We say that a graph G is recolourable if for every k greater than its chromatic number, any k-colouring of G can be transformed into any other by these reconfiguration steps. The second (more general) type of reconfiguration step is Kempe swaps. We call a graph Kempe connected if for every k, any k-colouring can be transformed into any other by Kempe swaps.

Abstract: In this talk, we present sequential contracts under matroid constraints. In the sequential setting, an agent can take actions one by one. After each action, the agent observes the stochastic value of the action and then decides which action to take next, if any. At the end, the agent decides what subset of taken actions to use for the principal's reward; and the principal receives the total value of this subset as a reward. Taking each action induces a certain cost for the agent. Thus, to motivate the agent to take actions the principal is expected to offer an appropriate contract. A contract describes the payment from the principal to the agent as a function of the principal's reward obtained through the agent's actions. In this work, we concentrate on studying linear contracts, i.e. the contracts where the principal transfers a fraction of their total reward to the agent. We assume that the total principal's reward is calculated based on a subset of actions that forms an independent set in a given matroid. We establish a relationship between the problem of finding an optimal linear contract (or computing the corresponding principal's utility) and the so called matroid (un)reliability problem. Generally, the above problems turn out to be equivalent subject to adding parallel copies of elements to the given matroid. (Joint work with Jacob Skitsko and Yun Xing)

Abstract: A central goal of quantum information theory is to determine the capacities of a quantum channel for sending different sorts of information.  I’ll highlight the new and fundamentally quantum aspects that arise in quantum information theory compared to the classical theory. These include the central role of entanglement, nonadditivity, and synergies between resources. I will also discuss some challenging open questions that we will have to solve to push the theory forward. 
 

Abstract: We use a new combinatorial construction and a sign-reversing involution to simplify an alternating sum that arises naturally in intersection theory on moduli spaces of curves. In particular, it is well known that a product of ψ classes on the moduli space M₀,ₙ-bar, the most commonly studied compactification of the moduli space M₀,ₙ of choices of n distinct marked points on ℙ¹, is equal to a multinomial coefficient and has many natural combinatorial interpretations.

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