IST PubRep
Not a member yet
752 research outputs found
Sort by
Bounding Helly numbers via Betti numbers
Get PDFWe show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest
On computability and triviality of well groups
Get PDFThe concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status
Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs
Get PDFWe consider the core algorithmic problems related to verification of systems with respect
to three classical quantitative properties, namely, the mean-payoff property, the ratio
property, and the minimum initial credit for energy property.
The algorithmic problem given a graph and a quantitative property asks to compute the
optimal value (the infimum value over all traces) from every node of the graph.
We consider graphs with constant treewidth, and it is well-known that the control-flow graphs
of most programs have constant treewidth.
Let denote the number of nodes of a graph, the number of edges (for constant treewidth
graphs ) and the largest absolute value of the weights.
Our main theoretical results are as follows.
First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value
within a multiplicative factor of in time
and linear space, as compared to the classical algorithms that require quadratic time.
Second, for the ratio property we present an algorithm that for constant treewidth graphs
works in time , when the output is , as compared to the previously best known algorithm
with running time .
Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in time and the associated decision problem
can be solved in time, improving the previous known and bounds, respectively; and
(ii)~for constant treewidth graphs we present an algorithm that requires time, improving the previous known
bound.
We have implemented some of our algorithms and show that they present a significant speedup
on standard benchmarks
Reconstructing robust phylogenies of metastatic cancers
Get PDFA comprehensive understanding of the clonal evolution of cancer is critical for understanding neoplasia. Genome-wide sequencing data enables evolutionary studies at unprecedented depth. However, classical phylogenetic methods often struggle with noisy sequencing data of impure DNA samples and fail to detect subclones that have different evolutionary trajectories. We have developed a tool, called Treeomics, that allows us to reconstruct the phylogeny of a cancer with commonly available sequencing technologies. Using Bayesian inference and Integer Linear Programming, robust phylogenies consistent with the biological processes underlying cancer evolution were obtained for pancreatic, ovarian, and prostate cancers. Furthermore, Treeomics correctly identified sequencing artifacts such as those resulting from low statistical power; nearly 7% of variants were misclassified by conventional statistical methods. These artifacts can skew phylogenies by creating illusory tumor heterogeneity among distinct samples. Importantly, we show that the evolutionary trees generated with Treeomics are mathematically optimal
Single-cell screening of photosynthetic growth and lactate production by cyanobacteria
No full textBackground
Photosynthetic cyanobacteria are attractive for a range of biotechnological applications including biofuel production. However, due to slow growth, screening of mutant libraries using microtiter plates is not feasible.
Results
We present a method for high-throughput, single-cell analysis and sorting of genetically engineered l-lactate-producing strains of Synechocystis sp. PCC6803. A microfluidic device is used to encapsulate single cells in picoliter droplets, assay the droplets for l-lactate production, and sort strains with high productivity. We demonstrate the separation of low- and high-producing reference strains, as well as enrichment of a more productive l-lactate-synthesizing population after UV-induced mutagenesis. The droplet platform also revealed population heterogeneity in photosynthetic growth and lactate production, as well as the presence of metabolically stalled cells.
Conclusions
The workflow will facilitate metabolic engineering and directed evolution studies and will be useful in studies of cyanobacteria biochemistry and physiology
Nanoscale distribution of presynaptic Ca2+ channels and its impact on vesicular release during development
No full textSynaptic efficacy and precision are influenced by the coupling of voltage-gated Ca2+ channels (VGCCs) to vesicles. But because the topography of VGCCs and their proximity to vesicles is unknown, a quantitative understanding of the determinants of vesicular release at nanometer scale is lacking. To investigate this, we combined freeze-fracture replica immunogold labeling of Cav2.1 channels, local [Ca2+] imaging, and patch pipette perfusion of EGTA at the calyx of Held. Between postnatal day 7 and 21, VGCCs formed variable sized clusters and vesicular release became less sensitive to EGTA, whereas fixed Ca2+ buffer properties remained constant. Experimentally constrained reaction-diffusion simulations suggest that Ca2+ sensors for vesicular release are located at the perimeter of VGCC clusters (<30nm) and predict that VGCC number per cluster determines vesicular release probability without altering release time course. This "perimeter release model" provides a unifying framework accounting for developmental changes in both synaptic efficacy and time course
A quasipolynomial reduction for generalized selective decryption on trees
Get PDFGeneralized Selective Decryption (GSD), introduced by Panjwani [TCC’07], is a game for a symmetric encryption scheme Enc that captures the difficulty of proving adaptive security of certain protocols, most notably the Logical Key Hierarchy (LKH) multicast encryption protocol. In the GSD game there are n keys k1,..., kn, which the adversary may adaptively corrupt (learn); moreover, it can ask for encryptions Encki (kj) of keys under other keys. The adversary’s task is to distinguish keys (which it cannot trivially compute) from random. Proving the hardness of GSD assuming only IND-CPA security of Enc is surprisingly hard. Using “complexity leveraging” loses a factor exponential in n, which makes the proof practically meaningless. We can think of the GSD game as building a graph on n vertices, where we add an edge i → j when the adversary asks for an encryption of kj under ki. If restricted to graphs of depth ℓ, Panjwani gave a reduction that loses only a factor exponential in ℓ (not n). To date, this is the only non-trivial result known for GSD. In this paper we give almost-polynomial reductions for large classes of graphs. Most importantly, we prove the security of the GSD game restricted to trees losing only a quasi-polynomial factor n3 log n+5. Trees are an important special case capturing real-world protocols like the LKH protocol. Our new bound improves upon Panjwani’s on some LKH variants proposed in the literature where the underlying tree is not balanced. Our proof builds on ideas from the “nested hybrids” technique recently introduced by Fuchsbauer et al. [Asiacrypt’14] for proving the adaptive security of constrained PRFs
Generic security of NMAC and HMAC with input whitening
Get PDFHMAC and its variant NMAC are the most popular approaches to deriving a MAC (and more generally, a PRF) from a cryptographic hash function. Despite nearly two decades of research, their exact security still remains far from understood in many different contexts. Indeed, recent works have re-surfaced interest for {\em generic} attacks, i.e., attacks that treat the compression function of the underlying hash function as a black box.
Generic security can be proved in a model where the underlying compression function is modeled as a random function -- yet, to date, the question of proving tight, non-trivial bounds on the generic security of HMAC/NMAC even as a PRF remains a challenging open question.
In this paper, we ask the question of whether a small modification to HMAC and NMAC can allow us to exactly characterize the security of the resulting constructions, while only incurring little penalty with respect to efficiency. To this end, we present simple variants of NMAC and HMAC, for which we prove tight bounds on the generic PRF security, expressed in terms of numbers of construction and compression function queries necessary to break the construction. All of our constructions are obtained via a (near) {\em black-box} modification of NMAC and HMAC, which can be interpreted as an initial step of key-dependent message pre-processing.
While our focus is on PRF security, a further attractive feature of our new constructions is that they clearly defeat all recent generic attacks against properties such as state recovery and universal forgery. These exploit properties of the so-called ``functional graph'' which are not directly accessible in our new constructions
Excitement about inhibitory presynaptic terminals
Get PDFBased on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression. Based on extrapolation from excitatory synapses, it is often assumed that depletion of the releasable pool of synaptic vesicles is the main factor underlying depression at inhibitory synapses. In this issue of Neuron, using subcellular patch-clamp recording from inhibitory presynaptic terminals, Kawaguchi and Sakaba (2015) show that at Purkinje cell-deep cerebellar nuclei neuron synapses, changes in presynaptic action potential waveform substantially contribute to synaptic depression
Systematic discovery of drug interaction mechanisms
No full textAbstract Drug combinations are increasingly important in disease treatments, for combating drug resistance, and for elucidating fundamental relationships in cell physiology. When drugs are combined, their individual effects on cells may be amplified or weakened. Such drug interactions are crucial for treatment efficacy, but their underlying mechanisms remain largely unknown. To uncover the causes of drug interactions, we developed a systematic approach based on precise quantification of the individual and joint effects of antibiotics on growth of genome-wide Escherichia coli gene deletion strains. We found that drug interactions between antibiotics representing the main modes of action are highly robust to genetic perturbation. This robustness is encapsulated in a general principle of bacterial growth, which enables the quantitative prediction of mutant growth rates under drug combinations. Rare violations of this principle exposed recurring cellular functions controlling drug interactions. In particular, we found that polysaccharide and ATP synthesis control multiple drug interactions with previously unexplained mechanisms, and small molecule adjuvants targeting these functions synthetically reshape drug interactions in predictable ways. These results provide a new conceptual framework for the design of multidrug combinations and suggest that there are universal mechanisms at the heart of most drug interactions. Synopsis A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions and can be targeted by small molecules to alter drug interactions in predictable ways. Drug interactions between antibiotics are highly robust to genetic perturbations. A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions. Diverse drug interactions are controlled by recurring cellular functions, including LPS synthesis and ATP synthesis. A general principle of bacterial growth enables the prediction of mutant growth rates under drug combinations. Rare violations of this principle expose cellular functions that control drug interactions and can be targeted by small molecules to alter drug interactions in predictable ways