@inproceedings{1653, abstract = {A somewhere statistically binding (SSB) hash, introduced by Hubáček and Wichs (ITCS ’15), can be used to hash a long string x to a short digest y = H hk (x) using a public hashing-key hk. Furthermore, there is a way to set up the hash key hk to make it statistically binding on some arbitrary hidden position i, meaning that: (1) the digest y completely determines the i’th bit (or symbol) of x so that all pre-images of y have the same value in the i’th position, (2) it is computationally infeasible to distinguish the position i on which hk is statistically binding from any other position i’. Lastly, the hash should have a local opening property analogous to Merkle-Tree hashing, meaning that given x and y = H hk (x) it should be possible to create a short proof π that certifies the value of the i’th bit (or symbol) of x without having to provide the entire input x. A similar primitive called a positional accumulator, introduced by Koppula, Lewko and Waters (STOC ’15) further supports dynamic updates of the hashed value. These tools, which are interesting in their own right, also serve as one of the main technical components in several recent works building advanced applications from indistinguishability obfuscation (iO). The prior constructions of SSB hashing and positional accumulators required fully homomorphic encryption (FHE) and iO respectively. In this work, we give new constructions of these tools based on well studied number-theoretic assumptions such as DDH, Phi-Hiding and DCR, as well as a general construction from lossy/injective functions.}, author = {Okamoto, Tatsuaki and Pietrzak, Krzysztof Z and Waters, Brent and Wichs, Daniel}, location = {Auckland, New Zealand}, pages = {121 -- 145}, publisher = {Springer}, title = {{New realizations of somewhere statistically binding hashing and positional accumulators}}, doi = {10.1007/978-3-662-48797-6_6}, volume = {9452}, year = {2016}, } @article{1662, abstract = {We introduce a modification of the classic notion of intrinsic volume using persistence moments of height functions. Evaluating the modified first intrinsic volume on digital approximations of a compact body with smoothly embedded boundary in Rn, we prove convergence to the first intrinsic volume of the body as the resolution of the approximation improves. We have weaker results for the other modified intrinsic volumes, proving they converge to the corresponding intrinsic volumes of the n-dimensional unit ball.}, author = {Edelsbrunner, Herbert and Pausinger, Florian}, journal = {Advances in Mathematics}, pages = {674 -- 703}, publisher = {Academic Press}, title = {{Approximation and convergence of the intrinsic volume}}, doi = {10.1016/j.aim.2015.10.004}, volume = {287}, year = {2016}, } @article{1705, abstract = {Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.}, author = {Bogomolov, Sergiy and Donzé, Alexandre and Frehse, Goran and Grosu, Radu and Johnson, Taylor and Ladan, Hamed and Podelski, Andreas and Wehrle, Martin}, journal = {International Journal on Software Tools for Technology Transfer}, number = {4}, pages = {449 -- 467}, publisher = {Springer}, title = {{Guided search for hybrid systems based on coarse-grained space abstractions}}, doi = {10.1007/s10009-015-0393-y}, volume = {18}, year = {2016}, } @inproceedings{1707, abstract = {Volunteer supporters play an important role in modern crisis and disaster management. In the times of mobile Internet devices, help from thousands of volunteers can be requested within a short time span, thus relieving professional helpers from minor chores or geographically spread-out tasks. However, the simultaneous availability of many volunteers also poses new problems. In particular, the volunteer efforts must be well coordinated, or otherwise situations might emerge in which too many idle volunteers at one location become more of a burden than a relief to the professionals. In this work, we study the task of optimally assigning volunteers to selected locations, e.g. in order to perform regular measurements, to report on damage, or to distribute information or resources to the population in a crisis situation. We formulate the assignment tasks as an optimization problem and propose an effective and efficient solution procedure. Experiments on real data of the Team Österreich, consisting of over 36,000 Austrian volunteers, show the effectiveness and efficiency of our approach.}, author = {Pielorz, Jasmin and Lampert, Christoph}, location = {Rennes, France}, publisher = {IEEE}, title = {{Optimal geospatial allocation of volunteers for crisis management}}, doi = {10.1109/ICT-DM.2015.7402041}, year = {2016}, } @article{173, abstract = {We calculate admissible values of r such that a square-free polynomial with integer coefficients, no fixed prime divisor and irreducible factors of degree at most 3 takes infinitely many values that are a product of at most r distinct primes.}, author = {Browning, Timothy D and Booker, Andrew}, journal = {Discrete Analysis}, pages = {1 -- 18}, title = {{Square-free values of reducible polynomials}}, doi = {10.19086/da.732}, volume = {8}, year = {2016}, } @article{1794, abstract = {We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.}, author = {Kolmogorov, Vladimir and Takhanov, Rustem}, journal = {Algorithmica}, number = {1}, pages = {17 -- 46}, publisher = {Springer}, title = {{Inference algorithms for pattern-based CRFs on sequence data}}, doi = {10.1007/s00453-015-0017-7}, volume = {76}, year = {2016}, } @article{1833, abstract = {Relational models for contingency tables are generalizations of log-linear models, allowing effects associated with arbitrary subsets of cells in the table, and not necessarily containing the overall effect, that is, a common parameter in every cell. Similarly to log-linear models, relational models can be extended to non-negative distributions, but the extension requires more complex methods. An extended relational model is defined as an algebraic variety, and it turns out to be the closure of the original model with respect to the Bregman divergence. In the extended relational model, the MLE of the cell parameters always exists and is unique, but some of its properties may be different from those of the MLE under log-linear models. The MLE can be computed using a generalized iterative scaling procedure based on Bregman projections. }, author = {Klimova, Anna and Rudas, Tamás}, journal = {Journal of Multivariate Analysis}, pages = {440 -- 452}, publisher = {Elsevier}, title = {{On the closure of relational models}}, doi = {10.1016/j.jmva.2015.10.005}, volume = {143}, year = {2016}, } @article{1881, abstract = {We consider random matrices of the form H=W+λV, λ∈ℝ+, where W is a real symmetric or complex Hermitian Wigner matrix of size N and V is a real bounded diagonal random matrix of size N with i.i.d.\ entries that are independent of W. We assume subexponential decay for the matrix entries of W and we choose λ∼1, so that the eigenvalues of W and λV are typically of the same order. Further, we assume that the density of the entries of V is supported on a single interval and is convex near the edges of its support. In this paper we prove that there is λ+∈ℝ+ such that the largest eigenvalues of H are in the limit of large N determined by the order statistics of V for λ>λ+. In particular, the largest eigenvalue of H has a Weibull distribution in the limit N→∞ if λ>λ+. Moreover, for N sufficiently large, we show that the eigenvectors associated to the largest eigenvalues are partially localized for λ>λ+, while they are completely delocalized for λ<λ+. Similar results hold for the lowest eigenvalues. }, author = {Lee, Jioon and Schnelli, Kevin}, journal = {Probability Theory and Related Fields}, number = {1-2}, pages = {165 -- 241}, publisher = {Springer}, title = {{Extremal eigenvalues and eigenvectors of deformed Wigner matrices}}, doi = {10.1007/s00440-014-0610-8}, volume = {164}, year = {2016}, } @article{13385, abstract = {Novel light-responsive nanoparticles were synthesized by decorating the surfaces of gold and silver nanoparticles with a nitrospiropyran molecular photoswitch. Upon exposure to UV light in nonpolar solvents, these nanoparticles self-assembled to afford spherical aggregates, which disassembled rapidly when the UV stimulus was turned off. The sizes of these aggregates depended on the nanoparticle concentration, and their lifetimes could be controlled by adjusting the surface concentration of nitrospiropyran on the nanoparticles. The conformational flexibility of nitrospiropyran, which was altered by modifying the structure of the background ligand, had a profound impact on the self-assembly process. By coating the nanoparticles with a spiropyran lacking the nitro group, a conceptually different self-assembly system, relying on a reversible proton transfer, was realized. The resulting particles spontaneously (in the dark) assembled into aggregates that could be readily disassembled upon exposure to blue light.}, author = {Kundu, Pintu K. and Das, Sanjib and Ahrens, Johannes and Klajn, Rafal}, issn = {2040-3372}, journal = {Nanoscale}, keywords = {General Materials Science}, number = {46}, pages = {19280--19286}, publisher = {Royal Society of Chemistry}, title = {{Controlling the lifetimes of dynamic nanoparticle aggregates by spiropyran functionalization}}, doi = {10.1039/c6nr05959g}, volume = {8}, year = {2016}, } @article{13386, abstract = {Azobenzenealkanethiols in self-assembled monolayers (SAMs) on Au(111) exhibit reversible trans–cis photoisomerization when diluted with alkanethiol spacers. Using these mixed SAMs, we show switching of the linear optical and second-harmonic response. The effective switching of these surface optical properties relies on a reasonably large cross section and a high photoisomerization yield as well as a long lifetime of the metastable cis isomer. We quantified the switching process by X-ray absorption spectroscopy. The cross sections for the trans–cis and cis–trans photoisomerization with 365 and 455 nm light, respectively, are 1 order of magnitude smaller than in solution. In vacuum, the 365 nm photostationary state comprises 50–74% of the molecules in the cis form, limited by their rapid thermal isomerization back to the trans state. In contrast, the 455 nm photostationary state contains nearly 100% trans-azobenzene. We determined time constants for the thermal cis–trans isomerization of only a few minutes in vacuum and in a dry nitrogen atmosphere but of more than 1 day in ambient air. Our results suggest that adventitious water adsorbed on the surface of the SAM stabilizes the polar cis configuration of azobenzene under ambient conditions. The back reaction rate constants differing by 2 orders of magnitude underline the huge influence of the environment and, accordingly, its importance when comparing various experiments.}, author = {Moldt, Thomas and Przyrembel, Daniel and Schulze, Michael and Bronsch, Wibke and Boie, Larissa and Brete, Daniel and Gahl, Cornelius and Klajn, Rafal and Tegeder, Petra and Weinelt, Martin}, issn = {1520-5827}, journal = {Langmuir}, keywords = {Electrochemistry, Spectroscopy, Surfaces and Interfaces, Condensed Matter Physics, General Materials Science}, number = {42}, pages = {10795--10801}, publisher = {American Chemical Society}, title = {{Differing isomerization kinetics of azobenzene-functionalized self-assembled monolayers in ambient air and in vacuum}}, doi = {10.1021/acs.langmuir.6b01690}, volume = {32}, year = {2016}, } @article{13387, abstract = {Come on in, the water's fine! Non-photoresponsive nanoparticles can be reversibly assembled using light by placing them in an aqueous solution of a photo­acid. Upon exposure to visible light, the photoacid reduces the pH of the solution, which induces attractive interactions between the nanoparticles. In the dark, the resulting nanoparticle aggregates spontaneously disassemble. The process can be repeated many times.}, author = {Samanta, Dipak and Klajn, Rafal}, issn = {2195-1071}, journal = {Advanced Optical Materials}, keywords = {Atomic and Molecular Physics, and Optics, Electronic, Optical and Magnetic Materials}, number = {9}, pages = {1373--1377}, publisher = {Wiley}, title = {{Aqueous light-controlled self-assembly of nanoparticles}}, doi = {10.1002/adom.201600364}, volume = {4}, year = {2016}, } @misc{13388, abstract = {The Inside Cover picture illustrates the fluorescent properties of a gold nanocluster functionalized with several copies of a red-emitting merocyanine (image by Ella Marushchenko). The red fluorescence can be turned on and off reversibly by using an external stimulus.}, author = {Udayabhaskararao, T. and Kundu, Pintu K. and Ahrens, Johannes and Klajn, Rafal}, booktitle = {ChemPhysChem}, issn = {1439-7641}, keywords = {Physical and Theoretical Chemistry, Atomic and Molecular Physics, and Optics}, number = {12}, pages = {1711--1711}, publisher = {Wiley}, title = {{Inside cover: Reversible photoisomerization of spiropyran on the surfaces of Au25 nanoclusters (ChemPhysChem 12/2016)}}, doi = {10.1002/cphc.201600480}, volume = {17}, year = {2016}, } @article{13389, abstract = {Au25 nanoclusters functionalized with a spiropyran molecular switch are synthesized via a ligand-exchange reaction at low temperature. The resulting nanoclusters are characterized by optical and NMR spectroscopies as well as by mass spectrometry. Spiropyran bound to nanoclusters isomerizes in a reversible fashion when exposed to UV and visible light, and its properties are similar to those of free spiropyran molecules in solution. The reversible photoisomerization entails the modulation of fluorescence as well as the light-controlled self-assembly of nanoclusters.}, author = {Udayabhaskararao, T. and Kundu, Pintu K. and Ahrens, Johannes and Klajn, Rafal}, issn = {1439-7641}, journal = {ChemPhysChem}, keywords = {Physical and Theoretical Chemistry, Atomic and Molecular Physics, and Optics}, number = {12}, pages = {1805--1809}, publisher = {Wiley}, title = {{Reversible photoisomerization of spiropyran on the surfaces of Au25 nanoclusters}}, doi = {10.1002/cphc.201500897}, volume = {17}, year = {2016}, } @article{1339, abstract = {We present a microelectromechanical system, in which a silicon beam is attached to a comb-drive actuator, which is used to tune the tension in the silicon beam and thus its resonance frequency. By measuring the resonance frequencies of the system, we show that the comb-drive actuator and the silicon beam behave as two strongly coupled resonators. Interestingly, the effective coupling rate (1.5 MHz) is tunable with the comb-drive actuator (10%) as well as with a side-gate (10%) placed close to the silicon beam. In contrast, the effective spring constant of the system is insensitive to either of them and changes only by 60.5%. Finally, we show that the comb-drive actuator can be used to switch between different coupling rates with a frequency of at least 10 kHz. }, author = {Verbiest, Gerard and Xu, Duo and Goldsche, Matthias and Khodkov, Timofiy and Barzanjeh, Shabir and Von Den Driesch, Nils and Buca, Dan and Stampfer, Christoph}, journal = {Applied Physics Letter}, publisher = {American Institute of Physics}, title = {{Tunable mechanical coupling between driven microelectromechanical resonators}}, doi = {10.1063/1.4964122}, volume = {109}, year = {2016}, } @article{13390, author = {Klajn, Rafal}, issn = {1869-1870}, journal = {Science China Chemistry}, keywords = {General Chemistry}, number = {4}, pages = {420--421}, publisher = {Springer Nature}, title = {{Borrowing titania’s photoinduced electrons for molecular switching}}, doi = {10.1007/s11426-016-5573-4}, volume = {59}, year = {2016}, } @article{13391, abstract = {It is reported that spiropyran—a widely investigated molecular photoswitch—can be stabilized in aqueous environments in the presence of a variety of proteins, including human serum albumin, insulin fibrils, lysozyme, and glucose oxidase. The optical properties of the complexed photoswitch are protein dependent, with human serum albumin providing the spiropyran with emission features previously observed for a photoswitch confined in media of high viscosity. Despite being bound to the protein molecules, spiropyran can undergo a ring-opening reaction upon exposure to UV light. This photoisomerization process can affect the properties of the proteins: here, it is shown that the electrical conduction through human serum albumin to which the spiropyran is bound increases following the ring-opening reaction.}, author = {Amdursky, Nadav and Kundu, Pintu K. and Ahrens, Johannes and Huppert, Dan and Klajn, Rafal}, issn = {2192-6506}, journal = {ChemPlusChem}, keywords = {General Chemistry}, number = {1}, pages = {44--48}, publisher = {Wiley}, title = {{Noncovalent interactions with proteins modify the physicochemical properties of a molecular switch}}, doi = {10.1002/cplu.201500417}, volume = {81}, year = {2016}, } @inproceedings{1340, abstract = {We study repeated games with absorbing states, a type of two-player, zero-sum concurrent mean-payoff games with the prototypical example being the Big Match of Gillete (1957). These games may not allow optimal strategies but they always have ε-optimal strategies. In this paper we design ε-optimal strategies for Player 1 in these games that use only O(log log T) space. Furthermore, we construct strategies for Player 1 that use space s(T), for an arbitrary small unbounded non-decreasing function s, and which guarantee an ε-optimal value for Player 1 in the limit superior sense. The previously known strategies use space Ω(log T) and it was known that no strategy can use constant space if it is ε-optimal even in the limit superior sense. We also give a complementary lower bound. Furthermore, we also show that no Markov strategy, even extended with finite memory, can ensure value greater than 0 in the Big Match, answering a question posed by Neyman [11].}, author = {Hansen, Kristoffer and Ibsen-Jensen, Rasmus and Koucký, Michal}, location = {Liverpool, United Kingdom}, pages = {64 -- 76}, publisher = {Springer}, title = {{The big match in small space}}, doi = {10.1007/978-3-662-53354-3_6}, volume = {9928}, year = {2016}, } @inproceedings{1341, abstract = {In resource allocation games, selfish players share resources that are needed in order to fulfill their objectives. The cost of using a resource depends on the load on it. In the traditional setting, the players make their choices concurrently and in one-shot. That is, a strategy for a player is a subset of the resources. We introduce and study dynamic resource allocation games. In this setting, the game proceeds in phases. In each phase each player chooses one resource. A scheduler dictates the order in which the players proceed in a phase, possibly scheduling several players to proceed concurrently. The game ends when each player has collected a set of resources that fulfills his objective. The cost for each player then depends on this set as well as on the load on the resources in it – we consider both congestion and cost-sharing games. We argue that the dynamic setting is the suitable setting for many applications in practice. We study the stability of dynamic resource allocation games, where the appropriate notion of stability is that of subgame perfect equilibrium, study the inefficiency incurred due to selfish behavior, and also study problems that are particular to the dynamic setting, like constraints on the order in which resources can be chosen or the problem of finding a scheduler that achieves stability.}, author = {Avni, Guy and Henzinger, Thomas A and Kupferman, Orna}, location = {Liverpool, United Kingdom}, pages = {153 -- 166}, publisher = {Springer}, title = {{Dynamic resource allocation games}}, doi = {10.1007/978-3-662-53354-3_13}, volume = {9928}, year = {2016}, } @article{1342, abstract = {A key aspect of bacterial survival is the ability to evolve while migrating across spatially varying environmental challenges. Laboratory experiments, however, often study evolution in well-mixed systems. Here, we introduce an experimental device, the microbial evolution and growth arena (MEGA)-plate, in which bacteria spread and evolved on a large antibiotic landscape (120 × 60 centimeters) that allowed visual observation of mutation and selection in a migrating bacterial front.While resistance increased consistently, multiple coexisting lineages diversified both phenotypically and genotypically. Analyzing mutants at and behind the propagating front,we found that evolution is not always led by the most resistant mutants; highly resistant mutants may be trapped behindmore sensitive lineages.TheMEGA-plate provides a versatile platformfor studying microbial adaption and directly visualizing evolutionary dynamics.}, author = {Baym, Michael and Lieberman, Tami and Kelsic, Eric and Chait, Remy P and Gross, Rotem and Yelin, Idan and Kishony, Roy}, journal = {Science}, number = {6304}, pages = {1147 -- 1151}, publisher = {American Association for the Advancement of Science}, title = {{Spatiotemporal microbial evolution on antibiotic landscapes}}, doi = {10.1126/science.aag0822}, volume = {353}, year = {2016}, } @article{1343, abstract = {The Fermi-Hubbard model is one of the key models of condensed matter physics, which holds a potential for explaining the mystery of high-temperature superconductivity. Recent progress in ultracold atoms in optical lattices has paved the way to studying the model’s phase diagram using the tools of quantum simulation, which emerged as a promising alternative to the numerical calculations plagued by the infamous sign problem. However, the temperatures achieved using elaborate laser cooling protocols so far have been too high to show the appearance of antiferromagnetic (AF) and superconducting quantum phases directly. In this work, we demonstrate that using the machinery of dissipative quantum state engineering, one can observe the emergence of the AF order in the Fermi-Hubbard model with fermions in optical lattices. The core of the approach is to add incoherent laser scattering in such a way that the AF state emerges as the dark state of the driven-dissipative dynamics. The proposed controlled dissipation channels described in this work are straightforward to add to already existing experimental setups.}, author = {Kaczmarczyk, Jan and Weimer, Hendrik and Lemeshko, Mikhail}, journal = {New Journal of Physics}, number = {9}, publisher = {IOP Publishing Ltd.}, title = {{Dissipative preparation of antiferromagnetic order in the Fermi-Hubbard model}}, doi = {10.1088/1367-2630/18/9/093042}, volume = {18}, year = {2016}, }