@inproceedings{17126, abstract = {Functional encryption (FE) is a primitive where the holder of a master secret key can control which functions a user can evaluate on encrypted data. It is a powerful primitive that even implies indistinguishability obfuscation (iO), given sufficiently compact ciphertexts (Ananth-Jain, CRYPTO’15 and Bitansky-Vaikuntanathan, FOCS’15). However, despite being extensively studied, there are FE schemes, such as function-hiding inner-product FE (Bishop-Jain-Kowalczyk, AC’15, Abdalla-Catalano-Fiore-Gay-Ursu, CRYPTO’18) and compact quadratic FE (Baltico-Catalano-Fiore-Gay, Lin, CRYPTO’17), that can be only realized using pairings. This raises the question if there are some mathematical barriers that hinder us from realizing these FE schemes from other assumptions. In this paper, we study the difficulty of constructing lattice-based compact FE. We generalize the impossibility results of Ünal (EC’20) for lattice-based function-hiding FE, and extend it to the case of compact FE. Concretely, we prove lower bounds for lattice-based compact FE schemes which meet some (natural) algebraic restrictions at encryption and decryption, and have ciphertexts of linear size and secret keys of minimal degree. We see our results as important indications of why it is hard to construct lattice-based FE schemes for new functionalities, and which mathematical barriers have to be overcome.}, author = {Tairi, Erkan and Ünal, Akin}, booktitle = {Advances in Cryptology – EUROCRYPT 2024}, isbn = {9783031587221}, issn = {1611-3349}, location = {Zurich, Switzerland}, pages = {249--279}, publisher = {Springer Nature}, title = {{Lower bounds for lattice-based compact functional encryption}}, doi = {10.1007/978-3-031-58723-8_9}, volume = {14652}, year = {2024}, } @article{17128, abstract = {The onset of turbulence in pipe flow has defied detailed understanding ever since the first observations of the spatially heterogeneous nature of the transition. Recent theoretical studies and experiments in simpler, shear-driven flows suggest that the onset of turbulence is a directed-percolation non-equilibrium phase transition, but whether these findings are generic and also apply to open or pressure-driven flows is unknown. In pipe flow, the extremely long time scales near the transition make direct observations of critical behaviour virtually impossible. Here we find a technical solution to that limitation and show that the universality class of the transition is directed percolation, from which a jammed phase of puffs emerges above the critical point. Our method is to experimentally characterize all pairwise interactions between localized patches of turbulence puffs and use these interactions as input for renormalization group and computer simulations of minimal models that extrapolate to long length and time scales. The strong interactions in the jamming regime enable us to explicitly measure the turbulent fraction and confirm model predictions. Our work shows that directed-percolation scaling applies beyond simple closed shear flows and underscores how statistical mechanics can lead to profound, quantitative and predictive insights on turbulent flows and their phases.}, author = {Lemoult, Grégoire M and Vasudevan, Mukund and Shih, Hong Yan and Linga, Gaute and Mathiesen, Joachim and Goldenfeld, Nigel and Hof, Björn}, issn = {1745-2481}, journal = {Nature Physics}, pages = {1339--1345}, publisher = {Springer Nature}, title = {{Directed percolation and puff jamming near the transition to pipe turbulence}}, doi = {10.1038/s41567-024-02513-0}, volume = {20}, year = {2024}, } @phdthesis{17133, abstract = {An ideal quantum computer relies on qubits capable of performing fast gate operations and maintaining strong interconnections while preserving their quantum coherence. Since the inception of experimental eforts toward building a quantum computer, the community has faced challenges in engineering such a system. Among the various methods of implementing a quantum computer, superconducting qubits have shown fast gates close to tens of nanoseconds, with the state-of-the-art reaching a coherence of a few milliseconds. However, achieving simultaneously long lifetimes with fast qubit operations poses an inherent paradox. Qubits with high coherence require isolation from the environment, while fast operation necessitates strong coupling of the qubit. This thesis approaches this issue by proposing the idea of engineering superconducting qubits capable of transitioning between operating in a protected regime, where the qubit is completely isolated from the environment, and coupling to the communication channels as needed. In this direction, we use the geometric superinductor to scan the parameter space of rf-SQUID devices, searching for a regime where we can take the qubit protection to its extreme. This leads us to the inductively shunted transmon (IST) regime, characterized by EJ /EC ≫ 1 and EJ /EL ≫ 1, where the circuit potential exhibits a double well with a large barrier separating the local ground states of each quantum well. In this regime, although it is anticipated that the two quantum wells would be isolated from each other, we observe single fuxon tunneling between them. The interplay of the cavity photons and the fuxon transition forms a rich physical system, containing resonance conditions that allow the preparation of the fuxon ground or excited states. This enables us to study the relaxation rate of such transition and show that it can be as large as 3.6 hours. Dynamically controlling the barrier height between the two quantum wells allows for controllable coupling, which scales exponentially, for a qubit encoded in two fuxon states. The 0-π qubit is one of the very few known superconducting circuit types that ofers exponential protection from both relaxation and dephasing simultaneously. However, this qubit is not exempt from the fact that such protection comes at the expense of complex readout and control. In this thesis, we propose a way to controllably break the circuit symmetry, the key reason for the protection, to momentarily restore the ability to control and manipulate the qubit. An asymmetry in capacitances and inductances in the 0-π circuit is detrimental since they lead to coupling of the protected state to the thermally occupied parasitic mode of the circuit. However, here we try to exploit a controlled asymmetry in Josephson energies and show that this can be used as a tunable coupler between the protected states. In the future, this should allow to perform gate operations by dynamically controlling the asymmetry instead of driving the protected transition with microwave pulses. Therefore, we believe that the proposed method can make the use of protected qubits more practical in experimental realizations of quantum computing.}, author = {Hassani, Farid}, isbn = {978-3-99078-040-4}, issn = {2663-337X}, keywords = {Quantum information, Qubits, Superconducting devices}, pages = {161}, publisher = {Institute of Science and Technology Austria}, title = {{Superconducting qubits capable of dynamic switching between protected and high-speed control regimes}}, doi = {10.15479/at:ista:17133}, year = {2024}, } @unpublished{17136, abstract = {This paper focuses on Majority Dynamics in sparse graphs, in particular, as a tool to study internal cuts. It is known that, in Majority Dynamics on a finite graph, each vertex eventually either comes to a fixed state, or oscillates with period two. The empirical evidence acquired by simulations suggests that for random odd-regular graphs, approximately half of the vertices end up oscillating with high probability. We notice a local symmetry between oscillating and non-oscillating vertices, that potentially can explain why the fraction of the oscillating vertices is concentrated around $\frac{1}{2}$. In our simulations, we observe that the parts of random odd-regular graph under Majority Dynamics with high probability do not contain $\lceil \frac{d}{2} \rceil$-cores at any timestep, and thus, one cannot use Majority Dynamics to prove that internal cuts exist in odd-regular graphs almost surely. However, we suggest a modification of Majority Dynamics, that yields parts with desired cores with high probability.}, author = {Arkhipov, Pavel}, booktitle = {arXiv}, title = {{Majority dynamics and internal partitions of random regular graphs: Experimental results}}, doi = {10.48550/arXiv.2406.07026}, year = {2024}, } @inproceedings{17139, author = {Schlögl, Alois and Khalid, Waleed and Elefante, Stefano and Stadlbauer, Stephan}, booktitle = {ASHPC24 - Austrian-Slovenian HPC Meeting 2024}, isbn = {9783200096455}, location = {Grundlsee, Austria}, pages = {46}, publisher = {EuroCC Austria}, title = {{How much memory per CPU core is requested?}}, doi = {10.25365/phaidra.463}, year = {2024}, } @article{17141, abstract = {The TIR1/AFB–Aux/IAA–ARF canonical auxin signaling pathway is widely accepted to (de)active transcriptional regulation, thus controlling auxin-associated developmental processes. However, the theme of a rapid auxin response has emerged since the 2018 Auxins and Cytokinin in Plant Development conference. To date, a few signaling components have been identified to mediate both slow and rapid auxin responses, which unveils the complexity of auxin signaling.}, author = {Zhang, Zilin and Chen, Huihuang and Peng, Shuaiying and Han, Huibin}, issn = {0022-0957}, journal = {Journal of Experimental Botany}, number = {18}, publisher = {Oxford University Press}, title = {{Slow and rapid auxin responses in Arabidopsis}}, doi = {10.1093/jxb/erae246}, volume = {75}, year = {2024}, } @article{17142, abstract = {Despite the diverse genetic origins of autism spectrum disorders (ASDs), affected individuals share strikingly similar and correlated behavioural traits that include perceptual and sensory processing challenges. Notably, the severity of these sensory symptoms is often predictive of the expression of other autistic traits. However, the origin of these perceptual deficits remains largely elusive. Here, we show a recurrent impairment in visual threat perception that is similarly impaired in 3 independent mouse models of ASD with different molecular aetiologies. Interestingly, this deficit is associated with reduced avoidance of threatening environments—a nonperceptual trait. Focusing on a common cause of ASDs, the Setd5 gene mutation, we define the molecular mechanism. We show that the perceptual impairment is caused by a potassium channel (Kv1)-mediated hypoexcitability in a subcortical node essential for the initiation of escape responses, the dorsal periaqueductal grey (dPAG). Targeted pharmacological Kv1 blockade rescued both perceptual and place avoidance deficits, causally linking seemingly unrelated trait deficits to the dPAG. Furthermore, we show that different molecular mechanisms converge on similar behavioural phenotypes by demonstrating that the autism models Cul3 and Ptchd1, despite having similar behavioural phenotypes, differ in their functional and molecular alteration. Our findings reveal a link between rapid perception controlled by subcortical pathways and appropriate learned interactions with the environment and define a nondevelopmental source of such deficits in ASD.}, author = {Burnett, Laura and Koppensteiner, Peter and Symonova, Olga and Masson, Tomas and Vega Zuniga, Tomas A and Contreras, Ximena and Rülicke, Thomas and Shigemoto, Ryuichi and Novarino, Gaia and Jösch, Maximilian A}, issn = {1545-7885}, journal = {PLoS Biology}, publisher = {Public Library of Science}, title = {{Shared behavioural impairments in visual perception and place avoidance across different autism models are driven by periaqueductal grey hypoexcitability in Setd5 haploinsufficient mice}}, doi = {10.1371/journal.pbio.3002668}, volume = {22}, year = {2024}, } @article{17143, abstract = {This paper deals with local criteria for the convergence to a global minimiser for gradient flow trajectories and their discretisations. To obtain quantitative estimates on the speed of convergence, we consider variations on the classical Kurdyka–Łojasiewicz inequality for a large class of parameter functions. Our assumptions are given in terms of the initial data, without any reference to an equilibrium point. The main results are convergence statements for gradient flow curves and proximal point sequences to a global minimiser, together with sharp quantitative estimates on the speed of convergence. These convergence results apply in the general setting of lower semicontinuous functionals on complete metric spaces, generalising recent results for smooth functionals on Rn. While the non-smooth setting covers very general spaces, it is also useful for (non)-smooth functionals on Rn. .}, author = {Dello Schiavo, Lorenzo and Maas, Jan and Pedrotti, Francesco}, issn = {1088-6850}, journal = {Transactions of the American Mathematical Society}, number = {6}, pages = {3779--3804}, publisher = {American Mathematical Society}, title = {{Local conditions for global convergence of gradient flows and proximal point sequences in metric spaces}}, doi = {10.1090/tran/9156}, volume = {377}, year = {2024}, } @inproceedings{17144, abstract = {We prove that the medial axis of closed sets is Hausdorff stable in the following sense: Let 𝒮 ⊆ ℝ^d be a fixed closed set that contains a bounding sphere. That is, the bounding sphere is part of the set 𝒮. Consider the space of C^{1,1} diffeomorphisms of ℝ^d to itself, which keep the bounding sphere invariant. The map from this space of diffeomorphisms (endowed with a Banach norm) to the space of closed subsets of ℝ^d (endowed with the Hausdorff distance), mapping a diffeomorphism F to the closure of the medial axis of F(𝒮), is Lipschitz. This extends a previous stability result of Chazal and Soufflet on the stability of the medial axis of C² manifolds under C² ambient diffeomorphisms.}, author = {Kourimska, Hana and Lieutier, André and Wintraecken, Mathijs}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{The medial axis of any closed bounded set Is Lipschitz stable with respect to the Hausdorff distance Under ambient diffeomorphisms}}, doi = {10.4230/LIPIcs.SoCG.2024.69}, volume = {293}, year = {2024}, } @inproceedings{17145, abstract = {Grid peeling is the process of repeatedly removing the convex hull vertices of the grid points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the affine curve-shortening flow, which deforms the curve based on the curvature. We prove this conjecture for one class of curves, parabolas with a vertical axis, and we determine the value of the constant factor in the formula that relates the two processes.}, author = {Rote, Günter and Rüber, Moritz and Saghafian, Morteza}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Grid peeling of parabolas}}, doi = {10.4230/LIPIcs.SoCG.2024.76}, volume = {293}, year = {2024}, } @article{17154, abstract = {We compute the deterministic approximation for mixed fluctuation moments of products of deterministic matrices and general Sobolev functions of Wigner matrices. Restricting to polynomials, our formulas reproduce recent results of Male et al. (Random Matrices Theory Appl. 11(2):2250015, 2022), showing that the underlying combinatorics of non-crossing partitions and annular non-crossing permutations continue to stay valid beyond the setting of second-order free probability theory. The formulas obtained further characterize the variance in the functional central limit theorem given in the recent companion paper (Reker in Preprint, arXiv:2204.03419, 2023). and thus allow identifying the fluctuation around the thermal value in certain thermalization problems.}, author = {Reker, Jana}, issn = {1572-9656}, journal = {Mathematical Physics, Analysis and Geometry}, number = {3}, publisher = {Springer Nature}, title = {{Fluctuation moments for regular functions of Wigner Matrices}}, doi = {10.1007/s11040-024-09483-y}, volume = {27}, year = {2024}, } @phdthesis{17156, abstract = {This dissertation is the summary of the author’s work, concerning the relations between cohomology rings of algebraic varieties and rings of functions on zero schemes and fixed point schemes. For most of the thesis, the focus is on smooth complex varieties with an action of a principally paired group, e.g. a parabolic subgroup of a reductive group. The fundamental theorem 5.2.11 from co-authored article [66] says that if the principal nilpotent has a unique zero, then the zero scheme over the Kostant section is isomorphic to the spectrum of the equivariant cohomology ring, remembering the grading in terms of a C^* action. A similar statement is proved also for the G-invariant functions on the total zero scheme over the whole Lie algebra. Additionally, we are able to prove an analogous result for the GKM spaces, which poses the question on a joint generalisation. We also tackle the situation of a singular variety. As long as it is embedded in a smooth variety with regular action, we are able to study its cohomology as well by means of the zero scheme. In case of e.g. Schubert varieties this determines the cohomology ring completely. In largest generality, this allows us to see a significant part of the cohomology ring. We also show (Theorem 6.2.1) that the cohomology ring of spherical varieties appears as the ring of functions on the zero scheme. The computational aspect is not easy, but one can hope that this can bring some concrete information about such cohomology rings. Lastly, the K-theory conjecture 6.3.1 is studied, with some results attained for GKM spaces. The thesis includes also an introduction to group actions on algebraic varieties. In particular, the vector fields associated to the actions are extensively studied. We also provide a version of the Kostant section for arbitrary principally paired group, which parametrises the regular orbits in the Lie algebra of an algebraic group. Before proving the main theorem, we also include a historical overview of the field. In particular we bring together the results of Akyildiz, Carrell and Lieberman on non-equivariant cohomology rings.}, author = {Rychlewicz, Kamil P}, issn = {2663-337X}, keywords = {equivariant cohomology, zero schemes, algebraic groups, Lie algebras}, pages = {117}, publisher = {Institute of Science and Technology Austria}, title = {{Equivariant cohomology and rings of functions}}, doi = {10.15479/at:ista:17156}, year = {2024}, } @article{17161, abstract = {Dynamic processes in molecules can occur on a wide range of timescales, and it is important to understand which timescales of motion contribute to different parameters used in dynamics measurements. For spin relaxation, this can easily be understood from the sampling frequencies of the spectral-density function by different relaxation-rate constants. In addition to data from relaxation measurements, determining dynamically averaged anisotropic interactions in magic-angle spinning (MAS) solid-state NMR allows for better quantification of the amplitude of molecular motion. For partially averaged anisotropic interactions, the relevant timescales of motion are not so clearly defined. Whether the averaging depends on the experimental methods (e.g., pulse sequences) or conditions (e.g., MAS frequency, magnitude of anisotropic interaction, radio-frequency field amplitudes) is not fully understood. To investigate these questions, we performed numerical simulations of dynamic systems based on the stochastic Liouville equation using several experiments for recoupling the dipolar coupling, chemical-shift anisotropy or quadrupolar coupling. As described in the literature, the transition between slow motion, where parameters characterizing the anisotropic interaction are not averaged, and fast motion, where the tensors are averaged leading to a scaled anisotropic quantity, occurs over a window of motional rate constants that depends mainly on the strength of the interaction. This transition region can span 2 orders of magnitude in exchange-rate constants (typically in the microsecond range) but depends only marginally on the employed recoupling scheme or sample spinning frequency. The transition region often coincides with a fast relaxation of coherences, making precise quantitative measurements difficult. Residual couplings in off-magic-angle experiments, however, average over longer timescales of motion. While in principle one may gain information on the timescales of motion from the transition area, extracting such information is hampered by low signal-to-noise ratio in experimental spectra due to fast relaxation that occurs in the same region.}, author = {Aebischer, Kathrin and Becker, Lea Marie and Schanda, Paul and Ernst, Matthias}, issn = {2699-0016}, journal = {Magnetic Resonance}, number = {1}, pages = {69--86}, publisher = {Copernicus Publications}, title = {{Evaluating the motional timescales contributing to averaged anisotropic interactions in MAS solid-state NMR}}, doi = {10.5194/mr-5-69-2024}, volume = {5}, year = {2024}, } @article{17162, abstract = {Cost analysis, also known as resource usage analysis, is the task of finding bounds on the total cost of a program and is a well-studied problem in static analysis. In this work, we consider two classical quantitative problems in cost analysis for probabilistic programs. The first problem is to find a bound on the expected total cost of the program. This is a natural measure for the resource usage of the program and can also be directly applied to average-case runtime analysis. The second problem asks for a tail bound, i.e. ‍given a threshold t the goal is to find a probability bound p such that ℙ[total cost ≥ t] ≤ p. Intuitively, given a threshold t on the resource, the problem is to find the likelihood that the total cost exceeds this threshold. First, for expectation bounds, a major obstacle in previous works on cost analysis is that they can handle only non-negative costs or bounded variable updates. In contrast, we provide a new variant of the standard notion of cost martingales, that allows us to find expectation bounds for a class of programs with general positive or negative costs and no restriction on the variable updates. More specifically, our approach is applicable as long as there is a lower bound on the total cost incurred along every path. Second, for tail bounds, all previous methods are limited to programs in which the expected total cost is finite. In contrast, we present a novel approach, based on a combination of our martingale-based method for expectation bounds with a quantitative safety analysis, to obtain a solution to the tail bound problem that is applicable even to programs with infinite expected cost. Specifically, this allows us to obtain runtime tail bounds for programs that do not terminate almost-surely. In summary, we provide a novel combination of martingale-based cost analysis and quantitative safety analysis that is able to find expectation and tail cost bounds for probabilistic programs, without the restrictions of non-negative costs, bounded updates, or finiteness of the expected total cost. Finally, we provide experimental results showcasing that our approach can solve instances that were beyond the reach of previous methods.}, author = {Chatterjee, Krishnendu and Goharshady, Amir Kafshdar and Meggendorfer, Tobias and Zikelic, Dorde}, issn = {2475-1421}, journal = {Proceedings of the ACM on Programming Languages}, number = {OOPSLA1}, publisher = {Association for Computing Machinery}, title = {{Quantitative bounds on resource usage of probabilistic programs}}, doi = {10.1145/3649824}, volume = {8}, year = {2024}, } @phdthesis{17164, abstract = {This thesis is structured into two parts. In the first part, we consider the random variable X := Tr(f1(W)A1 . . . fk(W)Ak) where W is an N × N Hermitian Wigner matrix, k ∈ N, and we choose (possibly N-dependent) regular functions f1, . . . , fk as well as bounded deterministic matrices A1, . . . , Ak. In this context, we prove a functional central limit theorem on macroscopic and mesoscopic scales, showing that the fluctuations of X around its expectation are Gaussian and that the limiting covariance structure is given by a deterministic recursion. We further give explicit error bounds in terms of the scaling of f1, . . . , fk and the number of traceless matrices among A1, . . . , Ak, thus extending the results of Cipolloni, Erdős and Schröder [40] to products of arbitrary length k ≥ 2. Analyzing the underlying combinatorics leads to a non-recursive formula for the variance of X as well as the covariance of X and Y := Tr(fk+1(W)Ak+1 . . . fk+ℓ(W)Ak+ℓ) of similar build. When restricted to polynomials, these formulas reproduce recent results of Male, Mingo, Peché, and Speicher [107], showing that the underlying combinatorics of noncrossing partitions and annular non-crossing permutations continue to stay valid beyond the setting of second-order free probability theory. As an application, we consider the fluctuation of Tr(eitW A1e −itW A2)/N around its thermal value Tr(A1) Tr(A2)/N2 when t is large and give an explicit formula for the variance. The second part of the thesis collects three smaller projects focusing on different random matrix models. In the first project, we show that a class of weakly perturbed Hamiltonians of the form Hλ = H0 + λW, where W is a Wigner matrix, exhibits prethermalization. That is, the time evolution generated by Hλ relaxes to its ultimate thermal state via an intermediate prethermal state with a lifetime of order λ −2 . As the main result, we obtain a general relaxation formula, expressing the perturbed dynamics via the unperturbed dynamics and the ultimate thermal state. The proof relies on a two-resolvent global law for the deformed Wigner matrix Hλ. The second project focuses on correlated random matrices, more precisely on a correlated N × N Hermitian random matrix with a polynomially decaying metric correlation structure. A trivial a priori bound shows that the operator norm of this model is stochastically dominated by √ N. However, by calculating the trace of the moments of the matrix and using the summable decay of the cumulants, the norm estimate can be improved to a bound of order one. In the third project, we consider a multiplicative perturbation of the form UA(t) where U is a unitary random matrix and A = diag(t, 1, ..., 1). This so-called UA model was first introduced by Fyodorov [73] for its applications in scattering theory. We give a general description of the eigenvalue trajectories obtained by varying the parameter t and introduce a flow of deterministic domains that separates the outlier resulting from the rank-one perturbation from the typical eigenvalues for all sub-critical timescales. The results are obtained under generic assumptions on U that hold for various unitary random matrices, including the circular unitary ensemble (CUE) in the original formulation of the model.}, author = {Reker, Jana}, issn = {2663-337X}, keywords = {Random Matrices, Spectrum, Central Limit Theorem, Resolvent, Free Probability}, pages = {206}, publisher = {Institute of Science and Technology Austria}, title = {{Central limit theorems for random matrices: From resolvents to free probability}}, doi = {10.15479/at:ista:17164}, year = {2024}, } @inproceedings{17170, abstract = {In this article we extend and strengthen the seminal work by Niyogi, Smale, and Weinberger on the learning of the homotopy type from a sample of an underlying space. In their work, Niyogi, Smale, and Weinberger studied samples of C² manifolds with positive reach embedded in ℝ^d. We extend their results in the following ways: - As the ambient space we consider both ℝ^d and Riemannian manifolds with lower bounded sectional curvature. - In both types of ambient spaces, we study sets of positive reach - a significantly more general setting than C² manifolds - as well as general manifolds of positive reach. - The sample P of a set (or a manifold) 𝒮 of positive reach may be noisy. We work with two one-sided Hausdorff distances - ε and δ - between P and 𝒮. We provide tight bounds in terms of ε and δ, that guarantee that there exists a parameter r such that the union of balls of radius r centred at the sample P deformation-retracts to 𝒮. We exhibit their tightness by an explicit construction. We carefully distinguish the roles of δ and ε. This is not only essential to achieve tight bounds, but also sensible in practical situations, since it allows one to adapt the bound according to sample density and the amount of noise present in the sample separately.}, author = {Attali, Dominique and Kourimska, Hana and Fillmore, Christopher D and Ghosh, Ishika and Lieutier, André and Stephenson, Elizabeth R and Wintraecken, Mathijs}, booktitle = {40th International Symposium on Computational Geometry}, isbn = {9783959773164}, issn = {1868-8969}, location = {Athens, Greece}, pages = {11:1--11:19}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of euclidean spaces and of Riemannian manifolds}}, doi = {10.4230/LIPIcs.SoCG.2024.11}, volume = {293}, year = {2024}, } @article{17187, abstract = {The generation of diverse cell types during development is fundamental to brain functions. We outline a protocol to quantitatively assess the clonal output of individual neural progenitors using mosaic analysis with double markers (MADM) in mice. We first describe steps to acquire and reconstruct adult MADM clones in the superior colliculus. Then we detail analysis pipelines to determine clonal composition and architecture. This protocol enables the buildup of quantitative frameworks of lineage progression with precise spatial resolution in the brain. For complete details on the use and execution of this protocol, please refer to Cheung et al.1}, author = {Cheung, Giselle T and Streicher, Carmen and Hippenmeyer, Simon}, issn = {2666-1667}, journal = {STAR Protocols}, number = {3}, publisher = {Elsevier}, title = {{Protocol for quantitative reconstruction of cell lineage using mosaic analysis with double markers in mice}}, doi = {10.1016/j.xpro.2024.103157}, volume = {5}, year = {2024}, } @article{17188, abstract = {In a delegation problem, a principal P with commitment power tries to pick one out of 𝑛 options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a Θ(1∕𝑛)-approximation and extend this result to ratios of Θ(𝑘∕𝑛) in case (1) A has a lookahead of 𝑘 rounds, or (2) A can propose up to 𝑘 different options. We provide fine-grained bounds independent of 𝑛 based on three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor 𝛼, we obtain an Ω(loglog 𝛼∕ log 𝛼)- approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1∕𝛼 cannot be avoided. If there are at most 𝛽 different utility values for A, we show a Θ(1∕𝛽)-approximation. If the utilities of P and A for each option are related by a factor 𝛾, we obtain an Ω(1∕ log 𝛾)- approximation, where 𝑂(log log 𝛾∕ log 𝛾) is best possible.}, author = {Braun, Pirmin and Hahn, Niklas and Hoefer, Martin and Schecker, Conrad}, issn = {0004-3702}, journal = {Artificial Intelligence}, publisher = {Elsevier}, title = {{Delegated online search}}, doi = {10.1016/j.artint.2024.104171}, volume = {334}, year = {2024}, } @article{17189, abstract = {Supergranules, which are solar flow features with a lateral scale of 30,000–40,000 km and a lifetime of ~24 h, form a prominent component of the Sun’s convective spectrum. However, their internal flows, which can be probed only by helioseismology, are not well understood. We analyse dopplergrams recorded by the Solar Dynamics Observatory satellite to identify and characterize ~23,000 supergranules. We find that the vertical flows peak at a depth of ~10,000 km, and remain invariant over the full range of lateral supergranular scales, contrary to numerical predictions. We also infer that, within the local seismic resolution (≳5,000 km), downflows are ~40% weaker than upflows, indicating an apparent mass-flux imbalance. This may imply that the descending flows also comprise plumes, which maintain the mass balance but are simply too small to be detected by seismic waves. These results challenge the widely used mixing-length description of solar convection.}, author = {Hanson, Chris S. and Das, Srijan B and Mani, Prasad and Hanasoge, Shravan and Sreenivasan, Katepalli R.}, issn = {2397-3366}, journal = {Nature Astronomy}, pages = {1088--1101}, publisher = {Springer Nature}, title = {{Supergranular-scale solar convection not explained by mixing-length theory}}, doi = {10.1038/s41550-024-02304-w}, volume = {8}, year = {2024}, } @article{17190, abstract = {For a locally finite set, 𝐴⊆ℝ𝑑 , the 𝑘 th Brillouin zone of 𝑎∈𝐴 is the region of points 𝑥∈ℝ𝑑 for which ‖𝑥−𝑎‖ is the 𝑘 th smallest among the Euclidean distances between 𝑥 and the points in 𝐴 . If 𝐴 is a lattice, the 𝑘 th Brillouin zones of the points in 𝐴 are translates of each other, and together they tile space. Depending on the value of 𝑘 , they express medium- or long-range order in the set. We study fundamental geometric and combinatorial properties of Brillouin zones, focusing on the integer lattice and its perturbations. Our results include the stability of a Brillouin zone under perturbations, a linear upper bound on the number of chambers in a zone for lattices in ℝ2 , and the convergence of the maximum volume of a chamber to zero for the integer lattice.}, author = {Edelsbrunner, Herbert and Garber, Alexey and Ghafaris, Mohadese and Heiss, Teresa and Saghafiant, Morteza and Wintraecken, Mathijs}, issn = {0895-4801}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, pages = {1784--1807}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Brillouin zones of integer lattices and their perturbations}}, doi = {10.1137/22M1489071}, volume = {38}, year = {2024}, }