קולוקוויום וסמינרים

In Approval-Based Committee (ABC) voting,  each voter lists the candidates they approve and then a voting rule aggregates the individual approvals into a committee that represents the collective choice of the voters. 
An extensively studied class of such rules is the class of ABC scoring rules, where each voter contributes to each possible committee a score based on the voter's approvals. 
We initiate a study of ABC voting in the presence of constraints about the general context surrounding the candidates. 
Specifically, we consider a framework in which there is a relational database with information about the candidates together with integrity constraints on the relational database extended with a virtual relation representing the committee. 
For an ABC scoring rule, the goal is to find a committee of maximum score such that all integrity constraints hold in the extended database. 

We focus on two well-known types of integrity constraints in relational databases: 
tuple-generating dependencies (TGDs) and denial constraints (DCs). 
The former can express, for example, desired representations of groups, while the latter can express conflicts among candidates.  
ABC voting is known to be computationally hard without integrity constraints, except for the case of approval voting where it is tractable. 
We show that integrity constraints make the problem NP-hard for approval voting, but we also identify certain tractable cases when key constraints are used. 
We then present an implementation of the framework via a reduction to Mixed Integer Programming (MIP) that supports arbitrary ABC scoring rules, TGDs and DCs. 
We devise heuristics for optimizing the resulting MIP, and describe an empirical study that illustrates the effectiveness of the optimized MIP over databases in three different domains.

As decentralized ledgers and blockchains become more common,  cross-chain interoperability becomes essential to making those ledgers useful. In a cross-chain task, $m$ active, Byzantine parties undertake to trade assets using n passive but trustworthy smart contracts. Each party seeks an outcome that maximizes its own utility in the presence of Byzantine counterparties. This talk introduces a novel task called ``cross-chain consensus''.

We show that cross-chain consensus is \emph{universal}, meaning that any cross-chain consensus protocol can be transformed into a protocol for any other well-formed cross-chain task. We show that cross-chain consensus is impossible using unsigned messages, even if communication channels are authenticated. If each party can generate signed messages verifiable on all the blockchains, then there is a tight bound of $\Theta(m)$ communication rounds, where $m$ is the number of participating parties. Moreover, there is a communication-round optimal protocol that uses a finite number of precomputed signed messages.

Joint work with Sucharita Jayanti.

In this seminar I will present our paper that was published in NeurIPS 2024. We introduce hierarchical selective classification, which extends selective classification to a hierarchical setting. Our approach leverages the inherent structure of class relationships, enabling models to reduce the specificity of their predictions when faced with uncertainty. We formalize hierarchical risk and coverage, and introduce hierarchical risk-coverage curves. Next, we develop algorithms for hierarchical selective classification (which we refer to as "inference rules"), and propose an efficient algorithm that guarantees a target accuracy constraint with high probability. Lastly, we conduct extensive empirical studies on over a thousand ImageNet classifiers, revealing that training regimes such as CLIP, pretraining on ImageNet21k and knowledge distillation boost hierarchical selective performance.

I will describe several old and new applications of topological and algebraic methods in the derivation of combinatorial results. In all of them the proofs provide no efficient procedures for solving the corresponding algorithmic questions. The problem of finding such procedures (or convincing reasons indicating that they are unlikely to exist) is an intriguing challenge and I will mention some progress in the study of this problem too.

Bio:

Noga Alon is a Professor of Mathematics at Princeton University and a Professor Emeritus of Mathematics and Computer Science at Tel Aviv University.

He works in Discrete Mathematics and its applications in Theoretical Computer Science, Information Theory, Combinatorial Geometry, and Combinatorial Number Theory.

He is a member of the Israel Academy of Sciences and Humanities and of the Academia Europaea, and an honorary member of the Hungarian Academy of Sciences. He received several awards, three recent ones are the 2022 Shaw Prize in Mathematical Sciences, the 2022 Knuth Prize for outstanding contributions to the foundations of computer science and the 2024 Wolf Prize in Mathematics. 

This doctoral research focuses on advancing the autonomy of Unmanned Aerial Vehicles (UAVs) operating in complex, dense urban environments, particularly emphasizing the critical task of identifying safe landing locations. Traditional sensing and decision-making methods often struggle with the intricacies of such settings. This work proposes leveraging semantic segmentation, a machine-learning technique that interprets visual scenes by assigning a class label (e.g., road, building, vegetation) to each pixel in an image, as a sophisticated sensor modality for UAVs.

A primary contribution is a novel multi-resolution strategy for landing site selection. This method involves the UAV collecting visual information at progressively decreasing altitudes, thereby acquiring images with increasing spatial resolution. For each potential terrain patch, a probability distribution representing its suitability for landing is maintained and updated as new data from different altitudes becomes available. A landing site is confirmed once the confidence level for a patch surpasses a predefined threshold. This decision-making process relies on a semantic segmentation algorithm to provide per-pixel likelihoods of different terrain types, which are then integrated with prior knowledge and previous measurements.

To facilitate the development and rigorous evaluation of semantic segmentation algorithms tailored for drone applications, a comprehensive dataset named MESSI (Multi-Elevation Semantic Segmentation Image) was developed. MESSI is distinguished by its inclusion of images captured from a wide range of altitudes and diverse urban locations, reflecting the varied perspectives encountered during a realistic 3D drone flight. This richly annotated dataset serves as a valuable resource for training deep neural networks and benchmarking their performance in understanding urban scenes.

Furthermore, this research addresses a fundamental challenge in applying semantic segmentation to probabilistic search problems: the statistical nature of its outputs differs from assumptions in classical detection theory. A systematic methodology is introduced to bridge this gap, enabling the effective integration of semantic segmentation into established probabilistic search frameworks. This integration provides a more robust foundation for decision-making processes, such as the identification of viable landing sites in partially known environments. The practical feasibility and effectiveness of the proposed approaches are demonstrated through extensive simulations and validation using real-world datasets, highlighting their potential to significantly enhance UAV operational capabilities in challenging urban settings.