nils-herrmann/clean_scirepeval huggingface dataset:
Limits of Ordered Graphs and Images

The emerging theory of graph limits exhibits an interesting analytic perspective on graphs, showing that many important concepts and tools in graph theory and its applications can be described naturally in analytic language. We extend the theory of graph limits to the ordered setting, presenting a limit object for dense vertex-ordered graphs, which we call an orderon. Images are an example of dense ordered bipartite graphs, where the rows and the columns constitute the vertices, and pixel colors are represented by row-column edges; thus, as a special case, we obtain a limit object for images. 
Along the way, we devise an ordered locality-preserving variant of the cut distance between ordered graphs, showing that two graphs are close with respect to this distance if and only if they are similar in terms of their ordered subgraph frequencies. We show that the space of orderons is compact with respect to this distance notion, which is key to a successful analysis of combinatorial objects through their limits. For the proof we combine techniques used in the unordered setting with several new techniques specifically designed to overcome the challenges arising in the ordered setting. We derive several results related to sampling and property testing on ordered graphs and images; For example, we describe how one can use the analytic machinery to obtain a new proof of the ordered graph removal lemma [Alon et al., FOCS 2017].
Entombed: An archaeological examination of an Atari 2600 game

The act and experience of programming is, at its heart, a fundamentally human activity that results in the production of artifacts. When considering programming, therefore, it would be a glaring omission to not involve people who specialize in studying artifacts and the human activity that yields them: archaeologists. Here we consider this with respect to computer games, the focus of archaeology's nascent subarea of archaeogaming. 
One type of archaeogaming research is digital excavation, a technical examination of the code and techniques used in old games' implementation. We apply that in a case study of Entombed, an Atari 2600 game released in 1982 by US Games. The player in this game is, appropriately, an archaeologist who must make their way through a zombie-infested maze. Maze generation is a fruitful area for comparative retrogame archaeology, because a number of early games on different platforms featured mazes, and their variety of approaches can be compared. The maze in Entombed is particularly interesting: it is shaped in part by the extensive real-time constraints of the Atari 2600 platform, and also had to be generated efficiently and use next to no memory. We reverse engineered key areas of the game's code to uncover its unusual maze-generation algorithm, which we have also built a reconstruction of, and analyzed the mysterious table that drives it. In addition, we discovered what appears to be a 35-year-old bug in the code, as well as direct evidence of code-reuse practices amongst game developers. 
What further makes this game's development interesting is that, in an era where video games were typically solo projects, a total of five people were involved in various ways with Entombed. We piece together some of the backstory of the game's development and intoxicant-fueled design using interviews to complement our technical work. 
Finally, we contextualize this example in archaeology and lay the groundwork for a broader interdisciplinary discussion about programming, one that includes both computer scientists and archaeologists.
A description logic framework for commonsense conceptual combination integrating typicality, probabilities and cognitive heuristics

We propose a nonmonotonic Description Logic of typicality able to account for the phenomenon of the combination of prototypical concepts. The proposed logic relies on the logic of typicality , whose semantics is based on the notion of rational closure, as well as on the distributed semantics of probabilistic Description Logics, and is equipped with a cognitive heuristic used by humans for concept composition. We first extend the logic of typicality by typicality inclusions of the form , whose intuitive meaning is that ‘we believe with degree about the fact that typical Cs are Ds’. As in the distributed semantics, we define different scenarios containing only some typicality inclusions, each one having a suitable probability. We then exploit such scenarios in order to ascribe typical properties to a concept obtained as the combination of two prototypical concepts. We also show that reasoning in the proposed Description Logic is ExpTime-complete as for the underlying standard Description Logic .
Proofs of life: molecular-biology reasoning simulates cell behaviors from first principles

We axiomatize the molecular-biology reasoning style, show compliance of the standard reference: Ptashne, A Genetic Switch, and present proof-theory-induced technologies to help infer phenotypes and to predict life cycles from genotypes. The key is to note that `reductionist discipline' entails constructive reasoning: any proof of a compound property can be decomposed to proofs of constituent properties. Proof theory makes explicit the inner structure of the axiomatized reasoning style and allows the permissible dynamics to be presented as a mode of computation that can be executed and analyzed. Constructivity and execution guarantee simulation when working over domain-specific languages. Here, we exhibit phenotype properties for genotype reasons: a molecular-biology argument is an open-system concurrent computation that results in compartment changes and is performed among processes of physiology change as determined from the molecular programming of given DNA. Life cycles are the possible sequentializations of the processes. A main implication of our construction is that formal correctness provides a complementary perspective on science that is as fundamental there as for pure mathematics. The bulk of the presented work has been verified formally correct by computer.
Superregular grammars do not provide additional explanatory power but allow for a compact analysis of animal song

A pervasive belief with regard to the differences between human language and animal vocal sequences (song) is that they belong to different classes of computational complexity, with animal song belonging to regular languages, whereas human language is superregular. This argument, however, lacks empirical evidence since superregular analyses of animal song are understudied. The goal of this paper is to perform a superregular analysis of animal song, using data from gibbons as a case study, and demonstrate that a superregular analysis can be effectively used with non-human data. A key finding is that a superregular analysis does not increase explanatory power but rather provides for compact analysis: fewer grammatical rules are necessary once superregularity is allowed. This pattern is analogous to a previous computational analysis of human language, and accordingly, the null hypothesis, that human language and animal song are governed by the same type of grammatical systems, cannot be rejected.
Category Trees - Classifiers that Branch on Category

This paper presents a batch classifier that splits a dataset into tree branches depending on the category type. It has been improved from the earlier version and fixed a mistake in the earlier paper. Two important changes have been made. The first is to represent each category with a separate classifier. Each classifier then classifies its own subset of data rows, using batch input values to create the centroid and also represent the category itself. If the classifier contains data from more than one category however, it needs to create new classifiers for the incorrect data. The second change therefore is to allow the classifier to branch to new layers when there is a split in the data, and create new classifiers there for the data rows that are incorrectly classified. Each layer can therefore branch like a tree - not for distinguishing features, but for distinguishing categories. The paper then suggests a further innovation, which is to represent some data columns with fixed value ranges, or bands. When considering features, it is shown that some of the data can be classified directly through fixed value ranges, while the rest must be classified using a classifier technique and the idea allows the paper to discuss a biological analogy with neurons and neuron links. Tests show that the method can successfully classify a diverse set of benchmark datasets to better than the state-of-the-art.
Policy Certificates: Towards Accountable Reinforcement Learning

The performance of a reinforcement learning algorithm can vary drastically during learning because of exploration. Existing algorithms provide little information about the quality of their current policy before executing it, and thus have limited use in high-stakes applications like healthcare. We address this lack of accountability by proposing that algorithms output policy certificates. These certificates bound the sub-optimality and return of the policy in the next episode, allowing humans to intervene when the certified quality is not satisfactory. We further introduce two new algorithms with certificates and present a new framework for theoretical analysis that guarantees the quality of their policies and certificates. For tabular MDPs, we show that computing certificates can even improve the sample-efficiency of optimism-based exploration. As a result, one of our algorithms is the first to achieve minimax-optimal PAC bounds up to lower-order terms, and this algorithm also matches (and in some settings slightly improves upon) existing minimax regret bounds.
A post-quantum theory of classical gravity?.

We present a consistent theory of classical gravity coupled to quantum field theory. The dynamics is linear in the density matrix, completely positive and trace-preserving, and reduces to Einstein's equations in the classical limit. The constraints of general relativity are imposed as a symmetry on the equations of motion. The assumption that gravity is classical necessarily modifies the dynamical laws of quantum mechanics -- the theory must be fundamentally stochastic involving finite sized and probabilistic jumps in space-time and in the quantum field. Nonetheless the quantum state of the system can remain pure conditioned on the classical degrees of freedom. The measurement postulate of quantum mechanics is not needed since the interaction of the quantum degrees of freedom with classical space-time necessarily causes collapse of the wave-function. More generally, we derive a form of classical-quantum dynamics using a non-commuting divergence which has as its limit deterministic classical Hamiltonian evolution, and which doesn't suffer from the pathologies of the semi-classical theory.
Biologically-plausible learning algorithms can scale to large datasets

The backpropagation (BP) algorithm is often thought to be biologically implausible in the brain. One of the main reasons is that BP requires symmetric weight matrices in the feedforward and feedback pathways. To address this "weight transport problem" (Grossberg, 1987), two more biologically plausible algorithms, proposed by Liao et al. (2016) and Lillicrap et al. (2016), relax BP's weight symmetry requirements and demonstrate comparable learning capabilities to that of BP on small datasets. However, a recent study by Bartunov et al. (2018) evaluate variants of target-propagation (TP) and feedback alignment (FA) on MINIST, CIFAR, and ImageNet datasets, and find that although many of the proposed algorithms perform well on MNIST and CIFAR, they perform significantly worse than BP on ImageNet. Here, we additionally evaluate the sign-symmetry algorithm (Liao et al., 2016), which differs from both BP and FA in that the feedback and feedforward weights share signs but not magnitudes. We examine the performance of sign-symmetry and feedback alignment on ImageNet and MS COCO datasets using different network architectures (ResNet-18 and AlexNet for ImageNet, RetinaNet for MS COCO). Surprisingly, networks trained with sign-symmetry can attain classification performance approaching that of BP-trained networks. These results complement the study by Bartunov et al. (2018), and establish a new benchmark for future biologically plausible learning algorithms on more difficult datasets and more complex architectures.
Scale-variant topological information for characterizing complex networks

The structure of real-world networks is usually difficult to characterize owing to the variation of topological scales, the nondyadic complex interactions, and the fluctuations in the network. We aim to address these problems by introducing a general framework using a method based on topological data analysis. By considering the diffusion process at a single specified timescale in a network, we map the network nodes to a finite set of points that contains the topological information of the network at a single scale. Subsequently, we study the shape of these point sets over variable timescales that provide scale-variant topological information, to understand the varying topological scales and the complex interactions in the network. We conduct experiments on synthetic and real-world data to demonstrate the effectiveness of the proposed framework in identifying network models, classifying real-world networks, and detecting transition points in time-evolving networks. Overall, our study presents a unified analysis that can be applied to more complex network structures, as in the case of multilayer and multiplex networks.
Spatter: A Benchmark Suite for Evaluating Sparse Access Patterns

Recent characterizations of data movement performance have evaluated optimizations for dense and blocked accesses used by accelerators like GPUs and Xeon Phi, but sparse access patterns like scatter and gather are still not well understood across current and emerging architectures. We propose a tunable benchmark suite, Spatter, that allows users to characterize scatter, gather, and related sparse access patterns at a low level across multiple backends, including CUDA, OpenCL, and OpenMP. Spatter also allows users to vary the block size and amount of data that is moved to create a more comprehensive picture of sparse access patterns and to model patterns that are found in real applications. With Spatter we aim to characterize the performance of memory systems in a novel way by evaluating how the density of accesses compares against real-world effective memory bandwidths (measured by STREAM) and how it can be compared across widely varying architectures including GPUs and x86, ARM, and Power CPUs. We demonstrate how Spatter can be used to generate analysis plots comparing different architectures and show that current GPU systems achieve up to 65% of STREAM bandwidth for sparse accesses and are more energy efficient in doing so for several different sparsity patterns. Our future plans for the spatter benchmark are to use these results to predict the impact of new memory access primitives on various architectures, develop backends for novel hardware like FPGAs and the Emu Chick, and automate testing so that users can perform their own sparse access studies.
Two-dimensional topological quantum walks in the momentum space of structured light

Quantum walks are powerful tools for quantum applications and for designing topological systems. Although they are simulated in a variety of platforms, genuine two-dimensional realizations are still challenging. Here we present an innovative approach to the photonic simulation of a quantum walk in two dimensions, where walker positions are encoded in the transverse-wavevector component of a single light beam. The desired dynamics is obtained by means of a sequence of liquid-crystal devices, which apply polarization-dependent transverse “kicks” to the photons in the beam. We engineer our quantum walk so that it realizes a periodically driven Chern insulator, and we probe its topological features by detecting the anomalous displacement of the photonic wavepacket under the effect of a constant force. Our compact, versatile platform offers exciting prospects for the photonic simulation of two-dimensional quantum dynamics and topological systems.
SLANG: Fast Structured Covariance Approximations for Bayesian Deep Learning with Natural Gradient

Uncertainty estimation in large deep-learning models is a computationally challenging task, where it is difficult to form even a Gaussian approximation to the posterior distribution. In such situations, existing methods usually resort to a diagonal approximation of the covariance matrix despite the fact that these matrices are known to give poor uncertainty estimates. To address this issue, we propose a new stochastic, low-rank, approximate natural-gradient (SLANG) method for variational inference in large deep models. Our method estimates a “diagonal plus low-rank” structure based solely on back-propagated gradients of the network log-likelihood. This requires strictly less gradient computations than methods that compute the gradient of the whole variational objective. Empirical evaluations on standard benchmarks confirm that SLANG enables faster and more accurate estimation of uncertainty than mean-field methods, and performs comparably to state-of-the-art methods.
Fine-tuning of Language Models with Discriminator

Cross-entropy loss is a common choice when it comes to multiclass classification tasks and language modeling in particular. Minimizing this loss results in language models of very good quality. We show that it is possible to fine-tune these models and make them perform even better if they are fine-tuned with sum of cross-entropy loss and reverse Kullback-Leibler divergence. The latter is estimated using discriminator network that we train in advance. During fine-tuning we can use this discriminator to figure out if probabilities of some words are overestimated and reduce them in this case. The novel approach that we propose allows us to reach state-of-the-art quality on Penn TreeBank: perplexity of the fine-tuned model drops down by more than 0.5 and is now below 54.0 in standard evaluation setting; however, in dynamic evaluation framework the improvement is much less perceptible. Our fine-tuning algorithm is rather fast and requires almost no hyperparameter tuning. We test it on different datasets including WikiText-2 and large-scale dataset. In the former case we also reach state-of-the-art results.
Neutrino-Based Tools for Nuclear Verification and Diplomacy in North Korea

We present neutrino-based options for verifying that the nuclear reactors at North Korea’s Yongbyon Nuclear Research Center are no longer operating or that they are operating in an agreed manner, precluding weapons production. Neutrino detectors may be a mutually agreeable complement to traditional verification protocols because they do not require access inside reactor buildings, could be installed collaboratively, and provide persistent and specific observations. At Yongbyon, neutrino detectors could passively verify reactor shutdowns or monitor power levels and plutonium contents, all from outside the reactor buildings. The monitoring options presented here build on recent successes in basic particle physics. Following a dedicated design study, these tools could be deployed in as little as one year at a reasonable cost. In North Korea, cooperative deployment of neutrino detectors could help redirect a limited number of scientists and engineers from military applications to peaceful technical work in an international community. Opportunities for scientific collaboration with South Korea are especially strong. We encourage policymakers to consider collaborative neutrino projects within a broader program of action toward stability and security on the Korean Peninsula.
SAGE: finding IMBH in the black hole desert

SAGE (SagnAc interferometer for Gravitational wavE) is a project for a space observatory based on multiple 12-U CubeSats in geosynchronous equatorial orbit. The objective is a fast track mission which would fill the observational gap between LISA and ground based observatories. With albeit a lower sensitivity, it would allow early investigation of the nature and event rate of intermediate-mass black hole (IMBH) mergers, constraining our understanding of the universe formation by probing the building up of IMBH up to supermassive black holes (SMBH). Technically, the CubeSats would create a triangular Sagnac interferometer with 140.000 km roundtrip arm length, optimised to be sensitive to gravitational waves at frequencies between 10 mHz and 2 Hz. The nature of the Sagnac measurement makes it almost insensitive to position error, a feature enabling the use of spacecrafts in ballistic trajectories instead of perfect free fall. The light source and recombination units of the interferometer are based on compact fibered technologies without bulk optics. A peak sensitivity of 23 pm ()−1 is expected at 1 Hz assuming a 200 mW internal laser source and 10-centimeter diameter apertures. Because of the absence of a test mass, the main limitation would come from the non-gravitational forces applied on the spacecrafts. However, conditionally upon our ability to partially post-process the effect of solar wind and solar pressure, SAGE would allow detection of gravitational waves with strains as low as a few 10−19 within the 0.1 to 1 Hz range. Averaged over the entire sky, and including the antenna gain of the Sagnac interferometer, the SAGE observatory would sense equal mass black hole mergers in the 104 to 106 solar masses range up to a luminosity distance of 800 Mpc. Additionally, coalescence of stellar black holes (10 M) around SMBH (IMBH) forming extreme (intermediate) mass ratio inspirals could be detected within a sphere of radius 200 Mpc.
Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension

We construct an efficient classical analogue of the quantum matrix inversion algorithm [HHL09] for low-rank matrices. Inspired by recent work of Tang [Tan18a], assuming length-square sampling access to input data, we implement the pseudo-inverse of a low-rank matrix and sample from the solution to the problem Ax = b using fast sampling techniques. We implement the