@inproceedings{22373, abstract = {Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. In the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n. We extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem. Finally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem. For the two latter problems no upper or lower bounds were previously known.}, author = {El-Hayek, Antoine and Henzinger, Monika H and Schmid, Stefan}, booktitle = {14th Innovations in Theoretical Computer Science Conference}, editor = {Tauman Kalai, Yael}, isbn = {9783959772631}, issn = {1868-8969}, keywords = {broadcast, cover, k-broadcast, dynamic radius, dynamic graphs, oblivious message adversary, time complexity, Theory of computation → Distributed algorithms, Networks → Network algorithms}, location = {Cambridge, Massachusetts, USA}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks}}, doi = {10.4230/LIPICS.ITCS.2023.47}, volume = {251}, year = {2023}, } @unpublished{15039, abstract = {A crucial property for achieving secure, trustworthy and interpretable deep learning systems is their robustness: small changes to a system's inputs should not result in large changes to its outputs. Mathematically, this means one strives for networks with a small Lipschitz constant. Several recent works have focused on how to construct such Lipschitz networks, typically by imposing constraints on the weight matrices. In this work, we study an orthogonal aspect, namely the role of the activation function. We show that commonly used activation functions, such as MaxMin, as well as all piece-wise linear ones with two segments unnecessarily restrict the class of representable functions, even in the simplest one-dimensional setting. We furthermore introduce the new N-activation function that is provably more expressive than currently popular activation functions. We provide code at this https URL.}, author = {Prach, Bernd and Lampert, Christoph}, booktitle = {arXiv}, title = {{1-Lipschitz neural networks are more expressive with N-activations}}, doi = {10.48550/ARXIV.2311.06103}, year = {2023}, } @inproceedings{14771, abstract = {Pruning—that is, setting a significant subset of the parameters of a neural network to zero—is one of the most popular methods of model compression. Yet, several recent works have raised the issue that pruning may induce or exacerbate bias in the output of the compressed model. Despite existing evidence for this phenomenon, the relationship between neural network pruning and induced bias is not well-understood. In this work, we systematically investigate and characterize this phenomenon in Convolutional Neural Networks for computer vision. First, we show that it is in fact possible to obtain highly-sparse models, e.g. with less than 10% remaining weights, which do not decrease in accuracy nor substantially increase in bias when compared to dense models. At the same time, we also find that, at higher sparsities, pruned models exhibit higher uncertainty in their outputs, as well as increased correlations, which we directly link to increased bias. We propose easy-to-use criteria which, based only on the uncompressed model, establish whether bias will increase with pruning, and identify the samples most susceptible to biased predictions post-compression. Our code can be found at https://github.com/IST-DASLab/pruned-vision-model-bias.}, author = {Iofinova, Eugenia B and Peste, Elena-Alexandra and Alistarh, Dan-Adrian}, booktitle = {2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition}, issn = {2575-7075}, location = {Vancouver, BC, Canada}, pages = {24364--24373}, publisher = {IEEE}, title = {{Bias in pruned vision models: In-depth analysis and countermeasures}}, doi = {10.1109/cvpr52729.2023.02334}, year = {2023}, } @article{12787, abstract = {Populations evolve in spatially heterogeneous environments. While a certain trait might bring a fitness advantage in some patch of the environment, a different trait might be advantageous in another patch. Here, we study the Moran birth–death process with two types of individuals in a population stretched across two patches of size N, each patch favouring one of the two types. We show that the long-term fate of such populations crucially depends on the migration rate μ between the patches. To classify the possible fates, we use the distinction between polynomial (short) and exponential (long) timescales. We show that when μ is high then one of the two types fixates on the whole population after a number of steps that is only polynomial in N. By contrast, when μ is low then each type holds majority in the patch where it is favoured for a number of steps that is at least exponential in N. Moreover, we precisely identify the threshold migration rate μ⋆ that separates those two scenarios, thereby exactly delineating the situations that support long-term coexistence of the two types. We also discuss the case of various cycle graphs and we present computer simulations that perfectly match our analytical results.}, author = {Svoboda, Jakub and Tkadlec, Josef and Kaveh, Kamran and Chatterjee, Krishnendu}, issn = {1471-2946}, journal = {Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences}, number = {2271}, publisher = {The Royal Society}, title = {{Coexistence times in the Moran process with environmental heterogeneity}}, doi = {10.1098/rspa.2022.0685}, volume = {479}, year = {2023}, } @article{12762, abstract = {Neurons in the brain are wired into adaptive networks that exhibit collective dynamics as diverse as scale-specific oscillations and scale-free neuronal avalanches. Although existing models account for oscillations and avalanches separately, they typically do not explain both phenomena, are too complex to analyze analytically or intractable to infer from data rigorously. Here we propose a feedback-driven Ising-like class of neural networks that captures avalanches and oscillations simultaneously and quantitatively. In the simplest yet fully microscopic model version, we can analytically compute the phase diagram and make direct contact with human brain resting-state activity recordings via tractable inference of the model’s two essential parameters. The inferred model quantitatively captures the dynamics over a broad range of scales, from single sensor oscillations to collective behaviors of extreme events and neuronal avalanches. Importantly, the inferred parameters indicate that the co-existence of scale-specific (oscillations) and scale-free (avalanches) dynamics occurs close to a non-equilibrium critical point at the onset of self-sustained oscillations.}, author = {Lombardi, Fabrizio and Pepic, Selver and Shriki, Oren and Tkačik, Gašper and De Martino, Daniele}, issn = {2662-8457}, journal = {Nature Computational Science}, pages = {254--263}, publisher = {Springer Nature}, title = {{Statistical modeling of adaptive neural networks explains co-existence of avalanches and oscillations in resting human brain}}, doi = {10.1038/s43588-023-00410-9}, volume = {3}, year = {2023}, } @unpublished{13312, abstract = {Superconductor/semiconductor hybrid devices have attracted increasing interest in the past years. Superconducting electronics aims to complement semiconductor technology, while hybrid architectures are at the forefront of new ideas such as topological superconductivity and protected qubits. In this work, we engineer the induced superconductivity in two-dimensional germanium hole gas by varying the distance between the quantum well and the aluminum. We demonstrate a hard superconducting gap and realize an electrically and flux tunable superconducting diode using a superconducting quantum interference device (SQUID). This allows to tune the current phase relation (CPR), to a regime where single Cooper pair tunneling is suppressed, creating a $ \sin \left( 2 \varphi \right)$ CPR. Shapiro experiments complement this interpretation and the microwave drive allows to create a diode with $ \approx 100 \%$ efficiency. The reported results open up the path towards monolithic integration of spin qubit devices, microwave resonators and (protected) superconducting qubits on a silicon technology compatible platform.}, author = {Valentini, Marco and Sagi, Oliver and Baghumyan, Levon and Gijsel, Thijs de and Jung, Jason and Calcaterra, Stefano and Ballabio, Andrea and Servin, Juan Aguilera and Aggarwal, Kushagra and Janik, Marian and Adletzberger, Thomas and Souto, Rubén Seoane and Leijnse, Martin and Danon, Jeroen and Schrade, Constantin and Bakkers, Erik and Chrastina, Daniel and Isella, Giovanni and Katsaros, Georgios}, booktitle = {arXiv}, keywords = {Mesoscale and Nanoscale Physics}, title = {{Radio frequency driven superconducting diode and parity conserving Cooper pair transport in a two-dimensional germanium hole gas}}, doi = {10.48550/arXiv.2306.07109}, year = {2023}, } @article{13340, abstract = {Photoisomerization of azobenzenes from their stable E isomer to the metastable Z state is the basis of numerous applications of these molecules. However, this reaction typically requires ultraviolet light, which limits applicability. In this study, we introduce disequilibration by sensitization under confinement (DESC), a supramolecular approach to induce the E-to-Z isomerization by using light of a desired color, including red. DESC relies on a combination of a macrocyclic host and a photosensitizer, which act together to selectively bind and sensitize E-azobenzenes for isomerization. The Z isomer lacks strong affinity for and is expelled from the host, which can then convert additional E-azobenzenes to the Z state. In this way, the host–photosensitizer complex converts photon energy into chemical energy in the form of out-of-equilibrium photostationary states, including ones that cannot be accessed through direct photoexcitation.}, author = {Gemen, Julius and Church, Jonathan R. and Ruoko, Tero-Petri and Durandin, Nikita and Białek, Michał J. and Weissenfels, Maren and Feller, Moran and Kazes, Miri and Borin, Veniamin A. and Odaybat, Magdalena and Kalepu, Rishir and Diskin-Posner, Yael and Oron, Dan and Fuchter, Matthew J. and Priimagi, Arri and Schapiro, Igor and Klajn, Rafal}, issn = {1095-9203}, journal = {Science}, number = {6664}, pages = {1357--1363}, publisher = {American Association for the Advancement of Science}, title = {{Disequilibrating azoarenes by visible-light sensitization under confinement}}, doi = {10.1126/science.adh9059}, volume = {381}, year = {2023}, } @inproceedings{14210, abstract = {Research on recovering the latent factors of variation of high dimensional data has so far focused on simple synthetic settings. Mostly building on unsupervised and weakly-supervised objectives, prior work missed out on the positive implications for representation learning on real world data. In this work, we propose to leverage knowledge extracted from a diversified set of supervised tasks to learn a common disentangled representation. Assuming that each supervised task only depends on an unknown subset of the factors of variation, we disentangle the feature space of a supervised multi-task model, with features activating sparsely across different tasks and information being shared as appropriate. Importantly, we never directly observe the factors of variations, but establish that access to multiple tasks is sufficient for identifiability under sufficiency and minimality assumptions. We validate our approach on six real world distribution shift benchmarks, and different data modalities (images, text), demonstrating how disentangled representations can be transferred to real settings.}, author = {Fumero, Marco and Wenzel, Florian and Zancato, Luca and Achille, Alessandro and Rodolà, Emanuele and Soatto, Stefano and Schölkopf, Bernhard and Locatello, Francesco}, booktitle = {37th International Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {New Orleans, LA, United States}, publisher = {Neural Information Processing Systems Foundation}, title = {{Leveraging sparse and shared feature activations for disentangled representation learning}}, volume = {36}, year = {2023}, } @inproceedings{14952, abstract = {While different neural models often exhibit latent spaces that are alike when exposed to semantically related data, this intrinsic similarity is not always immediately discernible. Towards a better understanding of this phenomenon, our work shows how representations learned from these neural modules can be translated between different pre-trained networks via simpler transformations than previously thought. An advantage of this approach is the ability to estimate these transformations using standard, well-understood algebraic procedures that have closed-form solutions. Our method directly estimates a transformation between two given latent spaces, thereby enabling effective stitching of encoders and decoders without additional training. We extensively validate the adaptability of this translation procedure in different experimental settings: across various trainings, domains, architectures (e.g., ResNet, CNN, ViT), and in multiple downstream tasks (classification, reconstruction). Notably, we show how it is possible to zero-shot stitch text encoders and vision decoders, or vice-versa, yielding surprisingly good classification performance in this multimodal setting.}, author = {Maiorca, Valentino and Moschella, Luca and Norelli, Antonio and Fumero, Marco and Locatello, Francesco and Rodolà, Emanuele}, booktitle = {37th Conference on Neural Information Processing Systems}, location = {New Orleans, LA, United States}, pages = {55394--55414}, publisher = {Neural Information Processing Systems Foundation}, title = {{Latent space translation via semantic alignment}}, doi = {10.52202/075280-2418}, year = {2023}, } @inproceedings{14207, abstract = {The binding problem in human cognition, concerning how the brain represents and connects objects within a fixed network of neural connections, remains a subject of intense debate. Most machine learning efforts addressing this issue in an unsupervised setting have focused on slot-based methods, which may be limiting due to their discrete nature and difficulty to express uncertainty. Recently, the Complex AutoEncoder was proposed as an alternative that learns continuous and distributed object-centric representations. However, it is only applicable to simple toy data. In this paper, we present Rotating Features, a generalization of complex-valued features to higher dimensions, and a new evaluation procedure for extracting objects from distributed representations. Additionally, we show the applicability of our approach to pre-trained features. Together, these advancements enable us to scale distributed object-centric representations from simple toy to real-world data. We believe this work advances a new paradigm for addressing the binding problem in machine learning and has the potential to inspire further innovation in the field.}, author = {Löwe, Sindy and Lippe, Phillip and Locatello, Francesco and Welling, Max}, booktitle = {37th Conference on Neural Information Processing Systems}, issn = {1049-5258}, location = {New Orleans, LA, United States}, publisher = {Neural Information Processing Systems Foundation}, title = {{Rotating features for object discovery}}, volume = {36}, year = {2023}, } @inproceedings{14948, abstract = {The extraction of modular object-centric representations for downstream tasks is an emerging area of research. Learning grounded representations of objects that are guaranteed to be stable and invariant promises robust performance across different tasks and environments. Slot Attention (SA) learns object-centric representations by assigning objects to \textit{slots}, but presupposes a \textit{single} distribution from which all slots are randomly initialised. This results in an inability to learn \textit{specialized} slots which bind to specific object types and remain invariant to identity-preserving changes in object appearance. To address this, we present \emph{\textsc{Co}nditional \textsc{S}lot \textsc{A}ttention} (\textsc{CoSA}) using a novel concept of \emph{Grounded Slot Dictionary} (GSD) inspired by vector quantization. Our proposed GSD comprises (i) canonical object-level property vectors and (ii) parametric Gaussian distributions, which define a prior over the slots. We demonstrate the benefits of our method in multiple downstream tasks such as scene generation, composition, and task adaptation, whilst remaining competitive with SA in popular object discovery benchmarks.}, author = {Kori, Avinash and Locatello, Francesco and Ribeiro, Fabio De Sousa and Toni, Francesca and Glocker, Ben}, booktitle = {12th International Conference on Learning Representations}, location = {Vienna, Austria}, publisher = {ICLR}, title = {{Grounded object centric learning}}, year = {2023}, } @article{12313, abstract = {Let P be a nontorsion point on an elliptic curve defined over a number field K and consider the sequence {Bn}n∈N of the denominators of x(nP). We prove that every term of the sequence of the Bn has a primitive divisor for n greater than an effectively computable constant that we will explicitly compute. This constant will depend only on the model defining the curve.}, author = {Verzobio, Matteo}, issn = {0030-8730}, journal = {Pacific Journal of Mathematics}, number = {2}, pages = {331--351}, publisher = {Mathematical Sciences Publishers}, title = {{Some effectivity results for primitive divisors of elliptic divisibility sequences}}, doi = {10.2140/pjm.2023.325.331}, volume = {325}, year = {2023}, } @article{14245, abstract = {We establish effective counting results for lattice points in families of domains in real, complex and quaternionic hyperbolic spaces of any dimension. The domains we focus on are defined as product sets with respect to an Iwasawa decomposition. Several natural diophantine problems can be reduced to counting lattice points in such domains. These include equidistribution of the ratio of the length of the shortest solution (x,y) to the gcd equation bx−ay=1 relative to the length of (a,b), where (a,b) ranges over primitive vectors in a disc whose radius increases, the natural analog of this problem in imaginary quadratic number fields, as well as equidistribution of integral solutions to the diophantine equation defined by an integral Lorentz form in three or more variables. We establish an effective rate of convergence for these equidistribution problems, depending on the size of the spectral gap associated with a suitable lattice subgroup in the isometry group of the relevant hyperbolic space. The main result underlying our discussion amounts to establishing effective joint equidistribution for the horospherical component and the radial component in the Iwasawa decomposition of lattice elements.}, author = {Horesh, Tal and Nevo, Amos}, issn = {1945-5844}, journal = {Pacific Journal of Mathematics}, number = {2}, pages = {265--294}, publisher = {Mathematical Sciences Publishers}, title = {{Horospherical coordinates of lattice points in hyperbolic spaces: Effective counting and equidistribution}}, doi = {10.2140/pjm.2023.324.265}, volume = {324}, year = {2023}, } @article{13091, abstract = {We use a function field version of the Hardy–Littlewood circle method to study the locus of free rational curves on an arbitrary smooth projective hypersurface of sufficiently low degree. On the one hand this allows us to bound the dimension of the singular locus of the moduli space of rational curves on such hypersurfaces and, on the other hand, it sheds light on Peyre’s reformulation of the Batyrev–Manin conjecture in terms of slopes with respect to the tangent bundle.}, author = {Browning, Timothy D and Sawin, Will}, issn = {1944-7833}, journal = {Algebra & Number Theory}, number = {3}, pages = {719--748}, publisher = {Mathematical Sciences Publishers}, title = {{Free rational curves on low degree hypersurfaces and the circle method}}, doi = {10.2140/ant.2023.17.719}, volume = {17}, year = {2023}, } @article{13973, abstract = {We construct families of log K3 surfaces and study the arithmetic of their members. We use this to produce explicit surfaces with an order 5 Brauer–Manin obstruction to the integral Hasse principle.}, author = {Lyczak, Julian}, issn = {0373-0956}, journal = {Annales de l'Institut Fourier}, number = {2}, pages = {447--478}, publisher = {Association des Annales de l'Institut Fourier}, title = {{Order 5 Brauer–Manin obstructions to the integral Hasse principle on log K3 surfaces}}, doi = {10.5802/aif.3529}, volume = {73}, year = {2023}, } @article{12427, abstract = {Let k be a number field and X a smooth, geometrically integral quasi-projective variety over k. For any linear algebraic group G over k and any G-torsor g : Z → X, we observe that if the étale-Brauer obstruction is the only one for strong approximation off a finite set of places S for all twists of Z by elements in H^1(k, G), then the étale-Brauer obstruction is the only one for strong approximation off a finite set of places S for X. As an application, we show that any homogeneous space of the form G/H with G a connected linear algebraic group over k satisfies strong approximation off the infinite places with étale-Brauer obstruction, under some compactness assumptions when k is totally real. We also prove more refined strong approximation results for homogeneous spaces of the form G/H with G semisimple simply connected and H finite, using the theory of torsors and descent.}, author = {Balestrieri, Francesca}, issn = {1088-6826}, journal = {Proceedings of the American Mathematical Society}, number = {3}, pages = {907--914}, publisher = {American Mathematical Society}, title = {{Some remarks on strong approximation and applications to homogeneous spaces of linear algebraic groups}}, doi = {10.1090/proc/15239}, volume = {151}, year = {2023}, } @article{12916, abstract = {We apply a variant of the square-sieve to produce an upper bound for the number of rational points of bounded height on a family of surfaces that admit a fibration over P1 whose general fibre is a hyperelliptic curve. The implied constant does not depend on the coefficients of the polynomial defining the surface. }, author = {Bonolis, Dante and Browning, Timothy D}, issn = {2036-2145}, journal = {Annali della Scuola Normale Superiore di Pisa, Classe di Scienze}, number = {1}, pages = {173--204}, publisher = {Scuola Normale Superiore - Edizioni della Normale}, title = {{Uniform bounds for rational points on hyperelliptic fibrations}}, doi = {10.2422/2036-2145.202010_018}, volume = {24}, year = {2023}, } @article{13180, abstract = {We study the density of everywhere locally soluble diagonal quadric surfaces, parameterised by rational points that lie on a split quadric surface}, author = {Browning, Timothy D and Lyczak, Julian and Sarapin, Roman}, issn = {1944-4184}, journal = {Involve}, number = {2}, pages = {331--342}, publisher = {Mathematical Sciences Publishers}, title = {{Local solubility for a family of quadrics over a split quadric surface}}, doi = {10.2140/involve.2023.16.331}, volume = {16}, year = {2023}, } @article{14717, abstract = {We count primitive lattices of rank d inside Zn as their covolume tends to infinity, with respect to certain parameters of such lattices. These parameters include, for example, the subspace that a lattice spans, namely its projection to the Grassmannian; its homothety class and its equivalence class modulo rescaling and rotation, often referred to as a shape. We add to a prior work of Schmidt by allowing sets in the spaces of parameters that are general enough to conclude the joint equidistribution of these parameters. In addition to the primitive d-lattices Λ themselves, we also consider their orthogonal complements in Zn⁠, A1⁠, and show that the equidistribution occurs jointly for Λ and A1⁠. Finally, our asymptotic formulas for the number of primitive lattices include an explicit bound on the error term.}, author = {Horesh, Tal and Karasik, Yakov}, issn = {1464-3847}, journal = {Quarterly Journal of Mathematics}, number = {4}, pages = {1253--1294}, publisher = {Oxford University Press}, title = {{Equidistribution of primitive lattices in ℝn}}, doi = {10.1093/qmath/haad008}, volume = {74}, year = {2023}, } @article{18179, abstract = {Linnik type problems concern the distribution of projections of integral points on the unit sphere as their norm increases, and different generalizations of this phenomenon. Our work addresses a question of this type: we prove the uniform distribution of the projections of primitive Z2 points in the p-adic unit sphere, as their (real) norm tends to infinity. The proof is via counting lattice points in semi-simple S-arithmetic groups.}, author = {Guilloux, Antonin and Horesh, Tal}, issn = {2592-6616}, journal = {Publications mathématiques de Besançon - Algèbre et Théorie des nombres}, pages = {85--107}, publisher = {Presses Universitaires de Franche-Comté}, title = {{p-adic directions of primitive vectors}}, doi = {10.5802/pmb.50}, volume = {2023}, year = {2023}, }