IST Austria: PubRep (Institute of Science and Technology)
Not a member yet
6140 research outputs found
Sort by
Monitoring robustness and individual fairness
No full textIn automated decision-making, it is desirable that outputs of decision-makers be robust to slight perturbations in their inputs, a property that may be called input-output robustness. Input-output robustness appears in various different forms in the literature, such as robustness of AI models to adversarial or semantic perturbations and individual fairness of AI models that make decisions about humans. We propose runtime monitoring of input-output robustness of deployed, black-box AI models, where the goal is to design monitors that would observe one long execution sequence of the model, and would raise an alarm whenever it is detected that two similar inputs from the past led to dissimilar outputs. This way, monitoring will complement existing offline ''robustification'' approaches to increase the trustworthiness of AI decision-makers. We show that the monitoring problem can be cast as the fixed-radius nearest neighbor (FRNN) search problem, which, despite being well-studied, lacks suitable online solutions. We present our tool Clemont, which offers a number of lightweight monitors, some of which use upgraded online variants of existing FRNN algorithms, and one uses a novel algorithm based on binary decision diagrams--a data-structure commonly used in software and hardware verification. We have also developed an efficient parallelization technique that can substantially cut down the computation time of monitors for which the distance between input-output pairs is measured using the L∞norm. Using standard benchmarks from the literature of adversarial and semantic robustness and individual fairness, we perform a comparative study of different monitors in Clemont, and demonstrate their effectiveness in correctly detecting robustness violations at runtime
The relationship between sexual dimorphism and intersex correlation: Do models support intuition?
No full textThe evolution of sexual dimorphism (the difference in average trait values between females and males, SD), is often thought to be constrained by shared genetic architecture between the sexes. Indeed, it is commonly expected that SD should negatively correlate with the intersex correlation (the genetic correlation between effects of segregating variants in females and males, r fm), either because (1) traits with ancestrally low r fm are less constrained in their ability to respond to sex-specific selection and thus evolve to be more dimorphic, or because (2) sex-specific selection, driving sexual dimorphism evolution, also acts to reduce r fm. Despite the intuitive appeal and prominence of these ideas, their generality and the conditions in which they hold remain unclear. Here, we develop models incorporating sex-specific stabilizing selection, mutation and genetic drift to examine the relationship between r fm and SD. We show that the two commonly-discussed mechanisms with the potential to generate a negative correlation between SD and r fm could just as easily generate a positive association, since the standard line of reasoning hinges on a hidden assumption that sex-specific adaptation more frequently favors increased dimorphism than reduced dimorphism. Our results provide, to our knowledge, the first mechanistic framework for understanding the conditions under which a correlation between r fm and SD may arise and offer a compelling explanation for inconsistent empirical evidence. We also make the intriguing observation that—even when selection between the two sexes is identical—drift generates nonzero SD. We quantify this effect and discuss its significance
Divisibility sequences related to abelian varieties isogenous to a power of an elliptic curve
No full textLet A be an abelian variety defined over a number field K, E/K be an elliptic curve, and ϕ : A → Em be an isogeny defined over K. Let P ∈ A(K) be such that ϕ(P)=(Q1,..., Qm) with RankZ(⟨Q1,...,Qm⟩)=1. We will study a divisibility sequence related to the point P and show its relation with elliptic divisibility sequences
A central limit theorem for the matching number of a sparse random graph
No full textIn 1981, Karp and Sipser proved a law of large numbers for the matching number of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called differential equation method for analysis of random graph processes. Strengthening this classical result, and answering a question of Aronson, Frieze and Pittel, we prove a central limit theorem in the same setting: the fluctuations in the matching number of a sparse random graph are asymptotically Gaussian. Our new contribution is to prove this central limit theorem in the subcritical and critical regimes, according to a celebrated algorithmic phase transition first observed by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation of the differential equation method (comparing the so-called Karp–Sipser process to a system of stochastic differential equations). Our proof builds on these methods, and introduces new techniques to handle certain degeneracies present in the subcritical and critical cases. Curiously, our new techniques lead to a non-constructive result: we are able to characterise the fluctuations of the matching number around its mean, despite these fluctuations being much smaller than the error terms in our best estimates of the mean. We also prove a central limit theorem for the rank of the adjacency matrix of a sparse random graph
The convergence of heavy and light seeds to overmassive black holes at cosmic dawn
No full textThe James Webb Space Telescope has revealed low-luminosity active galactic nuclei at redshifts of z ≳ 4–7, many of which host accreting massive black holes (BHs) with BH-to-galaxy mass (MBH/M⋆) ratios exceeding the local values by more than an order of magnitude. The origin of these overmassive BHs remains unclear but requires potential contributions from heavy seeds and/or episodes of super-Eddington accretion. We present a growth model coupled with dark matter halo assembly to explore the evolution of the MBH/M⋆ ratio under different seeding and feedback scenarios. Given the gas inflow rates in protogalaxies, BHs grow episodically at moderate super-Eddington rates, and the mass ratio increases early on, despite significant mass loss through feedback. Regardless of seeding mechanisms, the mass ratio converges to a universal value ∼0.1–0.3, set by the balance between gas feeding and star formation efficiency in the nucleus. This behavior defines an attractor in the MBH–M⋆ diagram, where overmassive BHs grow more slowly than their hosts, while undermassive seeds experience rapid growth before aligning with the attractor. We derive an analytical expression for the universal mass ratio, linking it to feedback strength and halo growth. The convergence of evolutionary tracks erases seeding information from the mass ratio by z ∼ 4–6. Detecting BHs with ∼105−6 M⊙ at higher redshifts that deviate from the convergence trend would provide key diagnostics of their birth conditions
Linear equations with min and max operators: Computational complexity
No full textWe consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition; and (C4) the only min or only max operator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions
Neuroendocrine control of synaptic transmission by PHAC-1 in C. elegans
No full textA dynamic interplay between fast synaptic signals and slower neuromodulatory signals controls the excitatory/inhibitory (E/I) balance within neuronal circuits. The mechanisms by which neuropeptide signaling is regulated to maintain E/I balance remain uncertain. We designed a genetic screen to isolate genes involved in the peptidergic maintenance of the E/I balance in the C. elegans motor circuit. This screen identified the C. elegans orthologs of the presynaptic phosphoprotein synapsin (snn-1) and the protein phosphatase 1 (PP1) regulatory subunit PHACTR1 (phac-1). We demonstrate that both phac-1 and snn-1 alter the motor behavior of C. elegans, and genetic interactions suggest that SNN-1 contributes to PP1-PHAC-1 holoenzyme signaling. De novo variants of human PHACTR1, associated with early-onset epilepsies [developmental and epileptic encephalopathy 70 (DEE70)], when expressed in C. elegans resulted in constitutive PP1-PHAC-1 holoenzyme activity. Unregulated PP1-PHAC-1 signaling alters the synapsin and actin cytoskeleton and increases neuropeptide release by cholinergic motor neurons, which secondarily affects the presynaptic vesicle cycle. Together, these results clarify the dominant mechanisms of action of the DEE70 alleles and suggest that altered neuropeptide release may alter E/I balance in DEE70
LNCS
No full textQuantitative automata model beyond-boolean aspects of systems: every execution is mapped to a real number by incorporating weighted transitions and value functions that generalize acceptance conditions of boolean w-automata. Despite the theoretical advances in systems analysis through quantitative automata, the first comprehensive software tool for quantitative automata (Quantitative Automata Kit, or QuAK) was developed only recently. QuAK implements algorithms for solving standard decision problems, e.g., emptiness and universality, as well as constructions for safety and liveness of quantitative automata. We present the architecture of QuAK, which reflects that all of these problems reduce to either checking inclusion between two quantitative automata or computing the highest value achievable by an automaton—its so-called top value. We improve QuAK by extending these two algorithms with an option to return, alongside their results, an ultimately periodic word witnessing the algorithm’s output, as well as implementing a new safety-liveness decomposition algorithm that can handle nondeterministic automata, making QuAK more informative and capable
Early indirect neurogenesis transitions to late direct neurogenesis in mouse cerebral cortex development
No full textThe cerebral cortex must contain the appropriate numbers of neurons in each layer to acquire its proper functional organization. Accordingly, neurogenesis requires precise regulation along development. Cortical neurons are made either directly by Radial Glia Cells (RGCs) that self- consume, or indirectly from RGCs via Intermediate Progenitor Cells (IPCs) and largely preserving the RGC pool. According to the standing model of cortical development, Direct Neurogenesis predominates at early stages of development, and progressively shifts to Indirect Neurogenesis, which predominates at late stages. However, neurogenesis at early stages should be compatible with RGC amplification, and neurogenesis at late stages needs to involve RGC consumption, which seems in conflict with the standing model. Here we studied the modes of neurogenesis along cortical development using multiple approaches, including birthdating, live imaging and MADM clone labeling. Contrary to the established dogma, our data show that Indirect Neurogenesis clearly predominates at early developmental stages, gradually shifting to Direct Neurogenesis at late stages. These findings challenge the current model of cortical neurogenesis, and prompt a re-evaluation of previous and ongoing work about the genetic and molecular mechanisms regulating this process
LNCS
No full textA verifiable delay function VDF(x, T)->(y, π) maps an input x and time parameter T to an output y together with an efficiently verifiable proof π certifying that y was correctly computed. The function runs in T sequential steps, and it should not be possible to compute y much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., y = x^2^T. There are two constructions for the proof of exponentiation (PoE) certifying that y = x^2^T, with Wesolowski (Eurocrypt’19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS’19).
A recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt’22) are short-lived proofs and signatures, which are proofs and signatures that are only sound for some time t, but after that can be forged by anyone. For this they rely on “watermarkable VDFs”, where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on “zero-knowledge VDFs”, where instead of the output y, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski’s PoE, for the watermarkable VDFs there’s currently no security proof.
In this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al.’s construction in several dimensions (faster forging times, arguably weaker assumptions).
A key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for y = x^2^T, but instead give a (watermarked or zk) proof for the more basic statement that
x^l, y^l satisfy x^l = x ^r, y^l = y^r for some r, together with a normal PoE for y^l = (x^l)^2^T