@article{6657, abstract = {In this article a model is described how Open Access definitions can be formed on the basis of objective criteria. The common Open Access definitions such as "gold" and "green" are not exactly defined. This becomes a problem as soon as one begins to measure Open Access, for example if the development of the Open Access share should be monitored. This was discussed in the working group on Open Access Monitoring of the AT2OA project and the present model was developed, which is based on 5 critics with 4 characteristics: location, licence, version, embargo and conditions of the Open Access publication are taken into account. In the meantime, the model has also been tested in practice using R scripts, and the initial results are quite promising.}, author = {Danowski, Patrick}, issn = {1022-2588}, journal = {Mitteilungen der Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare}, number = {1}, pages = {59--65}, publisher = {Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare}, title = {{An Austrian proposal for the classification of Open Access Tuples (COAT) - distinguish different open access types beyond colors}}, doi = {10.31263/voebm.v72i1.2276}, volume = {72}, year = {2019}, } @inproceedings{6822, abstract = {In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the qualitative winner or quantitative payoff of the game. In bidding games, in each turn, we hold an auction between the two players to determine which player moves the token. Bidding games have largely been studied with concrete bidding mechanisms that are variants of a first-price auction: in each turn both players simultaneously submit bids, the higher bidder moves the token, and pays his bid to the lower bidder in Richman bidding, to the bank in poorman bidding, and in taxman bidding, the bid is split between the other player and the bank according to a predefined constant factor. Bidding games are deterministic games. They have an intriguing connection with a fragment of stochastic games called randomturn games. We study, for the first time, a combination of bidding games with probabilistic behavior; namely, we study bidding games that are played on Markov decision processes, where the players bid for the right to choose the next action, which determines the probability distribution according to which the next vertex is chosen. We study parity and meanpayoff bidding games on MDPs and extend results from the deterministic bidding setting to the probabilistic one.}, author = {Avni, Guy and Henzinger, Thomas A and Ibsen-Jensen, Rasmus and Novotny, Petr}, booktitle = {Proceedings of the 13th International Conference of Reachability Problems}, isbn = {978-303030805-6}, issn = {0302-9743}, location = {Brussels, Belgium}, pages = {1--12}, publisher = {Springer}, title = {{Bidding games on Markov decision processes}}, doi = {10.1007/978-3-030-30806-3_1}, volume = {11674}, year = {2019}, } @inproceedings{6528, abstract = {We construct a verifiable delay function (VDF) by showing how the Rivest-Shamir-Wagner time-lock puzzle can be made publicly verifiable. Concretely, we give a statistically sound public-coin protocol to prove that a tuple (N,x,T,y) satisfies y=x2T (mod N) where the prover doesn’t know the factorization of N and its running time is dominated by solving the puzzle, that is, compute x2T, which is conjectured to require T sequential squarings. To get a VDF we make this protocol non-interactive using the Fiat-Shamir heuristic.The motivation for this work comes from the Chia blockchain design, which uses a VDF as akey ingredient. For typical parameters (T≤2 40, N= 2048), our proofs are of size around 10K B, verification cost around three RSA exponentiations and computing the proof is 8000 times faster than solving the puzzle even without any parallelism.}, author = {Pietrzak, Krzysztof Z}, booktitle = {10th Innovations in Theoretical Computer Science Conference}, isbn = {978-3-95977-095-8}, issn = {1868-8969}, location = {San Diego, CA, United States}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Simple verifiable delay functions}}, doi = {10.4230/LIPICS.ITCS.2019.60}, volume = {124}, year = {2019}, } @inproceedings{7401, abstract = {The genus g(G) of a graph G is the minimum g such that G has an embedding on the orientable surface M_g of genus g. A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z_2-genus of a graph G, denoted by g_0(G), is the minimum g such that G has an independently even drawing on M_g. By a result of Battle, Harary, Kodama and Youngs from 1962, the graph genus is additive over 2-connected blocks. In 2013, Schaefer and Stefankovic proved that the Z_2-genus of a graph is additive over 2-connected blocks as well, and asked whether this result can be extended to so-called 2-amalgamations, as an analogue of results by Decker, Glover, Huneke, and Stahl for the genus. We give the following partial answer. If G=G_1 cup G_2, G_1 and G_2 intersect in two vertices u and v, and G-u-v has k connected components (among which we count the edge uv if present), then |g_0(G)-(g_0(G_1)+g_0(G_2))|<=k+1. For complete bipartite graphs K_{m,n}, with n >= m >= 3, we prove that g_0(K_{m,n})/g(K_{m,n})=1-O(1/n). Similar results are proved also for the Euler Z_2-genus. We express the Z_2-genus of a graph using the minimum rank of partial symmetric matrices over Z_2; a problem that might be of independent interest. }, author = {Fulek, Radoslav and Kyncl, Jan}, booktitle = {35th International Symposium on Computational Geometry}, isbn = {978-3-95977-104-7}, issn = {1868-8969}, location = {Portland, OR, United States}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Z_2-Genus of graphs and minimum rank of partial symmetric matrices}}, doi = {10.4230/LIPICS.SOCG.2019.39}, volume = {129}, year = {2019}, } @inproceedings{7437, abstract = {Most of today's distributed machine learning systems assume reliable networks: whenever two machines exchange information (e.g., gradients or models), the network should guarantee the delivery of the message. At the same time, recent work exhibits the impressive tolerance of machine learning algorithms to errors or noise arising from relaxed communication or synchronization. In this paper, we connect these two trends, and consider the following question: Can we design machine learning systems that are tolerant to network unreliability during training? With this motivation, we focus on a theoretical problem of independent interest-given a standard distributed parameter server architecture, if every communication between the worker and the server has a non-zero probability p of being dropped, does there exist an algorithm that still converges, and at what speed? The technical contribution of this paper is a novel theoretical analysis proving that distributed learning over unreliable network can achieve comparable convergence rate to centralized or distributed learning over reliable networks. Further, we prove that the influence of the packet drop rate diminishes with the growth of the number of parameter servers. We map this theoretical result onto a real-world scenario, training deep neural networks over an unreliable network layer, and conduct network simulation to validate the system improvement by allowing the networks to be unreliable.}, author = {Yu, Chen and Tang, Hanlin and Renggli, Cedric and Kassing, Simon and Singla, Ankit and Alistarh, Dan-Adrian and Zhang, Ce and Liu, Ji}, booktitle = {36th International Conference on Machine Learning}, isbn = {9781510886988}, location = {Long Beach, CA, United States}, pages = {12481--12512}, publisher = {IMLS}, title = {{Distributed learning over unreliable networks}}, volume = {2019-June}, year = {2019}, } @inproceedings{10877, abstract = {This report presents the results of a friendly competition for formal verification of continuous and hybrid systems with piecewise constant dynamics. The friendly competition took place as part of the workshop Applied Verification for Continuous and Hybrid Systems (ARCH) in 2019. In this third edition, six tools have been applied to solve five different benchmark problems in the category for piecewise constant dynamics: BACH, Lyse, Hy- COMP, PHAVer/SX, PHAVerLite, and VeriSiMPL. Compared to last year, a new tool has participated (HyCOMP) and PHAVerLite has replaced PHAVer-lite. The result is a snap- shot of the current landscape of tools and the types of benchmarks they are particularly suited for. Due to the diversity of problems, we are not ranking tools, yet the presented results probably provide the most complete assessment of tools for the safety verification of continuous and hybrid systems with piecewise constant dynamics up to this date.}, author = {Frehse, Goran and Abate, Alessandro and Adzkiya, Dieky and Becchi, Anna and Bu, Lei and Cimatti, Alessandro and Giacobbe, Mirco and Griggio, Alberto and Mover, Sergio and Mufid, Muhammad Syifa'ul and Riouak, Idriss and Tonetta, Stefano and Zaffanella, Enea}, booktitle = {6th International Workshop on Applied Verification of Continuous and Hybrid Systems}, editor = {Frehse, Goran and Althoff, Matthias}, issn = {2398-7340}, location = {Montreal, Canada}, pages = {1--13}, publisher = {EasyChair}, title = {{ARCH-COMP19 Category Report: Hybrid systems with piecewise constant dynamics}}, doi = {10.29007/rjwn}, volume = {61}, year = {2019}, } @article{6240, abstract = {For a general class of large non-Hermitian random block matrices X we prove that there are no eigenvalues away from a deterministic set with very high probability. This set is obtained from the Dyson equation of the Hermitization of X as the self-consistent approximation of the pseudospectrum. We demonstrate that the analysis of the matrix Dyson equation from (Probab. Theory Related Fields (2018)) offers a unified treatment of many structured matrix ensembles.}, author = {Alt, Johannes and Erdös, László and Krüger, Torben H and Nemish, Yuriy}, issn = {0246-0203}, journal = {Annales de l'Institut Henri Poincaré, Probabilités et Statistiques}, number = {2}, pages = {661--696}, publisher = {Institut Henri Poincaré}, title = {{Location of the spectrum of Kronecker random matrices}}, doi = {10.1214/18-AIHP894}, volume = {55}, year = {2019}, } @article{6756, abstract = {We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models.}, author = {Pranav, Pratyush and Adler, Robert J. and Buchert, Thomas and Edelsbrunner, Herbert and Jones, Bernard J.T. and Schwartzman, Armin and Wagner, Hubert and Van De Weygaert, Rien}, issn = {1432-0746}, journal = {Astronomy & Astrophysics}, publisher = {EDP Sciences}, title = {{Unexpected topology of the temperature fluctuations in the cosmic microwave background}}, doi = {10.1051/0004-6361/201834916}, volume = {627}, year = {2019}, } @article{22205, abstract = {A group is sofic when every finite subset can be well approximated in a finite symmetric group. No example of a non-sofic group is known. Higman's group, which is a circular amalgamation of four copies of the Baumslag–Solitar group, is a candidate. Here we contribute to the discussion of the problem of its soficity in two ways. We construct variations on Higman's group replacing the Baumslag–Solitar group by other groups G. We give an elementary condition on G enjoyed for example by Z≀Z and the integral Heisenberg group, under which the resulting group is sofic. We then use soficity to deduce that there exist permutations of Z/nZ that are seemingly pathological in that they have order dividing four and yet locally they behave like exponential functions over most of their domains. Our approach is based on that of Helfgott and Juschenko, who recently showed the soficity of Higman's group would imply some the existence of some similarly pathological functions. Our results call into question their suggestion that this might be a step towards proving the existence of a non-sofic group.}, author = {Kassabov, Martin and Kuperberg, Vivian Zieve and Riley, Timothy R.}, issn = {2415-6302}, journal = {Journal of Combinatorial Algebra}, number = {1}, pages = {41--70}, publisher = {European Mathematical Society}, title = {{Soficity and variations on Higman’s group}}, doi = {10.4171/jca/26}, volume = {3}, year = {2019}, } @article{22208, abstract = {The bulk synthesis of fluorescent colloidal SU‐8 polymer rods with tunable dimensions is described. The colloidal SU‐8 rods are prepared by shearing an emulsion of SU‐8 polymer droplets and then exposing the resulting non‐Brownian rods to ultrasonic waves, which breaks them into colloidal rods with typical lengths of 3.5–10 µm and diameters of 0.4–1 µm. The rods are stable in both aqueous and apolar solvents, and by varying the composition of apolar solvent mixtures both the difference in refractive index and mass density between particles and solvent can be independently controlled. Consequently, these colloidal SU‐8 rods can be used in both 3D confocal microscopy and optical trapping experiments while carefully tuning the effect of gravity. This is demonstrated by using confocal microscopy to image the liquid crystalline phases and the isotropic–nematic interface formed by the colloidal SU‐8 rods and by optically trapping single rods in water. Finally, the simultaneous confocal imaging and optical manipulation of multiple SU‐8 rods in the isotropic phase is shown.}, author = {Fernández-Rico, Carla and Yanagishima, Taiki and Curran, Arran and Aarts, Dirk G. A. L. and Dullens, Roel P. A.}, issn = {1521-4095}, journal = {Advanced Materials}, number = {17}, publisher = {Wiley}, title = {{Synthesis of colloidal SU‐8 polymer rods using sonication}}, doi = {10.1002/adma.201807514}, volume = {31}, year = {2019}, } @unpublished{8305, abstract = {In this paper, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual (f,2f+1)−threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption). In order to create a DKG with a dual (f,2f+1)− threshold we first answer in the affirmative the open question posed by Cachin et al. how to create an AVSS protocol with recovery thresholds f+1