@inproceedings{313,
  abstract     = {Tunneling of a particle through a potential barrier remains one of the most remarkable quantum phenomena. Owing to advances in laser technology, electric fields comparable to those electrons experience in atoms are readily generated and open opportunities to dynamically investigate the process of electron tunneling through the potential barrier formed by the superposition of both laser and atomic fields. Attosecond-time and angstrom-space resolution of the strong laser-field technique allow to address fundamental questions related to tunneling, which are still open and debated: Which time is spent under the barrier and what momentum is picked up by the particle in the meantime? In this combined experimental and theoretical study we demonstrate that for strong-field ionization the leading quantum mechanical Wigner treatment for the time resolved description of tunneling is valid. We achieve a high sensitivity on the tunneling barrier and unambiguously isolate its effects by performing a differential study of two systems with almost identical tunneling geometry. Moreover, working with a low frequency laser, we essentially limit the non-adiabaticity of the process as a major source of uncertainty. The agreement between experiment and theory implies two substantial corrections with respect to the widely employed quasiclassical treatment: In addition to a non-vanishing longitudinal momentum along the laser field-direction we provide clear evidence for a non-zero tunneling time delay. This addresses also the fundamental question how the transition occurs from the tunnel barrier to free space classical evolution of the ejected electron.},
  author       = {Camus, Nicolas and Yakaboylu, Enderalp and Fechner, Lutz and Klaiber, Michael and Laux, Martin and Mi, Yonghao and Hatsagortsyan, Karen and Pfeifer, Thomas and Keitel, Cristoph and Moshammer, Robert},
  issn         = {1742-6588},
  location     = {Kazan, Russian Federation},
  number       = {1},
  publisher    = {American Physical Society},
  title        = {{Experimental evidence for Wigner's tunneling time}},
  doi          = {10.1088/1742-6596/999/1/012004},
  volume       = {999},
  year         = {2017},
}

@inbook{424,
  abstract     = {We 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 Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] 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 C*(K)→C*(Rd).},
  author       = {Goaoc, Xavier and Paták, Pavel and Patakova, Zuzana and Tancer, Martin and Wagner, Uli},
  booktitle    = {A Journey through Discrete Mathematics: A Tribute to Jiri Matousek},
  editor       = {Loebl, Martin and Nešetřil, Jaroslav and Thomas, Robin},
  isbn         = {978-331944479-6},
  pages        = {407 -- 447},
  publisher    = {Springer},
  title        = {{Bounding helly numbers via betti numbers}},
  doi          = {10.1007/978-3-319-44479-6_17},
  year         = {2017},
}

@inproceedings{431,
  abstract     = {Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to its excellent scalability properties. A fundamental barrier when parallelizing SGD is the high bandwidth cost of communicating gradient updates between nodes; consequently, several lossy compresion heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always converge. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes with convergence guarantees and good practical performance. QSGD allows the user to smoothly trade off communication bandwidth and convergence time: nodes can adjust the number of bits sent per iteration, at the cost of possibly higher variance. We show that this trade-off is inherent, in the sense that improving it past some threshold would violate information-theoretic lower bounds. QSGD guarantees convergence for convex and non-convex objectives, under asynchrony, and can be extended to stochastic variance-reduced techniques. When applied to training deep neural networks for image classification and automated speech recognition, QSGD leads to significant reductions in end-to-end training time. For instance, on 16GPUs, we can train the ResNet-152 network to full accuracy on ImageNet 1.8 × faster than the full-precision variant. },
  author       = {Alistarh, Dan-Adrian and Grubic, Demjan and Li, Jerry and Tomioka, Ryota and Vojnović, Milan},
  issn         = {1049-5258},
  location     = {Long Beach, CA, United States},
  pages        = {1710--1721},
  publisher    = {Neural Information Processing Systems Foundation},
  title        = {{QSGD: Communication-efficient SGD via gradient quantization and encoding}},
  volume       = {2017},
  year         = {2017},
}

@inproceedings{432,
  abstract     = {Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order of magnitude. We examine training at reduced precision, both from a theoretical and practical perspective, and ask: is it possible to train models at end-to-end low precision with provable guarantees? Can this lead to consistent order-of-magnitude speedups? We mainly focus on linear models, and the answer is yes for linear models. We develop a simple framework called ZipML based on one simple but novel strategy called double sampling. Our ZipML framework is able to execute training at low precision with no bias, guaranteeing convergence, whereas naive quanti- zation would introduce significant bias. We val- idate our framework across a range of applica- tions, and show that it enables an FPGA proto- type that is up to 6.5 × faster than an implemen- tation using full 32-bit precision. We further de- velop a variance-optimal stochastic quantization strategy and show that it can make a significant difference in a variety of settings. When applied to linear models together with double sampling, we save up to another 1.7 × in data movement compared with uniform quantization. When training deep networks with quantized models, we achieve higher accuracy than the state-of-the- art XNOR-Net. },
  author       = {Zhang, Hantian and Li, Jerry and Kara, Kaan and Alistarh, Dan-Adrian and Liu, Ji and Zhang, Ce},
  booktitle    = {Proceedings of Machine Learning Research},
  isbn         = {978-151085514-4},
  location     = {Sydney, Australia},
  pages        = {4035 -- 4043},
  publisher    = {ML Research Press},
  title        = {{ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning}},
  volume       = { 70},
  year         = {2017},
}

@article{466,
  abstract     = {We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. There exist two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector. We consider optimization with respect to both objectives at once, thus unifying the existing semantics. Precisely, the goal is to optimize the expectation while ensuring the satisfaction constraint. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensure certain probabilistic guarantee). Our main results are as follows: First, we present algorithms for the decision problems which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Second, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem. },
  author       = {Chatterjee, Krishnendu and Křetínská, Zuzana and Kretinsky, Jan},
  issn         = {1860-5974},
  journal      = {Logical Methods in Computer Science},
  number       = {2},
  publisher    = {International Federation for Computational Logic},
  title        = {{Unifying two views on multiple mean-payoff objectives in Markov decision processes}},
  doi          = {10.23638/LMCS-13(2:15)2017},
  volume       = {13},
  year         = {2017},
}

@article{465,
  abstract     = {The edit distance between two words w 1 , w 2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w 1 to w 2 . The edit distance generalizes to languages L 1 , L 2 , where the edit distance from L 1 to L 2 is the minimal number k such that for every word from L 1 there exists a word in L 2 with edit distance at most k . We study the edit distance computation problem between pushdown automata and their subclasses. The problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for the following problems: (1) deciding whether, for a given threshold k , the edit distance from a pushdown automaton to a finite automaton is at most k , and (2) deciding whether the edit distance from a pushdown automaton to a finite automaton is finite. },
  author       = {Chatterjee, Krishnendu and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Otop, Jan},
  issn         = {1860-5974},
  journal      = {Logical Methods in Computer Science},
  number       = {3},
  publisher    = {International Federation for Computational Logic},
  title        = {{Edit distance for pushdown automata}},
  doi          = {10.23638/LMCS-13(3:23)2017},
  volume       = {13},
  year         = {2017},
}

@article{464,
  abstract     = {The computation of the winning set for parity objectives and for Streett objectives in graphs as well as in game graphs are central problems in computer-aided verification, with application to the verification of closed systems with strong fairness conditions, the verification of open systems, checking interface compatibility, well-formedness of specifications, and the synthesis of reactive systems. We show how to compute the winning set on n vertices for (1) parity-3 (aka one-pair Streett) objectives in game graphs in time O(n5/2) and for (2) k-pair Streett objectives in graphs in time O(n2+nklogn). For both problems this gives faster algorithms for dense graphs and represents the first improvement in asymptotic running time in 15 years.},
  author       = {Chatterjee, Krishnendu and Henzinger, Monika H and Loitzenbauer, Veronika},
  issn         = {1860-5974},
  journal      = {Logical Methods in Computer Science},
  number       = {3},
  publisher    = {International Federation for Computational Logic},
  title        = {{Improved algorithms for parity and Streett objectives}},
  doi          = {10.23638/LMCS-13(3:26)2017},
  volume       = {13},
  year         = {2017},
}

@article{484,
  abstract     = {We consider the dynamics of a large quantum system of N identical bosons in 3D interacting via a two-body potential of the form N3β-1w(Nβ(x - y)). For fixed 0 = β < 1/3 and large N, we obtain a norm approximation to the many-body evolution in the Nparticle Hilbert space. The leading order behaviour of the dynamics is determined by Hartree theory while the second order is given by Bogoliubov theory.},
  author       = {Nam, Phan and Napiórkowski, Marcin M},
  issn         = {1095-0761},
  journal      = {Advances in Theoretical and Mathematical Physics},
  number       = {3},
  pages        = {683 -- 738},
  publisher    = {International Press of Boston},
  title        = {{Bogoliubov correction to the mean-field dynamics of interacting bosons}},
  doi          = {10.4310/ATMP.2017.v21.n3.a4},
  volume       = {21},
  year         = {2017},
}

@article{483,
  abstract     = {We prove the universality for the eigenvalue gap statistics in the bulk of the spectrum for band matrices, in the regime where the band width is comparable with the dimension of the matrix, W ~ N. All previous results concerning universality of non-Gaussian random matrices are for mean-field models. By relying on a new mean-field reduction technique, we deduce universality from quantum unique ergodicity for band matrices.},
  author       = {Bourgade, Paul and Erdös, László and Yau, Horng and Yin, Jun},
  issn         = {1095-0761},
  journal      = {Advances in Theoretical and Mathematical Physics},
  number       = {3},
  pages        = {739 -- 800},
  publisher    = {International Press of Boston},
  title        = {{Universality for a class of random band matrices}},
  doi          = {10.4310/ATMP.2017.v21.n3.a5},
  volume       = {21},
  year         = {2017},
}

@inproceedings{1000,
  abstract     = {We study probabilistic models of natural images and extend the autoregressive family of PixelCNN models by incorporating latent variables. Subsequently, we describe two new generative image models that exploit different image transformations as latent variables: a quantized grayscale view of the image or a multi-resolution image pyramid. The proposed models tackle two known shortcomings of existing PixelCNN models: 1) their tendency to focus on low-level image details, while largely ignoring high-level image information, such as object shapes, and 2) their computationally costly procedure for image sampling. We experimentally demonstrate benefits of our LatentPixelCNN models, in particular showing that they produce much more realistically looking image samples than previous state-of-the-art probabilistic models. },
  author       = {Kolesnikov, Alexander and Lampert, Christoph},
  booktitle    = {34th International Conference on Machine Learning},
  isbn         = {978-151085514-4},
  location     = {Sydney, Australia},
  pages        = {1905 -- 1914},
  publisher    = {Journal of Machine Learning Research},
  title        = {{PixelCNN models with auxiliary variables for natural image modeling}},
  volume       = {70},
  year         = {2017},
}

@article{568,
  abstract     = {We study robust properties of zero sets of continuous maps f: X → ℝn. Formally, we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| ≥ r) and we claim that Z< r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r > 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C).},
  author       = {Franek, Peter and Krcál, Marek},
  issn         = {1532-0073},
  journal      = {Homology, Homotopy and Applications},
  number       = {2},
  pages        = {313 -- 342},
  publisher    = {International Press of Boston},
  title        = {{Persistence of zero sets}},
  doi          = {10.4310/HHA.2017.v19.n2.a16},
  volume       = {19},
  year         = {2017},
}

@article{701,
  abstract     = {A d-dimensional simplex S is called a k-reptile (or a k-reptile simplex) if it can be tiled by k simplices with disjoint interiors that are all mutually congruent and similar to S. For d = 2, triangular k-reptiles exist for all k of the form a^2, 3a^2 or a^2+b^2 and they have been completely characterized by Snover, Waiveris, and Williams. On the other hand, the only k-reptile simplices that are known for d ≥ 3, have k = m^d, where m is a positive integer. We substantially simplify the proof by Matoušek and the second author that for d = 3, k-reptile tetrahedra can exist only for k = m^3. We then prove a weaker analogue of this result for d = 4 by showing that four-dimensional k-reptile simplices can exist only for k = m^2.},
  author       = {Kynčl, Jan and Patakova, Zuzana},
  issn         = {1077-8926},
  journal      = {The Electronic Journal of Combinatorics},
  number       = {3},
  pages        = {1--44},
  publisher    = {International Press of Boston},
  title        = {{On the nonexistence of k reptile simplices in ℝ^3 and ℝ^4}},
  volume       = {24},
  year         = {2017},
}

@article{951,
  abstract     = {Dengue-suppressing Wolbachia strains are promising tools for arbovirus control, particularly as they have the potential to self-spread following local introductions. To test this, we followed the frequency of the transinfected Wolbachia strain wMel through Ae. aegypti in Cairns, Australia, following releases at 3 nonisolated locations within the city in early 2013. Spatial spread was analysed graphically using interpolation and by fitting a statistical model describing the position and width of the wave. For the larger 2 of the 3 releases (covering 0.97 km2 and 0.52 km2), we observed slow but steady spatial spread, at about 100–200 m per year, roughly consistent with theoretical predictions. In contrast, the smallest release (0.11 km2) produced erratic temporal and spatial dynamics, with little evidence of spread after 2 years. This is consistent with the prediction concerning fitness-decreasing Wolbachia transinfections that a minimum release area is needed to achieve stable local establishment and spread in continuous habitats. Our graphical and likelihood analyses produced broadly consistent estimates of wave speed and wave width. Spread at all sites was spatially heterogeneous, suggesting that environmental heterogeneity will affect large-scale Wolbachia transformations of urban mosquito populations. The persistence and spread of Wolbachia in release areas meeting minimum area requirements indicates the promise of successful large-scale population transfo},
  author       = {Schmidt, Tom and Barton, Nicholas H and Rasic, Gordana and Turley, Andrew and Montgomery, Brian and Iturbe Ormaetxe, Inaki and Cook, Peter and Ryan, Peter and Ritchie, Scott and Hoffmann, Ary and O’Neill, Scott and Turelli, Michael},
  issn         = {1544-9173},
  journal      = {PLoS Biology},
  number       = {5},
  publisher    = {Public Library of Science},
  title        = {{Local introduction and heterogeneous spatial spread of dengue-suppressing Wolbachia through an urban population of Aedes Aegypti}},
  doi          = {10.1371/journal.pbio.2001894},
  volume       = {15},
  year         = {2017},
}

@misc{9857,
  author       = {Schmidt, Tom and Barton, Nicholas H and Rasic, Gordana and Turley, Andrew and Montgomery, Brian and Iturbe Ormaetxe, Inaki and Cook, Peter and Ryan, Peter and Ritchie, Scott and Hoffmann, Ary and O’Neill, Scott and Turelli, Michael},
  publisher    = {Public Library of Science},
  title        = {{Supporting information concerning observed wMel frequencies and analyses of habitat variables}},
  doi          = {10.1371/journal.pbio.2001894.s015},
  year         = {2017},
}

@inbook{604,
  abstract     = {In several settings of physics and chemistry one has to deal with molecules interacting with some kind of an external environment, be it a gas, a solution, or a crystal surface. Understanding molecular processes in the presence of such a many-particle bath is inherently challenging, and usually requires large-scale numerical computations. Here, we present an alternative approach to the problem, based on the notion of the angulon quasiparticle. We show that molecules rotating inside superfluid helium nanodroplets and Bose–Einstein condensates form angulons, and therefore can be described by straightforward solutions of a simple microscopic Hamiltonian. Casting the problem in the language of angulons allows us not only to greatly simplify it, but also to gain insights into the origins of the observed phenomena and to make predictions for future experimental studies.},
  author       = {Lemeshko, Mikhail and Schmidt, Richard},
  booktitle    = {Cold Chemistry: Molecular Scattering and Reactivity Near Absolute Zero },
  editor       = {Dulieu, Oliver and Osterwalder, Andreas},
  issn         = {2041-3181},
  pages        = {444 -- 495},
  publisher    = {Royal Society of Chemistry},
  title        = {{Molecular impurities interacting with a many-particle environment: From ultracold gases to helium nanodroplets}},
  doi          = {10.1039/9781782626800-00444},
  volume       = {11},
  year         = {2017},
}

@article{823,
  abstract     = {The resolution of a linear system with positive integer variables is a basic yet difficult computational problem with many applications. We consider sparse uncorrelated random systems parametrised by the density c and the ratio α=N/M between number of variables N and number of constraints M. By means of ensemble calculations we show that the space of feasible solutions endows a Van-Der-Waals phase diagram in the plane (c, α). We give numerical evidence that the associated computational problems become more difficult across the critical point and in particular in the coexistence region.},
  author       = {Colabrese, Simona and De Martino, Daniele and Leuzzi, Luca and Marinari, Enzo},
  issn         = {1742-5468},
  journal      = {Journal of Statistical Mechanics: Theory and Experiment},
  number       = {9},
  publisher    = {IOP Publishing},
  title        = {{Phase transitions in integer linear problems}},
  doi          = {10.1088/1742-5468/aa85c3},
  volume       = {2017},
  year         = {2017},
}

@article{912,
  abstract     = {We consider a many-body system of fermionic atoms interacting via a local pair potential and subject to an external potential within the framework of Bardeen-Cooper-Schrieffer (BCS) theory. We measure the free energy of the whole sample with respect to the free energy of a reference state which allows us to define a BCS functional with boundary conditions at infinity. Our main result is a lower bound for this energy functional in terms of expressions that typically appear in Ginzburg-Landau functionals.
},
  author       = {Deuchert, Andreas},
  issn         = {0022-2488},
  journal      = {Journal of Mathematical Physics},
  number       = {8},
  publisher    = {AIP Publishing},
  title        = {{A lower bound for the BCS functional with boundary conditions at infinity}},
  doi          = {10.1063/1.4996580},
  volume       = {58},
  year         = {2017},
}

@article{744,
  abstract     = {In evolutionary game theory interactions between individuals are often assumed obligatory. However, in many real-life situations, individuals can decide to opt out of an interaction depending on the information they have about the opponent. We consider a simple evolutionary game theoretic model to study such a scenario, where at each encounter between two individuals the type of the opponent (cooperator/defector) is known with some probability, and where each individual either accepts or opts out of the interaction. If the type of the opponent is unknown, a trustful individual accepts the interaction, whereas a suspicious individual opts out of the interaction. If either of the two individuals opt out both individuals remain without an interaction. We show that in the prisoners dilemma optional interactions along with suspicious behaviour facilitates the emergence of trustful cooperation.},
  author       = {Priklopil, Tadeas and Chatterjee, Krishnendu and Nowak, Martin},
  issn         = {0022-5193},
  journal      = {Journal of Theoretical Biology},
  pages        = {64 -- 72},
  publisher    = {Elsevier},
  title        = {{Optional interactions and suspicious behaviour facilitates trustful cooperation in prisoners dilemma}},
  doi          = {10.1016/j.jtbi.2017.08.025},
  volume       = {433},
  year         = {2017},
}

@article{1076,
  abstract     = {Signatures of the Coulomb corrections in the photoelectron momentum distribution during laser-induced ionization of atoms or ions in tunneling and multiphoton regimes are investigated analytically in the case of a one-dimensional problem. A high-order Coulomb-corrected strong-field approximation is applied, where the exact continuum state in the S matrix is approximated by the eikonal Coulomb-Volkov state including the second-order corrections to the eikonal. Although without high-order corrections our theory coincides with the known analytical R-matrix (ARM) theory, we propose a simplified procedure for the matrix element derivation. Rather than matching the eikonal Coulomb-Volkov wave function with the bound state as in the ARM theory to remove the Coulomb singularity, we calculate the matrix element via the saddle-point integration method by time as well as by coordinate, and in this way avoiding the Coulomb singularity. The momentum shift in the photoelectron momentum distribution with respect to the ARM theory due to high-order corrections is analyzed for tunneling and multiphoton regimes. The relation of the quantum corrections to the tunneling delay time is discussed.},
  author       = {Klaiber, Michael and Daněk, Jiří and Yakaboylu, Enderalp and Hatsagortsyan, Karen and Keitel, Christoph},
  issn         = {2469-9926},
  journal      = {Physical Review A},
  number       = {2},
  publisher    = {American Physical Society},
  title        = {{Strong-field ionization via a high-order Coulomb-corrected strong-field approximation}},
  doi          = {10.1103/PhysRevA.95.023403},
  volume       = {95},
  year         = {2017},
}

@inproceedings{6526,
  abstract     = {This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.},
  author       = {Skórski, Maciej},
  booktitle    = {2017 IEEE International Symposium on Information Theory},
  isbn         = {9781509040964},
  location     = {Aachen, Germany},
  publisher    = {IEEE},
  title        = {{On the complexity of estimating Rènyi divergences}},
  doi          = {10.1109/isit.2017.8006529},
  year         = {2017},
}