Events

Submodular maximization under various constraints is a fundamental problem studied continuously, in both computer science and operations research, since the late 1970’s. A central technique in this field is to approximately optimize the multilinear extension of the submodular objective, and then round the solution. The use of this technique requires a solver able to approximately maximize multilinear extensions. Following a long line of work, Buchbinder and Feldman(2019) described such a solver guaranteeing 0.385-approximation for down-closed constraints, while Oveis Gharan and Vondrak (2011) showed that no solver can guarantee better than 0.478-approximation. In this talk, I will present a new solver guaranteeing 0.401-approximation, which significantly reduces the gap between the best known solver and the inapproximability result. The design and analysis of the new solver are based on a novel bound that we have proved for DR-submodular functions, and might be of independent interest.

Based on a joint work with Niv Buchbinder.

The effective resistance satisfies the triangle inequality and thus defines a metric. For finite graphs, this metric contains all of the information about the expected hitting times between pairs of vertices as well as about the cover time of the graph (= the first time by which every vertex has been visited at least once).

We show that for transitive graphs, the effective resistance between a pair of vertices which are at distance r from one another is comparable (up to a constant multiplicative factor, depending only on the degree) to the expected number of returns to the origin by time r^2. We use this (in the transitive bounded degree setup) to:

(1) Give a complete characterization of the effective resistance metric up to quasi-isometries, with effective O(1) implicit constants.

(2) Give simple formulas, involving few natural geometric quantities, for the orders of the expected cover time and the maximal (over all pairs) effective resistance between a pair of vertices.

Joint work with Lucas Teyssier (UBC) and Matt Tointon (U. Bristol).

This talk presents two wavelet-based innovations that significantly improve convolutional neural networks (CNNs) in terms of scalability, computational efficiency, and robustness. I’ll begin with WTConv, a novel convolutional layer that leverages multilevel Haar wavelet decomposition to expand receptive fields efficiently. WTConv scales logarithmically with kernel size, enabling nearly global receptive fields without the parameter bloat typical of large kernels. Beyond improving classification accuracy, WTConv boosts shape bias and robustness to corruptions, all while remaining a lightweight, drop-in replacement for depthwise convolutions.

Next, I’ll introduce Wavelet Compressed Convolution (WCC), a method for compressing high-resolution activation maps in image-to-image tasks. By applying joint wavelet-domain shrinkage across channels and executing 1×1 convolutions directly on the compressed representation, WCC substantially reduces memory bandwidth and compute cost. Unlike aggressive quantization—which often causes severe degradation—WCC maintains high accuracy across tasks like segmentation, super-resolution, and depth estimation, even under extreme compression. Together, these methods show how wavelet transforms can serve as a powerful, hardware-friendly toolset for designing scalable and efficient CNNs.

Bio:
Shahaf Finder is a PhD candidate in Computer Science, supervised by Prof. Oren Freifeld and Prof. Eran Treister, researching efficient neural networks with a focus on convolutional neural networks (CNNs) and graph neural networks (GNNs). He is also a Co-Founder of LimitlessCNC, a startup focused on integrating AI into CNC programming, where he leads the development of the core algorithmic technology.

A copy of a permutation pattern (say, 132) in a sequence of numbers is any subsequence whose values have the same relative order as in the pattern. (Say, for 132, the first element is smallest, the second is largest, and the third is in-between.)

Counting permutation patterns has a surprisingly rich set of connections and applications in ranking, statistics, combinatorics, fine-grained complexity, and parametrized complexity, especially for fixed small k. Here are three examples:
(i) Counting 4-cycles in sparse graphs is equivalent to counting 4-patterns [Dudek and Gawrychowski, 2020].
(ii) Many fundamental tests in nonparametric statistics amount to counting k-patterns for k up to 5.
(iii) The study of twin-width in parametrized complexity has originated from a breakthrough FPT algorithm of Guillemot and Marx [2013] for permutation pattern detection, which runs in linear time when k is fixed.

In this talk I will describe an algorithm for approximately counting all k-patterns for k up to 5 in near-linear time, deterministically, to within a (1+eps)-multiplicative error. This algorithm gives the first known (conditional) separation between exact and approximate counting in this domain. Interestingly, our algorithm leverages sublinear techniques from distribution testing, which to our knowledge have not been used in a pattern counting context before.

Joint work with Slobodan Mitrović (UC Davis) and Pranjal Srivastava (MIT)

TBD

TBD

TBD