10 citations · 61 across the 34 of their papers we have counts for
41 papers
Beyond Fixed Points: Superpolynomial Capacity of Asymmetric Hopfield Networks
Aakash Kumar, Anatoly Khina, Frederik Mallmann-Trenn +1
Classical Hopfield networks are limited to static patterns due to symmetric weights, whereas asymmetric networks can encode temporal sequences via limit-cycle attractors. Achieving…
Undecided State Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of decided opinions or the undecided state. We consider both the gos…
Structured vs. Unstructured Pruning: An Exponential Gap
Davide Ferre', Frédéric Giroire, Frederik Mallmann-Trenn +1
The Strong Lottery Ticket Hypothesis (SLTH) states that large, randomly initialized neural networks contain sparse subnetworks capable of approximating a target function at initial…
Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks
Justin Dachille, Aurora Rossi, Sunil Kumar Maurya +5
Computing the importance of nodes in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centr…
Modeling Feasible Locomotion of Nanobots for Cancer Detection and Treatment
Noble Harasha, Cristina Gava, Nancy Lynch +2
Deploying motile nanosized particles, also known as ``nanobots'', in the human body promises to improve selectivity in drug delivery and reduce side effects. We consider a swarm of…
Trading-off Accuracy and Communication Cost in Federated Learning
Mattia Jacopo Villani, Emanuele Natale, Frederik Mallmann-Trenn
Leveraging the training-by-pruning paradigm introduced by Zhou et al. and Isik et al. introduced a federated learning protocol that achieves a 34-fold reduction in communication co…
Decision-Making Under Complete Uncertainty: You Will Not Regret Being Greedy
Kristijan Atanasov, Frederik Mallmann-Trenn, Mehmet Mars Seven
In this paper, we propose a game-theoretic model to study the properties of the worst-case regret of the greedy strategy under complete (Knightian) uncertainty. In a game between a…
On the Sparsity of the Strong Lottery Ticket Hypothesis
Emanuele Natale, Davide Ferre', Giordano Giambartolomei +2
Considerable research efforts have recently been made to show that a random neural network contains subnetworks capable of accurately approximating any given neural network tha…
Asynchronous 3-Majority Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with vertices, each vertex starting with one of initial opinions. At each discrete time step,…
Harmonizing vs Polarizing Platform Influence Functions
Hind AlMahmoud, Frederik Mallmann-trenn
We investigate the dynamics of opinion formation on social networking platforms, focusing on how individual opinions, influenced by both social connections and platform algorithms,…
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given dist…
Sorting in One and Two Rounds using -Comparators
Ran Gelles, Zvi Lotker, Frederik Mallmann-Trenn
We examine sorting algorithms for elements whose basic operation is comparing elements simultaneously (a -comparator). We focus on algorithms that use only a single roun…
Community Consensus: Converging Locally despite Adversaries and Heterogeneous Connectivity
Cristina Gava, Aron Vekassy, Matthew Cavorsi +2
We introduce the concept of community consensus in the presence of malicious agents using a well-known median-based consensus algorithm. We consider networks that have multiple wel…
Dynamic Crowd Vetting: Collaborative Detection of Malicious Robots in Dynamic Communication Networks
Matthew Cavorsi, Frederik Mallmann-Trenn, David Saldaña +1
Coordination in a large number of networked robots is a challenging task, especially when robots are constantly moving around the environment and there are malicious attacks within…
Learning Hierarchically-Structured Concepts II: Overlapping Concepts, and Networks With Feedback
Nancy Lynch, Frederik Mallmann-Trenn
We continue our study from Lynch and Mallmann-Trenn (Neural Networks, 2021), of how concepts that have hierarchical structure might be represented in brain-like neural networks, ho…
Prophet Inequalities: Separating Random Order from Order Selection
Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values in an online fashion, sampled from an instance of independent distributions,…
Distributed Averaging in Opinion Dynamics
Petra Berenbrink, Colin Cooper, Cristina Gava +4
We consider two simple asynchronous opinion dynamics on arbitrary graphs where every node has an initial value . In the first process, the NodeModel, at each time step…
Beyond Impossibility: Balancing Sufficiency, Separation and Accuracy
Limor Gultchin, Vincent Cohen-Addad, Sophie Giffard-Roisin +2
Among the various aspects of algorithmic fairness studied in recent years, the tension between satisfying both \textit{sufficiency} and \textit{separation} -- e.g. the ratios of po…
Diversity, Fairness, and Sustainability in Population Protocols
Nan Kang, Frederik Mallmann-Trenn, Nicolás Rivera
Over the years, population protocols with the goal of reaching consensus have been studied in great depth. However, many systems in the real-world do not result in all agents event…
Crowd Vetting: Rejecting Adversaries via Collaboration--with Application to Multi-Robot Flocking
Frederik Mallmann-Trenn, Matthew Cavorsi, Stephanie Gil
We characterize the advantage of using a robot's neighborhood to find and eliminate adversarial robots in the presence of a Sybil attack. We show that by leveraging the opinions of…
Online Page Migration with ML Advice
Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrović +1
We consider online algorithms for the {\em page migration problem} that use predictions, potentially imperfect, to improve their performance. The best known online algorithms for t…
How to Spread a Rumor: Call Your Neighbors or Take a Walk?
George Giakkoupis, Frederik Mallmann-Trenn, Hayk Saribekyan
We study the problem of randomized information dissemination in networks. We compare the now standard PUSH-PULL protocol, with agent-based alternatives where information is dissemi…
Learning Hierarchically Structured Concepts
Nancy Lynch, Frederik Mallmann-Trenn
We study the question of how concepts that have structure get represented in the brain. Specifically, we introduce a model for hierarchically structured concepts and we show how a…
How to Color a French Flag--Biologically Inspired Algorithms for Scale-Invariant Patterning
Alberto Ancona, Ayesha Bajwa, Nancy Lynch +1
In the French flag problem, initially uncolored cells on a grid must differentiate to become blue, white or red. The goal is for the cells to color the grid as a French flag, i.e.,…