@article{2427, abstract = {Intersection graphs of disks and of line segments, respectively, have been well studied, because of both practical applications and theoretically interesting properties of these graphs. Despite partial results, the complexity status of the Clique problem for these two graph classes is still open. Here, we consider the Clique problem for intersection graphs of ellipses, which, in a sense, interpolate between disks and line segments, and show that the problem is APX-hard in that case. Moreover, this holds even if for all ellipses, the ratio of the larger over the smaller radius is some prescribed number. Furthermore, the reduction immediately carries over to intersection graphs of triangles. To our knowledge, this is the first hardness result for the Clique problem in intersection graphs of convex objects with finite description complexity. We also describe a simple approximation algorithm for the case of ellipses for which the ratio of radii is bounded.}, author = {Ambühl, Christoph and Uli Wagner}, journal = {Theory of Computing Systems}, number = {3}, pages = {279 -- 292}, publisher = {Springer}, title = {{The Clique problem in intersection graphs of ellipses and triangles}}, doi = {10.1007/s00224-005-1141-6}, volume = {38}, year = {2005}, } @inproceedings{2428, abstract = {We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log 2 n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log 2 n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open.}, author = {Fiat, Amos and Levy, Meital B and Matoušek, Jiří and Pach, Elchanan M and Sharir, Micha and Smorodinsky, Shakhar and Uli Wagner and Welzl, Emo}, pages = {545 -- 554}, publisher = {SIAM}, title = {{Online conflict-free coloring for intervals}}, doi = {10.1137/S0097539704446682}, year = {2005}, } @inproceedings{4560, abstract = {We define and study a quantitative generalization of the traditional boolean framework of model-based specification and verification. In our setting, propositions have integer values at states, and properties have integer values on traces. For example, the value of a quantitative proposition at a state may represent power consumed at the state, and the value of a quantitative property on a trace may represent energy used along the trace. The value of a quantitative property at a state, then, is the maximum (or minimum) value achievable over all possible traces from the state. In this framework, model checking can be used to compute, for example, the minimum battery capacity necessary for achieving a given objective, or the maximal achievable lifetime of a system with a given initial battery capacity. In the case of open systems, these problems require the solution of games with integer values. Quantitative model checking and game solving is undecidable, except if bounds on the computation can be found. Indeed, many interesting quantitative properties, like minimal necessary battery capacity and maximal achievable lifetime, can be naturally specified by quantitative-bound automata, which are finite automata with integer registers whose analysis is constrained by a bound function f that maps each system K to an integer f(K). Along with the linear-time, automaton-based view of quantitative verification, we present a corresponding branching-time view based on a quantitative-bound μ-calculus, and we study the relationship, expressive power, and complexity of both views. }, author = {Chakrabarti, Arindam and Krishnendu Chatterjee and Thomas Henzinger and Kupferman, Orna and Majumdar, Ritankar S}, pages = {50 -- 64}, publisher = {Springer}, title = {{Verifying quantitative properties using bound functions}}, doi = {10.1007/11560548_7}, volume = {3725}, year = {2005}, } @inproceedings{4576, abstract = {We present a language for specifying web service interfaces. A web service interface puts three kinds of constraints on the users of the service. First, the interface specifies the methods that can be called by a client, together with types of input and output parameters; these are called signature constraints. Second, the interface may specify propositional constraints on method calls and output values that may oc- cur in a web service conversation; these are called consis- tency constraints. Third, the interface may specify temporal constraints on the ordering of method calls; these are called protocol constraints. The interfaces can be used to check, first, if two or more web services are compatible, and second, if a web service A can be safely substituted for a web ser- vice B. The algorithm for compatibility checking verifies that two or more interfaces fulfill each others’ constraints. The algorithm for substitutivity checking verifies that service A demands fewer and fulfills more constraints than service B.}, author = {Beyer, Dirk and Chakrabarti, Arindam and Thomas Henzinger}, pages = {148 -- 159}, publisher = {ACM}, title = {{Web service interfaces}}, doi = {10.1145/1060745.1060770}, year = {2005}, } @inproceedings{4579, abstract = {BLAST is an automatic verification tool for checking temporal safety properties of C programs. Given a C program and a temporal safety property, BLAST statically proves that either the program satisfies the safety property or the program has an execution trace that exhibits a violation of the property. BLAST constructs, explores, and refines abstractions of the program state space based on lazy predicate abstraction and interpolation-based predicate discovery. We show how BLAST can be used to statically prove memory safety for C programs. We take a two-step approach. First, we use Ccured, a type-based memory safety analyzer, to annotate with run-time checks all program points that cannot be proved memory safe by the type system. Second, we use BLAST to remove as many of the run-time checks as possible (by proving that these checks never fail), and to generate for the remaining run-time checks execution traces that witness them fail. Our experience shows that BLAST can remove many of the run-time checks added by Ccured and provide useful information to the programmer about many of the remaining checks.}, author = {Beyer, Dirk and Thomas Henzinger and Jhala, Ranjit and Majumdar, Ritankar S}, pages = {2 -- 18}, publisher = {Springer}, title = {{Checking memory safety with BLAST}}, doi = {10.1007/978-3-540-31984-9_2}, volume = {3442}, year = {2005}, } @inproceedings{4624, abstract = {Surveying results from [5] and [6], we motivate and introduce the theory behind formalizing rich interfaces for software and hardware components. Rich interfaces specify the protocol aspects of component interaction. Their formalization, called interface automata, permits a compiler to check the compatibility of component interaction protocols. Interface automata support incremental design and independent implementability. Incremental design means that the compatibility checking of interfaces can proceed for partial system descriptions, without knowing the interfaces of all components. Independent implementability means that compatible interfaces can be refined separately, while still maintaining compatibility.}, author = {de Alfaro, Luca and Thomas Henzinger}, pages = {83 -- 104}, publisher = {Springer}, title = {{Interface-based design}}, doi = {10.1007/1-4020-3532-2_3}, volume = {195}, year = {2005}, } @article{4625, abstract = {Temporal logic is two-valued: formulas are interpreted as either true or false. When applied to the analysis of stochastic systems, or systems with imprecise formal models, temporal logic is therefore fragile: even small changes in the model can lead to opposite truth values for a specification. We present a generalization of the branching-time logic CTL which achieves robustness with respect to model perturbations by giving a quantitative interpretation to predicates and logical operators, and by discounting the importance of events according to how late they occur. In every state, the value of a formula is a real number in the interval [0,1], where 1 corresponds to truth and 0 to falsehood. The boolean operators and and or are replaced by min and max, the path quantifiers ∃ and ∀ determine sup and inf over all paths from a given state, and the temporal operators ⋄ and □ specify sup and inf over a given path; a new operator averages all values along a path. Furthermore, all path operators are discounted by a parameter that can be chosen to give more weight to states that are closer to the beginning of the path. We interpret the resulting logic DCTL over transition systems, Markov chains, and Markov decision processes. We present two semantics for DCTL: a path semantics, inspired by the standard interpretation of state and path formulas in CTL, and a fixpoint semantics, inspired by the μ-calculus evaluation of CTL formulas. We show that, while these semantics coincide for CTL, they differ for DCTL, and we provide model-checking algorithms for both semantics.}, author = {de Alfaro, Luca and Faella, Marco and Thomas Henzinger and Majumdar, Ritankar S and Stoelinga, Mariëlle}, journal = {Theoretical Computer Science}, number = {1}, pages = {139 -- 170}, publisher = {Elsevier}, title = {{Model checking discounted temporal properties}}, doi = {10.1016/j.tcs.2005.07.033}, volume = {345}, year = {2005}, } @inproceedings{575, abstract = {We present the first demonstration of Jozsa's "counterfactual computation", using an optical Grover's search algorithm. We put the algorithm in a superposition of 'running' and 'not-running', obtaining information even though the algorithm does not run.}, author = {Onur Hosten and Rakher, Matthew T and Barreiro, Julio T and Peters, Nicholas A and Kwiat, Paul G}, pages = {365 -- 367}, publisher = {IEEE}, title = {{Counterfactual quantum computation}}, doi = { 10.1109/QELS.2005.1548783}, volume = {1}, year = {2005}, } @article{6153, abstract = {A current challenge in neuroscience is to bridge the gaps between genes, proteins, neurons, neural circuits, and behavior in a single animal model. The nematode Caenorhabditis elegans has unique features that facilitate this synthesis. Its nervous system includes exactly 302 neurons, and their pattern of synaptic connectivity is known. With only five olfactory neurons, C. elegans can dynamically respond to dozens of attractive and repellant odors. Thermosensory neurons enable the nematode to remember its cultivation temperature and to track narrow isotherms. Polymodal sensory neurons detect a wide range of nociceptive cues and signal robust escape responses. Pairing of sensory stimuli leads to long-lived changes in behavior consistent with associative learning. Worms exhibit social behaviors and complex ultradian rhythms driven by Ca2+ oscillators with clock-like properties. Genetic analysis has identified gene products required for nervous system function and elucidated the molecular and neural bases of behaviors.}, author = {de Bono, Mario and Villu Maricq, Andres}, issn = {0147-006X}, journal = {Annual Review of Neuroscience}, pages = {451--501}, publisher = {Annual Reviews}, title = {{Neuronal substrates of complex behaviors in C. elegans}}, doi = {10.1146/annurev.neuro.27.070203.144259}, volume = {28}, year = {2005}, } @article{6154, author = {Cheung, Benny H.H. and Cohen, Merav and Rogers, Candida and Albayram, Onder and de Bono, Mario}, issn = {0960-9822}, journal = {Current Biology}, number = {10}, pages = {905--917}, publisher = {Elsevier}, title = {{Experience-dependent modulation of C. elegans behavior by ambient oxygen}}, doi = {10.1016/j.cub.2005.04.017}, volume = {15}, year = {2005}, } @inbook{1444, abstract = {The paper surveys the mirror symmetry conjectures of Hausel-Thaddeus and Hausel-Rodriguez-Villegas concerning the equality of certain Hodge numbers of SL(n, ℂ) vs. PGL(n, ℂ) flat connections and character varieties for curves, respectively. Several new results and conjectures and their relations to works of Hitchin, Gothen, Garsia-Haiman and Earl-Kirwan are explained. These use the representation theory of finite groups of Lie-type via the arithmetic of character varieties and lead to an unexpected conjecture for a Hard Lefschetz theorem for their cohomology.}, author = {Tamas Hausel}, booktitle = {Geometric Methods in Algebra and Number Theory}, pages = {193 -- 217}, publisher = {Springer}, title = {{Mirror symmetry and Langlands duality in the non-Abelian Hodge theory of a curve}}, doi = {10.1007/0-8176-4417-2_9}, volume = {235}, year = {2005}, } @article{1447, abstract = {Building on a recent paper [8], here we argue that the combinatorics of matroids are intimately related to the geometry and topology of toric hyperkähler varieties. We show that just like toric varieties occupy a central role in Stanley’s proof for the necessity of McMullen’s conjecture (or g-inequalities) about the classification of face vectors of simplicial polytopes, the topology of toric hyperkähler varieties leads to new restrictions on face vectors of matroid complexes. Namely in this paper we will give two proofs that the injectivity part of the Hard Lefschetz theorem survives for toric hyperkähler varieties. We explain how this implies the g-inequalities for rationally representable matroids. We show how the geometrical intuition in the first proof, coupled with results of Chari [3], leads to a proof of the g-inequalities for general matroid complexes, which is a recent result of Swartz [20]. The geometrical idea in the second proof will show that a pure O-sequence should satisfy the g-inequalities, thus showing that our result is in fact a consequence of a long-standing conjecture of Stanley.}, author = {Tamas Hausel}, journal = {Open Mathematics}, number = {1}, pages = {26 -- 38}, publisher = {Central European Science Journals}, title = {{Quaternionic geometry of matroids}}, doi = {10.2478/BF02475653}, volume = {3}, year = {2005}, } @article{1463, abstract = {We study an integration theory in circle equivariant cohomology in order to prove a theorem relating the cohomology ring of a hyperkähler quotient to the cohomology ring of the quotient by a maximal abelian subgroup, analogous to a theorem of Martin for symplectic quotients. We discuss applications of this theorem to quiver varieties, and compute as an example the ordinary and equivariant cohomology rings of a hyperpolygon space.}, author = {Tamas Hausel and Proudfoot, Nicholas J}, journal = {Topology}, number = {1}, pages = {231 -- 248}, publisher = {Elsevier}, title = {{Abelianization for hyperkähler quotients}}, doi = {10.1016/j.top.2004.04.002}, volume = {44}, year = {2005}, } @article{13431, abstract = {Hydrogel stamps can microstructure solid surfaces, i.e., modify the surface topology of metals, glasses, and crystals. It is demonstrated that stamps soaked in an appropriate etchant can remove material with micrometer-scale precision. The Figure shows an array of concentric circles etched in glass using the immersion wet stamping process described (scale bar: 500 μm).}, author = {Smoukov, S. K. and Bishop, K. J. M. and Klajn, Rafal and Campbell, C. J. and Grzybowski, B. A.}, issn = {1521-4095}, journal = {Advanced Materials}, keywords = {Mechanical Engineering, Mechanics of Materials, General Materials Science}, number = {11}, pages = {1361--1365}, publisher = {Wiley}, title = {{Cutting into solids with micropatterned gels}}, doi = {10.1002/adma.200402086}, volume = {17}, year = {2005}, } @article{13432, abstract = {A new experimental technique is described that uses reaction−diffusion phenomena as a means of one-step microfabrication of complex, multilevel surface reliefs. Thin films of dry gelatin doped with potassium hexacyanoferrate are chemically micropatterned with a solution of silver nitrate delivered from an agarose stamp. Precipitation reaction between the two salts causes the surface to deform. The mechanism of surface deformation is shown to involve a sequence of reactions, diffusion, and gel swelling/contraction. This mechanism is established experimentally and provides a basis of a theoretical lattice-gas model that allows prediction surface topographies emerging from arbitrary geometries of the stamped features. The usefulness of the technique is demonstrated by using it to rapidly prepare two types of mold for passive microfluidic mixers.}, author = {Campbell, Christopher J. and Klajn, Rafal and Fialkowski, Marcin and Grzybowski, Bartosz A.}, issn = {1520-5827}, journal = {Langmuir}, keywords = {Electrochemistry, Spectroscopy, Surfaces and Interfaces, Condensed Matter Physics, General Materials Science}, number = {1}, pages = {418--423}, publisher = {American Chemical Society}, title = {{One-step multilevel microfabrication by reaction−diffusion}}, doi = {10.1021/la0487747}, volume = {21}, year = {2005}, } @article{13433, abstract = {Self-assembled monolayers (SAMs) of alkane thiols on gold and other metals are versatile constructs with which to study interfacial phenomena and reactions at surfaces. Surface properties of SAMs - e.g., wettability, stability in diverse environments, propensity to interact with or to resist adsorption of macromolecules -- depend on and can be controlled flexibly by the properties of the functional (head) groups in the w position of the alkyl chain. SAMs provide a basis for many important scientific and technological applications, ranging from micropatterning methods, through sensing, to biological recognition. Despite their importance, the literature on SAMs and the synthesis of molecules that constitute them remains scattered and often conflicting. The purpose of this Review is (i) to summarize the applications and physical properties of SAMs and (ii) to systematize the strategies of synthesis of ω-functionalized alkane thiols. Generic retrosynthetic scheme is developed that allows efficient synthetic planning. Issues related to the selection of appropriate protecting groups and the ways of introduction of the thiol functionality are discussed in detail, and illustrated with examples of syntheses of several complex alkane thiols.}, author = {Witt, Dariusz and Klajn, Rafal and Barski, Piotr and Grzybowski, Bartosz}, issn = {1875-5348}, journal = {Current Organic Chemistry}, keywords = {Organic Chemistry}, number = {18}, pages = {1763--1797}, publisher = {Bentham Science}, title = {{Applications, properties and synthesis of w-functionalized n-alkanethiols and disulfides - the building blocks of self-assembled monolayers}}, doi = {10.2174/1385272043369421}, volume = {8}, year = {2005}, } @article{9491, abstract = {Cytosine DNA methylation in vertebrates is widespread, but methylation in plants is found almost exclusively at transposable elements and repetitive DNA [1]. Within regions of methylation, methylcytosines are typically found in CG, CNG, and asymmetric contexts. CG sites are maintained by a plant homolog of mammalian Dnmt1 acting on hemi-methylated DNA after replication. Methylation of CNG and asymmetric sites appears to be maintained at each cell cycle by other mechanisms. We report a new type of DNA methylation in Arabidopsis, dense CG methylation clusters found at scattered sites throughout the genome. These clusters lack non-CG methylation and are preferentially found in genes, although they are relatively deficient toward the 5′ end. CG methylation clusters are present in lines derived from different accessions and in mutants that eliminate de novo methylation, indicating that CG methylation clusters are stably maintained at specific sites. Because 5-methylcytosine is mutagenic, the appearance of CG methylation clusters over evolutionary time predicts a genome-wide deficiency of CG dinucleotides and an excess of C(A/T)G trinucleotides within transcribed regions. This is exactly what we find, implying that CG methylation clusters have contributed profoundly to plant gene evolution. We suggest that CG methylation clusters silence cryptic promoters that arise sporadically within transcription units.}, author = {Tran, Robert K. and Henikoff, Jorja G. and Zilberman, Daniel and Ditt, Renata F. and Jacobsen, Steven E. and Henikoff, Steven}, issn = {1879-0445}, journal = {Current Biology}, number = {2}, pages = {154--159}, publisher = {Elsevier}, title = {{DNA methylation profiling identifies CG methylation clusters in Arabidopsis genes}}, doi = {10.1016/j.cub.2005.01.008}, volume = {15}, year = {2005}, } @article{9514, abstract = {Background: DNA methylation occurs at preferred sites in eukaryotes. In Arabidopsis, DNA cytosine methylation is maintained by three subfamilies of methyltransferases with distinct substrate specificities and different modes of action. Targeting of cytosine methylation at selected loci has been found to sometimes involve histone H3 methylation and small interfering (si)RNAs. However, the relationship between different cytosine methylation pathways and their preferred targets is not known. Results: We used a microarray-based profiling method to explore the involvement of Arabidopsis CMT3 and DRM DNA methyltransferases, a histone H3 lysine-9 methyltransferase (KYP) and an Argonaute-related siRNA silencing component (AGO4) in methylating target loci. We found that KYP targets are also CMT3 targets, suggesting that histone methylation maintains CNG methylation genome-wide. CMT3 and KYP targets show similar proximal distributions that correspond to the overall distribution of transposable elements of all types, whereas DRM targets are distributed more distally along the chromosome. We find an inverse relationship between element size and loss of methylation in ago4 and drm mutants. Conclusion: We conclude that the targets of both DNA methylation and histone H3K9 methylation pathways are transposable elements genome-wide, irrespective of element type and position. Our findings also suggest that RNA-directed DNA methylation is required to silence isolated elements that may be too small to be maintained in a silent state by a chromatin-based mechanism alone. Thus, parallel pathways would be needed to maintain silencing of transposable elements.}, author = {Tran, Robert K. and Zilberman, Daniel and de Bustos, Cecilia and Ditt, Renata F. and Henikoff, Jorja G. and Lindroth, Anders M. and Delrow, Jeffrey and Boyle, Tom and Kwong, Samson and Bryson, Terri D. and Jacobsen, Steven E. and Henikoff, Steven}, issn = {1465-6906}, journal = {Genome Biology}, number = {11}, publisher = {Springer Nature}, title = {{Chromatin and siRNA pathways cooperate to maintain DNA methylation of small transposable elements in Arabidopsis}}, doi = {10.1186/gb-2005-6-11-r90}, volume = {6}, year = {2005}, } @article{9529, abstract = {Eukaryotic organisms have the remarkable ability to inherit states of gene activity without altering the underlying DNA sequence. This epigenetic inheritance can persist over thousands of years, providing an alternative to genetic mutations as a substrate for natural selection. Epigenetic inheritance might be propagated by differences in DNA methylation, post-translational histone modifications, and deposition of histone variants. Mounting evidence also indicates that small interfering RNA (siRNA)-mediated mechanisms play central roles in setting up and maintaining states of gene activity. Much of the epigenetic machinery of many organisms, including Arabidopsis, appears to be directed at silencing viruses and transposable elements, with epigenetic regulation of endogenous genes being mostly derived from such processes.}, author = {Zilberman, Daniel and Henikoff, Steven}, issn = {0959-437X}, journal = {Current Opinion in Genetics and Development}, number = {5}, pages = {557--562}, publisher = {Elsevier}, title = {{Epigenetic inheritance in Arabidopsis: Selective silence}}, doi = {10.1016/j.gde.2005.07.002}, volume = {15}, year = {2005}, } @article{11904, abstract = {Many daily activities present information in the form of a stream of text, and often people can benefit from additional information on the topic discussed. TV broadcast news can be treated as one such stream of text; in this paper we discuss finding news articles on the web that are relevant to news currently being broadcast. We evaluated a variety of algorithms for this problem, looking at the impact of inverse document frequency, stemming, compounds, history, and query length on the relevance and coverage of news articles returned in real time during a broadcast. We also evaluated several postprocessing techniques for improving the precision, including reranking using additional terms, reranking by document similarity, and filtering on document similarity. For the best algorithm, 84–91% of the articles found were relevant, with at least 64% of the articles being on the exact topic of the broadcast. In addition, a relevant article was found for at least 70% of the topics.}, author = {Henzinger, Monika H and Chang, Bay-Wei and Milch, Brian and Brin, Sergey}, issn = {1573-1413}, journal = {World Wide Web}, number = {2}, pages = {101--126}, publisher = {Springer Nature}, title = {{Query-free news search}}, doi = {10.1007/s11280-004-4870-6}, volume = {8}, year = {2005}, }