Top linked arXiv articles

View breakdown by




1.
Acquisition of Chess Knowledge in AlphaZero (arxiv.org) Abstract ↓
What is learned by sophisticated neural network agents such as AlphaZero? This question is of both scientific and practical interest. If the representations of strong neural networks bear no resemblance to human concepts, our ability to understand faithful explanations of their decisions will be restricted, ultimately limiting what we can achieve with neural network interpretability. In this work we provide evidence that human knowledge is acquired by the AlphaZero neural network as it trains on the game of chess. By probing for a broad range of human chess concepts we show when and where these concepts are represented in the AlphaZero network. We also provide a behavioural analysis focusing on opening play, including qualitative analysis from chess Grandmaster Vladimir Kramnik. Finally, we carry out a preliminary investigation looking at the low-level details of AlphaZero's representations, and make the resulting behavioural and representational analyses available online.
2.
Language Models are Few-Shot Learners (arxiv.org) Abstract ↓
Recent work has demonstrated substantial gains on many NLP tasks and benchmarks by pre-training on a large corpus of text followed by fine-tuning on a specific task. While typically task-agnostic in architecture, this method still requires task-specific fine-tuning datasets of thousands or tens of thousands of examples. By contrast, humans can generally perform a new language task from only a few examples or from simple instructions - something which current NLP systems still largely struggle to do. Here we show that scaling up language models greatly improves task-agnostic, few-shot performance, sometimes even reaching competitiveness with prior state-of-the-art fine-tuning approaches. Specifically, we train GPT-3, an autoregressive language model with 175 billion parameters, 10x more than any previous non-sparse language model, and test its performance in the few-shot setting. For all tasks, GPT-3 is applied without any gradient updates or fine-tuning, with tasks and few-shot demonstrations specified purely via text interaction with the model. GPT-3 achieves strong performance on many NLP datasets, including translation, question-answering, and cloze tasks, as well as several tasks that require on-the-fly reasoning or domain adaptation, such as unscrambling words, using a novel word in a sentence, or performing 3-digit arithmetic. At the same time, we also identify some datasets where GPT-3's few-shot learning still struggles, as well as some datasets where GPT-3 faces methodological issues related to training on large web corpora. Finally, we find that GPT-3 can generate samples of news articles which human evaluators have difficulty distinguishing from articles written by humans. We discuss broader societal impacts of this finding and of GPT-3 in general.
3.
A Simple Proof of the Quadratic Formula (arxiv.org) Abstract ↓
This article provides a simple proof of the quadratic formula, which also produces an efficient and natural method for solving general quadratic equations. The derivation is computationally light and conceptually natural, and has the potential to demystify quadratic equations for students worldwide.
4.
Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer (arxiv.org) Abstract ↓
We develop a high-performance tensor-based simulator for random quantum circuits(RQCs) on the new Sunway supercomputer. Our major innovations include: (1) a near-optimal slicing scheme, and a path-optimization strategy that considers both complexity and compute density; (2) a three-level parallelization scheme that scales to about 42 million cores; (3) a fused permutation and multiplication design that improves the compute efficiency for a wide range of tensor contraction scenarios; and (4) a mixed-precision scheme to further improve the performance. Our simulator effectively expands the scope of simulatable RQCs to include the 10*10(qubits)*(1+40+1)(depth) circuit, with a sustained performance of 1.2 Eflops (single-precision), or 4.4 Eflops (mixed-precision)as a new milestone for classical simulation of quantum circuits; and reduces the simulation sampling time of Google Sycamore to 304 seconds, from the previously claimed 10,000 years.
5.
Containment Control for a Social Network with State-Dependent Connectivity (arxiv.org) Abstract ↓
Social interactions influence our thoughts, opinions and actions. In this paper, social interactions are studied within a group of individuals composed of influential social leaders and followers. Each person is assumed to maintain a social state, which can be an emotional state or an opinion. Followers update their social states based on the states of local neighbors, while social leaders maintain a constant desired state. Social interactions are modeled as a general directed graph where each directed edge represents an influence from one person to another. Motivated by the non-local property of fractional-order systems, the social response of individuals in the network are modeled by fractional-order dynamics whose states depend on influences from local neighbors and past experiences. A decentralized influence method is then developed to maintain existing social influence between individuals (i.e., without isolating peers in the group) and to influence the social group to a common desired state (i.e., within a convex hull spanned by social leaders). Mittag-Leffler stability methods are used to prove asymptotic stability of the networked fractional-order system.
6.
Demonstration of Communication using Neutrinos (arxiv.org) Abstract ↓
Beams of neutrinos have been proposed as a vehicle for communications under unusual circumstances, such as direct point-to-point global communication, communication with submarines, secure communications and interstellar communication. We report on the performance of a low-rate communications link established using the NuMI beam line and the MINERvA detector at Fermilab. The link achieved a decoded data rate of 0.1 bits/sec with a bit error rate of 1% over a distance of 1.035 km, including 240 m of earth.
7.
Dependency Solving Is Still Hard, but We Are Getting Better at It (arxiv.org) Abstract ↓
Dependency solving is a hard (NP-complete) problem in all non-trivial component models due to either mutually incompatible versions of the same packages or explicitly declared package conflicts. As such, software upgrade planning needs to rely on highly specialized dependency solvers, lest falling into pitfalls such as incompleteness-a combination of package versions that satisfy dependency constraints does exist, but the package manager is unable to find it. In this paper we look back at proposals from dependency solving research dating back a few years. Specifically, we review the idea of treating dependency solving as a separate concern in package manager implementations, relying on generic dependency solvers based on tried and tested techniques such as SAT solving, PBO, MILP, etc. By conducting a census of dependency solving capabilities in state-of-the-art package managers we conclude that some proposals are starting to take off (e.g., SAT-based dependency solving) while-with few exceptions-others have not (e.g., out-sourcing dependency solving to reusable components). We reflect on why that has been the case and look at novel challenges for dependency solving that have emerged since.
8.
Locally Testable Codes with constant rate, distance, and locality (arxiv.org) Abstract ↓
A locally testable code (LTC) is an error-correcting code that has a property-tester. The tester reads $q$ bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter $q$ is called the locality of the tester. LTCs were initially studied as important components of PCPs, and since then the topic has evolved on its own. High rate LTCs could be useful in practice: before attempting to decode a received word, one can save time by first quickly testing if it is close to the code. An outstanding open question has been whether there exist "$c^3$-LTCs", namely LTCs with *c*onstant rate, *c*onstant distance, and *c*onstant locality. In this work we construct such codes based on a new two-dimensional complex which we call a left-right Cayley complex. This is essentially a graph which, in addition to vertices and edges, also has squares. Our codes can be viewed as a two-dimensional version of (the one-dimensional) expander codes, where the codewords are functions on the squares rather than on the edges.
9.
DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning (arxiv.org) Abstract ↓
Expert problem-solving is driven by powerful languages for thinking about problems and their solutions. Acquiring expertise means learning these languages -- systems of concepts, alongside the skills to use them. We present DreamCoder, a system that learns to solve problems by writing programs. It builds expertise by creating programming languages for expressing domain concepts, together with neural networks to guide the search for programs within these languages. A ``wake-sleep'' learning algorithm alternately extends the language with new symbolic abstractions and trains the neural network on imagined and replayed problems. DreamCoder solves both classic inductive programming tasks and creative tasks such as drawing pictures and building scenes. It rediscovers the basics of modern functional programming, vector algebra and classical physics, including Newton's and Coulomb's laws. Concepts are built compositionally from those learned earlier, yielding multi-layered symbolic representations that are interpretable and transferrable to new tasks, while still growing scalably and flexibly with experience.
10.
KML: Using Machine Learning to Improve Storage Systems (arxiv.org) Abstract ↓
Operating systems include many heuristic algorithms designed to improve overall storage performance and throughput. Because such heuristics cannot work well for all conditions and workloads, system designers resorted to exposing numerous tunable parameters to users -- essentially burdening users with continually optimizing their own storage systems and applications. Storage systems are usually responsible for most latency in I/O heavy applications, so even a small overall latency improvement can be significant. Machine learning (ML) techniques promise to learn patterns, generalize from them, and enable optimal solutions that adapt to changing workloads. We propose that ML solutions become a first-class component in OSs and replace manual heuristics to optimize storage systems dynamically. In this paper, we describe our proposed ML architecture, called KML. We developed a prototype KML architecture and applied it to two problems: optimal readahead and NFS read-size values. Our experiments show that KML consumes little OS resources, adds negligible latency, and yet can learn patterns that can improve I/O throughput by as much as 2.3x or 15x for the two use cases respectively -- even for complex, never-before-seen, concurrently running mixed workloads on different storage devices.
11.
Mithril: Cooperative Row Hammer Protection on Commodity DRAM Leveraging Managed Refresh (arxiv.org) Abstract ↓
Since its public introduction in the mid-2010s, the Row Hammer (RH) phenomenon has drawn significant attention from the research community due to its security implications. Although many RH-protection schemes have been proposed by processor vendors, DRAM manufacturers, and academia, they still have shortcomings. Solutions implemented in the memory controller (MC) pay an increasingly higher cost due to their conservative design for the worst case in terms of the number of DRAM banks and RH threshold to support. Meanwhile, the DRAM-side implementation has a limited time margin for RH protection measures or requires extensive modifications to the standard DRAM interface. Recently, a new command for RH protection has been introduced in the DDR5/LPDDR5 standards, called refresh management (RFM). RFM enables the separation of the tasks for RH protection to both MC and DRAM. It does so by having the former generate an RFM command at a specific activation frequency, and the latter take proper RH protection measures within a given time window. Although promising, no existing study presents and analyzes RFM-based solutions for RH protection. In this paper, we propose Mithril, the first RFM interface-compatible, DRAM-MC cooperative RH protection scheme providing deterministic protection guarantees. Mithril has minimal energy overheads for common use cases without adversarial memory access patterns. We also introduce Mithril+, an extension to provide minimal performance overheads at the expense of a tiny modification to the MC while utilizing an existing DRAM command.
12.
Crowd Disasters as Systemic Failures: Analysis of the Love Parade Disaster (arxiv.org) Abstract ↓
Each year, crowd disasters happen in different areas of the world. How and why do such disasters happen? Are the fatalities caused by relentless behavior of people or a psychological state of panic that makes the crowd 'go mad'? Or are they a tragic consequence of a breakdown of coordination? These and other questions are addressed, based on a qualitative analysis of publicly available videos and materials, which document the planning and organization of the Love Parade in Duisburg, Germany, and the crowd disaster on July 24, 2010. Our analysis reveals a number of misunderstandings that have widely spread. We also provide a new perspective on concepts such as 'intentional pushing', 'mass panic', 'stampede', and 'crowd crushs'. The focus of our analysis is on the contributing causal factors and their mutual interdependencies, not on legal issues or the judgment of personal or institutional responsibilities. Video recordings show that, in Duisburg, people stumbled and piled up due to a 'domino effect', resulting from a phenomenon called 'crowd turbulence' or 'crowd quake'. Crowd quakes are a typical reason for crowd disasters, to be distinguished from crowd disasters resulting from 'panic stampedes' or 'crowd crushes'. In Duisburg, crowd turbulence was the consequence of amplifying feedback and cascading effects, which are typical for systemic instabilities. Accordingly, things can go terribly wrong in spite of no bad intentions from anyone. Comparing the incident in Duisburg with others, we give recommendations to help prevent future crowd disasters. In particular, we introduce a new scale to assess the criticality of conditions in the crowd. This may allow preventative measures to be taken earlier on. Furthermore, we discuss the merits and limitations of citizen science for public investigation, considering that today, almost every event is recorded and reflected in the World Wide Web.
13.
Evaluating Large Language Models Trained on Code (arxiv.org) Abstract ↓
We introduce Codex, a GPT language model fine-tuned on publicly available code from GitHub, and study its Python code-writing capabilities. A distinct production version of Codex powers GitHub Copilot. On HumanEval, a new evaluation set we release to measure functional correctness for synthesizing programs from docstrings, our model solves 28.8% of the problems, while GPT-3 solves 0% and GPT-J solves 11.4%. Furthermore, we find that repeated sampling from the model is a surprisingly effective strategy for producing working solutions to difficult prompts. Using this method, we solve 70.2% of our problems with 100 samples per problem. Careful investigation of our model reveals its limitations, including difficulty with docstrings describing long chains of operations and with binding operations to variables. Finally, we discuss the potential broader impacts of deploying powerful code generation technologies, covering safety, security, and economics.
14.
Fault-tolerant operation of a logical qubit in a diamond quantum processor (arxiv.org) Abstract ↓
Solid-state spin qubits are a promising platform for quantum computation and quantum networks. Recent experiments have demonstrated high-quality control over multi-qubit systems, elementary quantum algorithms and non-fault-tolerant error correction. Large-scale systems will require using error-corrected logical qubits that are operated fault-tolerantly, so that reliable computation is possible despite noisy operations. Overcoming imperfections in this way remains a major outstanding challenge for quantum science. Here, we demonstrate fault-tolerant operations on a logical qubit using spin qubits in diamond. Our approach is based on the 5-qubit code with a recently discovered flag protocol that enables fault-tolerance using a total of seven qubits. We encode the logical qubit using a novel protocol based on repeated multi-qubit measurements and show that it outperforms non-fault-tolerant encoding schemes. We then fault-tolerantly manipulate the logical qubit through a complete set of single-qubit Clifford gates. Finally, we demonstrate flagged stabilizer measurements with real-time processing of the outcomes. Such measurements are a primitive for fault-tolerant quantum error correction. While future improvements in fidelity and the number of qubits will be required, our realization of fault-tolerant protocols on the logical-qubit level is a key step towards large-scale quantum information processing based on solid-state spins.
15.
Are adversarial examples inevitable? (arxiv.org) Abstract ↓
A wide range of defenses have been proposed to harden neural networks against adversarial attacks. However, a pattern has emerged in which the majority of adversarial defenses are quickly broken by new attacks. Given the lack of success at generating robust defenses, we are led to ask a fundamental question: Are adversarial attacks inevitable? This paper analyzes adversarial examples from a theoretical perspective, and identifies fundamental bounds on the susceptibility of a classifier to adversarial attacks. We show that, for certain classes of problems, adversarial examples are inescapable. Using experiments, we explore the implications of theoretical guarantees for real-world problems and discuss how factors such as dimensionality and image complexity limit a classifier's robustness against adversarial examples.
16.
Cross-platform programming model for many-core lattice Boltzmann simulations (arxiv.org) Abstract ↓
We present a novel, hardware-agnostic implementation strategy for lattice Boltzmann (LB) simulations, which yields massive performance on homogeneous and heterogeneous many-core platforms. Based solely on C++17 Parallel Algorithms, our approach does not rely on any language extensions, external libraries, vendor-specific code annotations, or pre-compilation steps. Thanks in particular to a recently proposed GPU back-end to C++17 Parallel Algorithms, it is shown that a single code can compile and reach state-of-the-art performance on both many-core CPU and GPU environments for the solution of a given non trivial fluid dynamics problem. The proposed strategy is tested with six different, commonly used implementation schemes to test the performance impact of memory access patterns on different platforms. Nine different LB collision models are included in the tests and exhibit good performance, demonstrating the versatility of our parallel approach. This work shows that it is less than ever necessary to draw a distinction between research and production software, as a concise and generic LB implementation yields performances comparable to those achievable in a hardware specific programming language. The results also highlight the gains of performance achieved by modern many-core CPUs and their apparent capability to narrow the gap with the traditionally massively faster GPU platforms. All code is made available to the community in form of the open-source project "stlbm", which serves both as a stand-alone simulation software and as a collection of reusable patterns for the acceleration of pre-existing LB codes.
17.
Systematic Analysis of Programming Languages and Their Execution Environments for Spectre Attacks (arxiv.org) Abstract ↓
In this paper, we analyze the security of programming languages and their execution environments (compilers and interpreters) with respect to Spectre attacks. The analysis shows that only 16 out of 42 execution environments have mitigations against at least one Spectre variant, i.e., 26 have no mitigations against any Spectre variant. Using our novel tool Speconnector, we develop Spectre proof-of-concept attacks in 8 programming languages and on code generated by 11 execution environments that were previously not known to be affected. Our results highlight some programming languages that are used to implement security-critical code, but remain entirely unprotected, even three years after the discovery of Spectre.
18.
A Theoretical Analysis of the Repetition Problem in Text Generation (arxiv.org) Abstract ↓
Text generation tasks, including translation, summarization, language models, and etc. see rapid growth during recent years. Despite the remarkable achievements, the repetition problem has been observed in nearly all text generation models undermining the generation performance extensively. To solve the repetition problem, many methods have been proposed, but there is no existing theoretical analysis to show why this problem happens and how it is resolved. In this paper, we propose a new framework for theoretical analysis for the repetition problem. We first define the Average Repetition Probability (ARP) to characterize the repetition problem quantitatively. Then, we conduct an extensive analysis of the Markov generation model and derive several upper bounds of the average repetition probability with intuitive understanding. We show that most of the existing methods are essentially minimizing the upper bounds explicitly or implicitly. Grounded on our theory, we show that the repetition problem is, unfortunately, caused by the traits of our language itself. One major reason is attributed to the fact that there exist too many words predicting the same word as the subsequent word with high probability. Consequently, it is easy to go back to that word and form repetitions and we dub it as the high inflow problem. Furthermore, we derive a concentration bound of the average repetition probability for a general generation model. Finally, based on the theoretical upper bounds, we propose a novel rebalanced encoding approach to alleviate the high inflow problem. The experimental results show that our theoretical framework is applicable in general generation models and our proposed rebalanced encoding approach alleviates the repetition problem significantly. The source code of this paper can be obtained from https://github.com/fuzihaofzh/repetition-problem-nlg.
19.
TRRespass: Exploiting the Many Sides of Target Row Refresh (arxiv.org) Abstract ↓
After a plethora of high-profile RowHammer attacks, CPU and DRAM vendors scrambled to deliver what was meant to be the definitive hardware solution against the RowHammer problem: Target Row Refresh (TRR). A common belief among practitioners is that, for the latest generation of DDR4 systems that are protected by TRR, RowHammer is no longer an issue in practice. However, in reality, very little is known about TRR. In this paper, we demystify the inner workings of TRR and debunk its security guarantees. We show that what is advertised as a single mitigation mechanism is actually a series of different solutions coalesced under the umbrella term TRR. We inspect and disclose, via a deep analysis, different existing TRR solutions and demonstrate that modern implementations operate entirely inside DRAM chips. Despite the difficulties of analyzing in-DRAM mitigations, we describe novel techniques for gaining insights into the operation of these mitigation mechanisms. These insights allow us to build TRRespass, a scalable black-box RowHammer fuzzer. TRRespass shows that even the latest generation DDR4 chips with in-DRAM TRR, immune to all known RowHammer attacks, are often still vulnerable to new TRR-aware variants of RowHammer that we develop. In particular, TRRespass finds that, on modern DDR4 modules, RowHammer is still possible when many aggressor rows are used (as many as 19 in some cases), with a method we generally refer to as Many-sided RowHammer. Overall, our analysis shows that 13 out of the 42 modules from all three major DRAM vendors are vulnerable to our TRR-aware RowHammer access patterns, and thus one can still mount existing state-of-the-art RowHammer attacks. In addition to DDR4, we also experiment with LPDDR4 chips and show that they are susceptible to RowHammer bit flips too. Our results provide concrete evidence that the pursuit of better RowHammer mitigations must continue.
20.
Ansor : Generating High-Performance Tensor Programs for Deep Learning (arxiv.org) Abstract ↓
High-performance tensor programs are crucial to guarantee efficient execution of deep neural networks. However, obtaining performant tensor programs for different operators on various hardware platforms is notoriously challenging. Currently, deep learning systems rely on vendor-provided kernel libraries or various search strategies to get performant tensor programs. These approaches either require significant engineering effort to develop platform-specific optimization code or fall short of finding high-performance programs due to restricted search space and ineffective exploration strategy. We present Ansor, a tensor program generation framework for deep learning applications. Compared with existing search strategies, Ansor explores many more optimization combinations by sampling programs from a hierarchical representation of the search space. Ansor then fine-tunes the sampled programs with evolutionary search and a learned cost model to identify the best programs. Ansor can find high-performance programs that are outside the search space of existing state-of-the-art approaches. In addition, Ansor utilizes a task scheduler to simultaneously optimize multiple subgraphs in deep neural networks. We show that Ansor improves the execution performance of deep neural networks relative to the state-of-the-art on the Intel CPU, ARM CPU, and NVIDIA GPU by up to $3.8\times$, $2.6\times$, and $1.7\times$, respectively.
21.
The signature and cusp geometry of hyperbolic knots (arxiv.org) Abstract ↓
We introduce a new real-valued invariant called the natural slope of a hyperbolic knot in the 3-sphere, which is defined in terms of its cusp geometry. We show that twice the knot signature and the natural slope differ by at most a constant times the hyperbolic volume divided by the cube of the injectivity radius. This inequality was discovered using machine learning to detect relationships between various knot invariants. It has applications to Dehn surgery and to 4-ball genus. We also show a refined version of the inequality where the upper bound is a linear function of the volume, and the slope is corrected by terms corresponding to short geodesics that link the knot an odd number of times.
22.
Mention Memory: incorporating textual knowledge into Transformers through entity mention attention (arxiv.org) Abstract ↓
Natural language understanding tasks such as open-domain question answering often require retrieving and assimilating factual information from multiple sources. We propose to address this problem by integrating a semi-parametric representation of a large text corpus into a Transformer model as a source of factual knowledge. Specifically, our method represents knowledge with `mention memory', a table of dense vector representations of every entity mention in a corpus. The proposed model - TOME - is a Transformer that accesses the information through internal memory layers in which each entity mention in the input passage attends to the mention memory. This approach enables synthesis of and reasoning over many disparate sources of information within a single Transformer model. In experiments using a memory of 150 million Wikipedia mentions, TOME achieves strong performance on several open-domain knowledge-intensive tasks, including the claim verification benchmarks HoVer and FEVER and several entity-based QA benchmarks. We also show that the model learns to attend to informative mentions without any direct supervision. Finally we demonstrate that the model can generalize to new unseen entities by updating the memory without retraining.
23.
Are We Susceptible to Rowhammer? An End-to-End Methodology for Cloud Providers (arxiv.org) Abstract ↓
Cloud providers are concerned that Rowhammer poses a potentially critical threat to their servers, yet today they lack a systematic way to test whether the DRAM used in their servers is vulnerable to Rowhammer attacks. This paper presents an end-to-end methodology to determine if cloud servers are susceptible to these attacks. With our methodology, a cloud provider can construct worst-case testing conditions for DRAM. We apply our methodology to three classes of servers from a major cloud provider. Our findings show that none of the CPU instruction sequences used in prior work to mount Rowhammer attacks create worst-case DRAM testing conditions. To address this limitation, we develop an instruction sequence that leverages microarchitectural side-effects to ``hammer'' DRAM at a near-optimal rate on modern Intel Skylake and Cascade Lake platforms. We also design a DDR4 fault injector that can reverse engineer row adjacency for any DDR4 DIMM. When applied to our cloud provider's DIMMs, we find that DRAM rows do not always follow a linear map.
24.
Quantifying social organization and political polarization in online platforms (arxiv.org) Abstract ↓
Optimism about the Internet's potential to bring the world together has been tempered by concerns about its role in inflaming the 'culture wars'. Via mass selection into like-minded groups, online society may be becoming more fragmented and polarized, particularly with respect to partisan differences. However, our ability to measure the social makeup of online communities, and in turn understand the social organization of online platforms, is limited by the pseudonymous, unstructured, and large-scale nature of digital discussion. We develop a neural embedding methodology to quantify the positioning of online communities along social dimensions by leveraging large-scale patterns of aggregate behaviour. Applying our methodology to 5.1B Reddit comments made in 10K communities over 14 years, we measure how the macroscale community structure is organized with respect to age, gender, and U.S. political partisanship. Examining political content, we find Reddit underwent a significant polarization event around the 2016 U.S. presidential election, and remained highly polarized for years afterward. Contrary to conventional wisdom, however, individual-level polarization is rare; the system-level shift in 2016 was disproportionately driven by the arrival of new and newly political users. Political polarization on Reddit is unrelated to previous activity on the platform, and is instead temporally aligned with external events. We also observe a stark ideological asymmetry, with the sharp increase in 2016 being entirely attributable to changes in right-wing activity. Our methodology is broadly applicable to the study of online interaction, and our findings have implications for the design of online platforms, understanding the social contexts of online behaviour, and quantifying the dynamics and mechanisms of online polarization.
25.
On the Measure of Intelligence (arxiv.org) Abstract ↓
To make deliberate progress towards more intelligent and more human-like artificial systems, we need to be following an appropriate feedback signal: we need to be able to define and evaluate intelligence in a way that enables comparisons between two systems, as well as comparisons with humans. Over the past hundred years, there has been an abundance of attempts to define and measure intelligence, across both the fields of psychology and AI. We summarize and critically assess these definitions and evaluation approaches, while making apparent the two historical conceptions of intelligence that have implicitly guided them. We note that in practice, the contemporary AI community still gravitates towards benchmarking intelligence by comparing the skill exhibited by AIs and humans at specific tasks such as board games and video games. We argue that solely measuring skill at any given task falls short of measuring intelligence, because skill is heavily modulated by prior knowledge and experience: unlimited priors or unlimited training data allow experimenters to "buy" arbitrary levels of skills for a system, in a way that masks the system's own generalization power. We then articulate a new formal definition of intelligence based on Algorithmic Information Theory, describing intelligence as skill-acquisition efficiency and highlighting the concepts of scope, generalization difficulty, priors, and experience. Using this definition, we propose a set of guidelines for what a general AI benchmark should look like. Finally, we present a benchmark closely following these guidelines, the Abstraction and Reasoning Corpus (ARC), built upon an explicit set of priors designed to be as close as possible to innate human priors. We argue that ARC can be used to measure a human-like form of general fluid intelligence and that it enables fair general intelligence comparisons between AI systems and humans.
26.
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (arxiv.org) Abstract ↓
We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Eker{\aa}-H{\aa}stad 2017, Eker{\aa} 2017, Eker{\aa} 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of $10^{-3}$, a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses $3 n + 0.002 n \lg n$ logical qubits, $0.3 n^3 + 0.0005 n^3 \lg n$ Toffolis, and $500 n^2 + n^2 \lg n$ measurement depth to factor $n$-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.
27.
Faster Policy Learning with Continuous-Time Gradients (arxiv.org) Abstract ↓
We study the estimation of policy gradients for continuous-time systems with known dynamics. By reframing policy learning in continuous-time, we show that it is possible construct a more efficient and accurate gradient estimator. The standard back-propagation through time estimator (BPTT) computes exact gradients for a crude discretization of the continuous-time system. In contrast, we approximate continuous-time gradients in the original system. With the explicit goal of estimating continuous-time gradients, we are able to discretize adaptively and construct a more efficient policy gradient estimator which we call the Continuous-Time Policy Gradient (CTPG). We show that replacing BPTT policy gradients with more efficient CTPG estimates results in faster and more robust learning in a variety of control tasks and simulators.
28.
Generalized Riemann Hypothesis and Stochastic Time Series (arxiv.org) Abstract ↓
Using the Dirichlet theorem on the equidistribution of residue classes modulo $q$ and the Lemke Oliver-Soundararajan conjecture on the distribution of pairs of residues on consecutive primes, we show that the domain of convergence of the infinite product of Dirichlet $L$-functions of non-principal characters can be extended from $\Re(s) > 1$ down to $\Re(s) > \half$, without encountering any zeros before reaching this critical line. The possibility of doing so can be traced back to a universal diffusive random walk behavior $C_N = {\cal O}(N^{1/2})$ of the series $C_N = \sum_{n=1}^N \chi (p_n)$ over the primes $p_n$ where $\chi$ is a Dirichlet character, which underlies the convergence of the infinite product of the Dirichlet functions. The series $C_N$ presents several aspects in common with stochastic time series and its control requires to address a problem similar to the Single Brownian Trajectory Problem in statistical mechanics. In the case of the Dirichlet functions of non principal characters, we show that this problem can be solved in terms of a self-averaging procedure based on an ensemble $\CE$ of block variables computed on extended intervals of primes. Those intervals, called {\em inertial intervals}, ensure the ergodicity and stationarity of the time series underlying the quantity $C_N$. The infinity of primes also ensures the absence of rare events which would have been responsible for a different scaling behavior than the universal law $C_N = {\cal O}(N^{1/2})$ of the random walks.
29.
Brownian Gibbs property for Airy line ensembles (arxiv.org) Abstract ↓
Consider N Brownian bridges B_i:[-N,N] -> R, B_i(-N) = B_i(N) = 0, 1 <= i <= N, conditioned not to intersect. The edge-scaling limit of this system is obtained by taking a limit as N -> infinity of these curves scaled around (0,2^{1/2} N) horizontally by a factor of N^{2/3} and vertically by N^{1/3}. If a parabola is added to each limit curve, an x-translation invariant process sometimes called the multi-line Airy process is obtained. We prove the existence of a version of this process (which we call the Airy line ensemble) in which curves are a.s. everywhere continuous and non-intersecting. This process naturally arises in the study of growth processes and random matrix ensembles, as do related processes with "wanderers" and "outliers". We formulate our results to treat these relatives as well. Note that the law of the finite collection of Brownian bridges above has the property -- called the Brownian Gibbs property -- of being invariant under the following action. Select an index 1 <= k <= N and erase B_k on a fixed time interval (a,b) subset of (-N,N); then replace this erased curve with a new curve on (a,b) according to the law of a Brownian bridge between the two existing endpoints (a,B_k(a)) and (b,B_k(b)), conditioned to intersect neither the curve above nor the one below. We show that this property is preserved under the edge-scaling limit and thus establish that the Airy line ensemble has the Brownian Gibbs property. An immediate consequence is a proof of M. Prahofer and H. Spohn's prediction that the lines of the Airy line ensemble are locally absolutely continuous with respect to Brownian motion. We also prove the conjecture of K. Johansson that the top line of the Airy line ensemble minus a parabola attains its maximum at a unique point, thus establishing the asymptotic law of the transversal fluctuation of last passage percolation with geometric weights.
30.
YAC: BFT Consensus Algorithm for Blockchain (arxiv.org) Abstract ↓
Consensus in decentralized systems that asynchronously receive events and which are subject to Byzantine faults is a common problem with many real-life applications. Advances in decentralized systems, such as distributed ledger (i.e., blockchain) technology, has only increased the importance of finding performant and secure solutions to consensus of state machine replication in decentralized systems. YAC is a practical decentralized consensus algorithm, that solves the problems of inefficient message passing and strong leaders that occur in classical Byzantine fault tolerant consensus algorithms. The algorithm is open source and currently is used to provide Byzantine fault tolerant consensus for the Hyperledger Iroha blockchain project. We provide proofs of safety and liveness, as well as empirical results showing that our algorithm can scale to dozens of validating peers.
31.
Classical Simulation of Quantum Supremacy Circuits (arxiv.org) Abstract ↓
It is believed that random quantum circuits are difficult to simulate classically. These have been used to demonstrate quantum supremacy: the execution of a computational task on a quantum computer that is infeasible for any classical computer. The task underlying the assertion of quantum supremacy by Arute et al. (Nature, 574, 505--510 (2019)) was initially estimated to require Summit, the world's most powerful supercomputer today, approximately 10,000 years. The same task was performed on the Sycamore quantum processor in only 200 seconds. In this work, we present a tensor network-based classical simulation algorithm. Using a Summit-comparable cluster, we estimate that our simulator can perform this task in less than 20 days. On moderately-sized instances, we reduce the runtime from years to minutes, running several times faster than Sycamore itself. These estimates are based on explicit simulations of parallel subtasks, and leave no room for hidden costs. The simulator's key ingredient is identifying and optimizing the "stem" of the computation: a sequence of pairwise tensor contractions that dominates the computational cost. This orders-of-magnitude reduction in classical simulation time, together with proposals for further significant improvements, indicates that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration.
32.
SegFormer: Simple and Efficient Design for Semantic Segmentation with Transformers (arxiv.org) Abstract ↓
We present SegFormer, a simple, efficient yet powerful semantic segmentation framework which unifies Transformers with lightweight multilayer perception (MLP) decoders. SegFormer has two appealing features: 1) SegFormer comprises a novel hierarchically structured Transformer encoder which outputs multiscale features. It does not need positional encoding, thereby avoiding the interpolation of positional codes which leads to decreased performance when the testing resolution differs from training. 2) SegFormer avoids complex decoders. The proposed MLP decoder aggregates information from different layers, and thus combining both local attention and global attention to render powerful representations. We show that this simple and lightweight design is the key to efficient segmentation on Transformers. We scale our approach up to obtain a series of models from SegFormer-B0 to SegFormer-B5, reaching significantly better performance and efficiency than previous counterparts. For example, SegFormer-B4 achieves 50.3% mIoU on ADE20K with 64M parameters, being 5x smaller and 2.2% better than the previous best method. Our best model, SegFormer-B5, achieves 84.0% mIoU on Cityscapes validation set and shows excellent zero-shot robustness on Cityscapes-C. Code will be released at: github.com/NVlabs/SegFormer.
33.
Understanding Perceptions of Problematic Facebook Use: When People Experience Negative Life Impact and a Lack of Control (arxiv.org) Abstract ↓
While many people use social network sites to connect with friends and family, some feel that their use is problematic, seriously affecting their sleep, work, or life. Pairing a survey of 20,000 Facebook users measuring perceptions of problematic use with behavioral and demographic data, we examined Facebook activities associated with problematic use as well as the kinds of people most likely to experience it. People who feel their use is problematic are more likely to be younger, male, and going through a major life event such as a breakup. They spend more time on the platform, particularly at night, and spend proportionally more time looking at profiles and less time browsing their News Feeds. They also message their friends more frequently. While they are more likely to respond to notifications, they are also more likely to deactivate their accounts, perhaps in an effort to better manage their time. Further, they are more likely to have seen content about social media or phone addiction. Notably, people reporting problematic use rate the site as more valuable to them, highlighting the complex relationship between technology use and well-being. A better understanding of problematic Facebook use can inform the design of context-appropriate and supportive tools to help people become more in control.
34.
Collective Motion of Moshers at Heavy Metal Concerts (arxiv.org) Abstract ↓
Human collective behavior can vary from calm to panicked depending on social context. Using videos publicly available online, we study the highly energized collective motion of attendees at heavy metal concerts. We find these extreme social gatherings generate similarly extreme behaviors: a disordered gas-like state called a mosh pit and an ordered vortex-like state called a circle pit. Both phenomena are reproduced in flocking simulations demonstrating that human collective behavior is consistent with the predictions of simplified models.
35.
The Rossiter-McLaughlin effect Revolutions: An ultra-short period planet and a warm mini-Neptune on perpendicular orbits (arxiv.org) Abstract ↓
Comparisons of the alignment of exoplanets with a common host star can be used to distinguish among concurrent evolution scenarios. However, multi-planet systems usually host mini-Neptunes and super-Earths, whose size make orbital architecture measurements challenging. We introduce the Rossiter-McLaughlin effect Revolutions technique, which can access spin-orbit angles of small planets by exploiting the full information contained in spectral transit time series. We validated the technique on published HARPS-N data of the mini-Neptune HD3167c, refining its high sky-projected spin-orbit angle (-108.9+5.4-5.5 deg), and we applied it to new ESPRESSO observations of the super-Earth HD3167b, revealing an aligned orbit (-6.6+6.6-7.9 deg). Surprisingly different variations in the contrast of the stellar lines occulted by the planets can be reconciled with a latitudinal dependence of the stellar line shape. In this scenario, a joint fit to both datasets constrains the inclination of the star (111.6+3.1-3.3 deg) and the 3D spin-orbit angles of HD3167b (29.5+7.2-9.4 deg) and HD3167c (107.7+5.1-4.9 deg). The projected spin-orbit angles do not depend on the model for the line contrast variations, and so, with a mutual inclination of 102.3+7.4-8.0 deg, we conclude that the two planets are on perpendicular orbits. This could be explained by HD3167b being strongly coupled to the star and retaining its primordial alignment, whereas HD3167c would have been brought to a nearly polar orbit via secular gravitational interactions with an outer companion. Follow-up observations and dynamical evolution simulations are required to search for this companion and explore this scenario. HD3167b is the smallest exoplanet with a confirmed spectroscopic Rossiter-McLaughlin signal. Our new technique opens the way to determining the orbital architectures of the super-Earth and Earth-sized planet populations.
36.
Evaluating Query Languages and Systems for High-Energy Physics Data [Extended Version] (arxiv.org) Abstract ↓
In the domain of high-energy physics (HEP), query languages in general and SQL in particular have found limited acceptance. This is surprising since HEP data analysis matches the SQL model well: the data is fully structured and queried using mostly standard operators. To gain insights on why this is the case, we perform a comprehensive analysis of six diverse, general-purpose data processing platforms using an HEP benchmark. The result of the evaluation is an interesting and rather complex picture of existing solutions: Their query languages vary greatly in how natural and concise HEP query patterns can be expressed. Furthermore, most of them are also between one and two orders of magnitude slower than the domain-specific system used by particle physicists today. These observations suggest that, while database systems and their query languages are in principle viable tools for HEP, significant work remains to make them relevant to HEP researchers.
37.
Rethinking Search: Making Domain Experts out of Dilettantes (arxiv.org) Abstract ↓
When experiencing an information need, users want to engage with a domain expert, but often turn to an information retrieval system, such as a search engine, instead. Classical information retrieval systems do not answer information needs directly, but instead provide references to (hopefully authoritative) answers. Successful question answering systems offer a limited corpus created on-demand by human experts, which is neither timely nor scalable. Pre-trained language models, by contrast, are capable of directly generating prose that may be responsive to an information need, but at present they are dilettantes rather than domain experts -- they do not have a true understanding of the world, they are prone to hallucinating, and crucially they are incapable of justifying their utterances by referring to supporting documents in the corpus they were trained over. This paper examines how ideas from classical information retrieval and pre-trained language models can be synthesized and evolved into systems that truly deliver on the promise of domain expert advice.
38.
A search for Planet Nine using the Zwicky Transient Facility public archive (arxiv.org) Abstract ↓
Recent estimates of the characteristics of Planet Nine have suggested that it could be closer than originally assumed. Such a Planet Nine would also be brighter than originally assumed, suggesting the possibility that it has already been observed in wide-field moderate-depth surveys. We search for Planet Nine in the Zwicky Transient Facility public archive and find no candidates. Using known asteroids to calculate the magnitude limit of the survey, we find that we should have detected Planet Nine throughout most of the northern portion of its predicted orbit -- including within the galactic plane -- to a 95% detection efficiency of approximately $V=20.5$. To aid in understanding detection limits for this and future analyses, we present a full-sky synthetic Planet Nine population drawn from a statistical sampling of predicted Planet Nine orbits. We use this reference population to estimate that this survey rules out 56% of predicted Planet Nine phase space, and we demonstrate how future analyses can use the same synthetic population to continue to constrain the amount of parameter space effectively searched for Planet Nine.
39.
Magic: The Gathering is Turing Complete (arxiv.org) Abstract ↓
$\textit{Magic: The Gathering}$ is a popular and famously complicated trading card game about magical combat. In this paper we show that optimal play in real-world $\textit{Magic}$ is at least as hard as the Halting Problem, solving a problem that has been open for a decade. To do this, we present a methodology for embedding an arbitrary Turing machine into a game of $\textit{Magic}$ such that the first player is guaranteed to win the game if and only if the Turing machine halts. Our result applies to how real $\textit{Magic}$ is played, can be achieved using standard-size tournament-legal decks, and does not rely on stochasticity or hidden information. Our result is also highly unusual in that all moves of both players are forced in the construction. This shows that even recognising who will win a game in which neither player has a non-trivial decision to make for the rest of the game is undecidable. We conclude with a discussion of the implications for a unified computational theory of games and remarks about the playability of such a board in a tournament setting.
40.
Discover & eXplore Neural Network (DXNN) Platform, a Modular TWEANN (arxiv.org) Abstract ↓
In this paper I present a novel type of Topology and Weight Evolving Artificial Neural Network (TWEANN) system called Modular Discover & eXplore Neural Network (DXNN). Modular DXNN utilizes a hierarchical/modular topology which allows for highly scalable and dynamically granular systems to evolve. Among the novel features discussed in this paper is a simple and database friendly encoding for hierarchical/modular NNs, a new selection method aimed at producing highly compact and fit individuals within the population, a "Targeted Tunning" system aimed at alleviating the curse of dimensionality, and a two phase based neuroevolutionary approach which yields high population diversity and removes the need for speciation algorithms. I will discuss DXNN's mutation operators which are aimed at improving its efficiency, expandability, and capabilities through a built in feature selection method that allows for the evolved system to expand, discover, and explore new sensors and actuators. Finally I will compare DXNN platform to other state of the art TWEANNs on a control task to demonstrate its superior ability to produce highly compact solutions faster than its competitors.
41.
On the Impossibility of Supersized Machines (arxiv.org) Abstract ↓
In recent years, a number of prominent computer scientists, along with academics in fields such as philosophy and physics, have lent credence to the notion that machines may one day become as large as humans. Many have further argued that machines could even come to exceed human size by a significant margin. However, there are at least seven distinct arguments that preclude this outcome. We show that it is not only implausible that machines will ever exceed human size, but in fact impossible.
42.
Jewish Problems (arxiv.org) Abstract ↓
This is a special collection of problems that were given to select applicants during oral entrance exams to the math department of Moscow State University. These problems were designed to prevent Jews and other undesirables from getting a passing grade. Among problems that were used by the department to blackball unwanted candidate students, these problems are distinguished by having a simple solution that is difficult to find. Using problems with a simple solution protected the administration from extra complaints and appeals. This collection therefore has mathematical as well as historical value.
43.
Nethammer: Inducing Rowhammer Faults through Network Requests (arxiv.org) Abstract ↓
A fundamental assumption in software security is that memory contents do not change unless there is a legitimate deliberate modification. Classical fault attacks show that this assumption does not hold if the attacker has physical access. Rowhammer attacks showed that local code execution is already sufficient to break this assumption. Rowhammer exploits parasitic effects in DRAM to modify the content of a memory cell without accessing it. Instead, other memory locations are accessed at a high frequency. All Rowhammer attacks so far were local attacks, running either in a scripted language or native code. In this paper, we present Nethammer. Nethammer is the first truly remote Rowhammer attack, without a single attacker-controlled line of code on the targeted system. Systems that use uncached memory or flush instructions while handling network requests, e.g., for interaction with the network device, can be attacked using Nethammer. Other systems can still be attacked if they are protected with quality-of-service techniques like Intel CAT. We demonstrate that the frequency of the cache misses is in all three cases high enough to induce bit flips. We evaluated different bit flip scenarios. Depending on the location, the bit flip compromises either the security and integrity of the system and the data of its users, or it can leave persistent damage on the system, i.e., persistent denial of service. We investigated Nethammer on personal computers, servers, and mobile phones. Nethammer is a security landslide, making the formerly local attack a remote attack.
44.
Linear Probing Revisited: Tombstones Mark the Death of Primary Clustering (arxiv.org) Abstract ↓
First introduced in 1954, linear probing is one of the oldest data structures in computer science, and due to its unrivaled data locality, it continues to be one of the fastest hash tables in practice. It is widely believed and taught, however, that linear probing should never be used at high load factors; this is because primary-clustering effects cause insertions at load factor $1 - 1 /x$ to take expected time $\Theta(x^2)$ (rather than the ideal $\Theta(x)$). The dangers of primary clustering, first discovered by Knuth in 1963, have been taught to generations of computer scientists, and have influenced the design of some of many widely used hash tables. We show that primary clustering is not a foregone conclusion. We demonstrate that small design decisions in how deletions are implemented have dramatic effects on the asymptotic performance of insertions, so that, even if a hash table operates continuously at a load factor $1 - \Theta(1/x)$, the expected amortized cost per operation is $\tilde{O}(x)$. This is because tombstones created by deletions actually cause an anti-clustering effect that combats primary clustering. We also present a new variant of linear probing (which we call graveyard hashing) that completely eliminates primary clustering on \emph{any} sequence of operations: if, when an operation is performed, the current load factor is $1 - 1/x$ for some $x$, then the expected cost of the operation is $O(x)$. One corollary is that, in the external-memory model with a data blocks of size $B$, graveyard hashing offers the following remarkable guarantee: at any load factor $1 - 1/x$ satisfying $x = o(B)$, graveyard hashing achieves $1 + o(1)$ expected block transfers per operation. Past external-memory hash tables have only been able to offer a $1 + o(1)$ guarantee when the block size $B$ is at least $\Omega(x^2)$.
45.
Light-cone PDFs and GPDs from Lattice QCD (arxiv.org) Abstract ↓
In this article, we review recent lattice calculations on the $x$-dependence of PDFs and GPDs from lattice QCD.
46.
Why and How zk-SNARK Works (arxiv.org) Abstract ↓
Despite the existence of multiple great resources on zk-SNARK construction, from original papers to explainers, due to the sheer number of moving parts the subject remains a black box for many. While some pieces of the puzzle are given one can not see the full picture without the missing ones. Hence the focus of this work is to shed light onto the topic with a straightforward and clean approach based on examples and answering many whys along the way so that more individuals can appreciate the state of the art technology, its innovators and ultimately the beauty of math. Paper's contribution is a simplistic exposition with a sufficient and gradually increasing level of complexity, necessary to understand zk-SNARK without any prerequisite knowledge of the subject, cryptography or advanced math. The primary goal is not only to explain how it works but why it works and how it came to be this way.
47.
The Myth of Modularity in Rule-Based Systems (arxiv.org) Abstract ↓
In this paper, we examine the concept of modularity, an often cited advantage of the ruled-based representation methodology. We argue that the notion of modularity consists of two distinct concepts which we call syntactic modularity and semantic modularity. We argue that when reasoning under certainty, it is reasonable to regard the rule-based approach as both syntactically and semantically modular. However, we argue that in the case of plausible reasoning, rules are syntactically modular but are rarely semantically modular. To illustrate this point, we examine a particular approach for managing uncertainty in rule-based systems called the MYCIN certainty factor model. We formally define the concept of semantic modularity with respect to the certainty factor model and discuss logical consequences of the definition. We show that the assumption of semantic modularity imposes strong restrictions on rules in a knowledge base. We argue that such restrictions are rarely valid in practical applications. Finally, we suggest how the concept of semantic modularity can be relaxed in a manner that makes it appropriate for plausible reasoning.
48.
Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics (arxiv.org) Abstract ↓
Robotic algorithms typically depend on various parameters, the choice of which significantly affects the robot's performance. While an initial guess for the parameters may be obtained from dynamic models of the robot, parameters are usually tuned manually on the real system to achieve the best performance. Optimization algorithms, such as Bayesian optimization, have been used to automate this process. However, these methods may evaluate unsafe parameters during the optimization process that lead to safety-critical system failures. Recently, a safe Bayesian optimization algorithm, called SafeOpt, has been developed, which guarantees that the performance of the system never falls below a critical value; that is, safety is defined based on the performance function. However, coupling performance and safety is often not desirable in robotics. For example, high-gain controllers might achieve low average tracking error (performance), but can overshoot and violate input constraints. In this paper, we present a generalized algorithm that allows for multiple safety constraints separate from the objective. Given an initial set of safe parameters, the algorithm maximizes performance but only evaluates parameters that satisfy safety for all constraints with high probability. To this end, it carefully explores the parameter space by exploiting regularity assumptions in terms of a Gaussian process prior. Moreover, we show how context variables can be used to safely transfer knowledge to new situations and tasks. We provide a theoretical analysis and demonstrate that the proposed algorithm enables fast, automatic, and safe optimization of tuning parameters in experiments on a quadrotor vehicle.
49.
An enriched category theory of language: from syntax to semantics (arxiv.org) Abstract ↓
State of the art language models return a natural language text continuation from any piece of input text. This ability to generate coherent text extensions implies significant sophistication, including a knowledge of grammar and semantics. In this paper, we propose a mathematical framework for passing from probability distributions on extensions of given texts, such as the ones learned by today's large language models, to an enriched category containing semantic information. Roughly speaking, we model probability distributions on texts as a category enriched over the unit interval. Objects of this category are expressions in language, and hom objects are conditional probabilities that one expression is an extension of another. This category is syntactical -- it describes what goes with what. Then, via the Yoneda embedding, we pass to the enriched category of unit interval-valued copresheaves on this syntactical category. This category of enriched copresheaves is semantic -- it is where we find meaning, logical operations such as entailment, and the building blocks for more elaborate semantic concepts.
50.
Towards combinatorial invariance for Kazhdan-Lusztig polynomials (arxiv.org) Abstract ↓
Kazhdan-Lusztig polynomials are important and mysterious objects in representation theory. Here we present a new formula for their computation for symmetric groups based on the Bruhat graph. Our approach suggests a solution to the combinatorial invariance conjecture for symmetric groups, a well-known conjecture formulated by Lusztig and Dyer in the 1980s.
51.
Dissolving the Fermi Paradox (arxiv.org) Abstract ↓
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe. The expectation that the universe should be teeming with intelligent life is linked to models like the Drake equation, which suggest that even if the probability of intelligent life developing at a given site is small, the sheer multitude of possible sites should nonetheless yield a large number of potentially observable civilizations. We show that this conflict arises from the use of Drake-like equations, which implicitly assume certainty regarding highly uncertain parameters. We examine these parameters, incorporating models of chemical and genetic transitions on paths to the origin of life, and show that extant scientific knowledge corresponds to uncertainties that span multiple orders of magnitude. This makes a stark difference. When the model is recast to represent realistic distributions of uncertainty, we find a substantial {\em ex ante} probability of there being no other intelligent life in our observable universe, and thus that there should be little surprise when we fail to detect any signs of it. This result dissolves the Fermi paradox, and in doing so removes any need to invoke speculative mechanisms by which civilizations would inevitably fail to have observable effects upon the universe.
52.
Perceiver IO: A General Architecture for Structured Inputs & Outputs (arxiv.org) Abstract ↓
The recently-proposed Perceiver model obtains good results on several domains (images, audio, multimodal, point clouds) while scaling linearly in compute and memory with the input size. While the Perceiver supports many kinds of inputs, it can only produce very simple outputs such as class scores. Perceiver IO overcomes this limitation without sacrificing the original's appealing properties by learning to flexibly query the model's latent space to produce outputs of arbitrary size and semantics. Perceiver IO still decouples model depth from data size and still scales linearly with data size, but now with respect to both input and output sizes. The full Perceiver IO model achieves strong results on tasks with highly structured output spaces, such as natural language and visual understanding, StarCraft II, and multi-task and multi-modal domains. As highlights, Perceiver IO matches a Transformer-based BERT baseline on the GLUE language benchmark without the need for input tokenization and achieves state-of-the-art performance on Sintel optical flow estimation.
53.
Rumble: Data Independence for Large Messy Data Sets (arxiv.org) Abstract ↓
This paper introduces Rumble, a query execution engine for large, heterogeneous, and nested collections of JSON objects built on top of Apache Spark. While data sets of this type are more and more wide-spread, most existing tools are built around a tabular data model, creating an impedance mismatch for both the engine and the query interface. In contrast, Rumble uses JSONiq, a standardized language specifically designed for querying JSON documents. The key challenge in the design and implementation of Rumble is mapping the recursive structure of JSON documents and JSONiq queries onto Spark's execution primitives based on tabular data frames. Our solution is to translate a JSONiq expression into a tree of iterators that dynamically switch between local and distributed execution modes depending on the nesting level. By overcoming the impedance mismatch in the engine, Rumble frees the user from solving the same problem for every single query, thus increasing their productivity considerably. As we show in extensive experiments, Rumble is able to scale to large and complex data sets in the terabyte range with a similar or better performance than other engines. The results also illustrate that Codd's concept of data independence makes as much sense for heterogeneous, nested data sets as it does on highly structured tables.
54.
Gaia EDR3 proper motions of Milky Way dwarfs. II: Velocities, Total Energy and Angular Momentum (arxiv.org) Abstract ↓
Here we show that precise Gaia EDR3 proper motions have provided robust estimates of 3D velocities, angular momentum and total energy for 40 Milky Way dwarfs. The results are statistically robust and are independent of the Milky Way mass profile. Dwarfs do not behave like long-lived satellites of the Milky Way because of their excessively large velocities, angular momenta, and total energies. Comparing them to other MW halo population, we find that many are at first passage, $\le$ 2 Gyr ago, i.e., more recently than the passage of Sagittarius, $\sim$ 4-5 Gyr ago. We suggest that this is in agreement with the stellar populations of all dwarfs, for which we find that a small fraction of young stars cannot be excluded. We also find that dwarf radial velocities contribute too little to their kinetic energy when compared to satellite systems with motions only regulated by gravity, and some other mechanism must be at work such as ram pressure. The latter may have preferentially reduced radial velocities when dwarf progenitors entered the halo until they lost their gas. It could also explain why most dwarfs lie near their pericenter. We also discover a novel large scale structure perpendicular to the Milky Way disk, which is made by 20% of dwarfs orbiting or counter orbiting with the Sagittarius dwarf.
55.
Julia for Biologists (arxiv.org) Abstract ↓
Increasing emphasis on data and quantitative methods in the biomedical sciences is making biological research more computational. Collecting, curating, processing, and analysing large genomic and imaging data sets poses major computational challenges, as does simulating larger and more realistic models in systems biology. Here we discuss how a relative newcomer among computer programming languages -- Julia -- is poised to meet the current and emerging demands in the computational biosciences, and beyond. Speed, flexibility, a thriving package ecosystem, and readability are major factors that make high-performance computing and data analysis available to an unprecedented degree to "gifted amateurs". We highlight how Julia's design is already enabling new ways of analysing biological data and systems, and we provide a, necessarily incomplete, list of resources that can facilitate the transition into the Julian way of computing.
56.
First neutrino interaction candidates at the LHC (arxiv.org) Abstract ↓
FASER$\nu$ at the CERN Large Hadron Collider (LHC) is designed to directly detect collider neutrinos for the first time and study their cross sections at TeV energies, where no such measurements currently exist. In 2018, a pilot detector employing emulsion films was installed in the far-forward region of ATLAS, 480 m from the interaction point, and collected 12.2 fb$^{-1}$ of proton-proton collision data at a center-of-mass energy of 13 TeV. We describe the analysis of this pilot run data and the observation of the first neutrino interaction candidates at the LHC. This milestone paves the way for high-energy neutrino measurements at current and future colliders.
57.
Three Attacks on Proof-of-Stake Ethereum (arxiv.org) Abstract ↓
Recently, two attacks were presented against Proof-of-Stake (PoS) Ethereum: one where short-range reorganizations of the underlying consensus chain are used to increase individual validators' profits and delay consensus decisions, and one where adversarial network delay is leveraged to stall consensus decisions indefinitely. We provide refined variants of these attacks, considerably relaxing the requirements on adversarial stake and network timing, and thus rendering the attacks more severe. Combining techniques from both refined attacks, we obtain a third attack which allows an adversary with vanishingly small fraction of stake and no control over network message propagation (assuming instead probabilistic message propagation) to cause even long-range consensus chain reorganizations. Honest-but-rational or ideologically motivated validators could use this attack to increase their profits or stall the protocol, threatening incentive alignment and security of PoS Ethereum. The attack can also lead to destabilization of consensus from congestion in vote processing.
58.
Quantum principle of relativity (arxiv.org) Abstract ↓
We show that the local and deterministic mode of description is not only in conflict with the quantum theory, but also with relativity. We argue that elementary relativistic properties of spacetime lead to the emergence of a non-deterministic quantum-mechanical picture involving quantum superpositions and complex probability amplitudes.
59.
Large-Scale Intelligent Microservices (arxiv.org) Abstract ↓
Deploying Machine Learning (ML) algorithms within databases is a challenge due to the varied computational footprints of modern ML algorithms and the myriad of database technologies each with its own restrictive syntax. We introduce an Apache Spark-based micro-service orchestration framework that extends database operations to include web service primitives. Our system can orchestrate web services across hundreds of machines and takes full advantage of cluster, thread, and asynchronous parallelism. Using this framework, we provide large scale clients for intelligent services such as speech, vision, search, anomaly detection, and text analysis. This allows users to integrate ready-to-use intelligence into any datastore with an Apache Spark connector. To eliminate the majority of overhead from network communication, we also introduce a low-latency containerized version of our architecture. Finally, we demonstrate that the services we investigate are competitive on a variety of benchmarks, and present two applications of this framework to create intelligent search engines, and real-time auto race analytics systems.
60.
Hierarchical Transformers Are More Efficient Language Models (arxiv.org) Abstract ↓
Transformer models yield impressive results on many NLP and sequence modeling tasks. Remarkably, Transformers can handle long sequences which allows them to produce long coherent outputs: full paragraphs produced by GPT-3 or well-structured images produced by DALL-E. These large language models are impressive but also very inefficient and costly, which limits their applications and accessibility. We postulate that having an explicit hierarchical architecture is the key to Transformers that efficiently handle long sequences. To verify this claim, we first study different ways to downsample and upsample activations in Transformers so as to make them hierarchical. We use the best performing upsampling and downsampling layers to create Hourglass - a hierarchical Transformer language model. Hourglass improves upon the Transformer baseline given the same amount of computation and can yield the same results as Transformers more efficiently. In particular, Hourglass sets new state-of-the-art for Transformer models on the ImageNet32 generation task and improves language modeling efficiency on the widely studied enwik8 benchmark.
61.
Solving the sampling problem of the Sycamore quantum supremacy circuits (arxiv.org) Abstract ↓
We study the problem of generating independent samples from the output distribution of Google's Sycamore quantum circuits with a target fidelity, which is believed to be beyond the reach of classical supercomputers and has been used to demonstrate quantum supremacy. We propose a new method to classically solve this problem by contracting the corresponding tensor network just once, and is massively more efficient than existing methods in obtaining a large number of uncorrelated samples with a target fidelity. For the Sycamore quantum supremacy circuit with $53$ qubits and $20$ cycles, we have generated one million uncorrelated bitstrings $\{\mathbf s\}$ which are sampled from a distribution $\widehat P(\mathbf s)=|\widehat \psi(\mathbf s)|^2$, where the approximate state $\widehat \psi$ has fidelity $F\approx 0.0037$. The whole computation has cost about $15$ hours on a computational cluster with $512$ GPUs. The obtained one million samples, the contraction code and contraction order are made public. If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google's quantum hardware.
62.
The Disk Substructures at High Angular Resolution Project (DSHARP): I. Motivation, Sample, Calibration, and Overview (arxiv.org) Abstract ↓
We introduce the Disk Substructures at High Angular Resolution Project (DSHARP), one of the initial Large Programs conducted with the Atacama Large Millimeter/submillimeter Array (ALMA). The primary goal of DSHARP is to find and characterize substructures in the spatial distributions of solid particles for a sample of 20 nearby protoplanetary disks, using very high resolution (0.035 arcsec, or 5 au FWHM) observations of their 240 GHz (1.25 mm) continuum emission. These data provide a first homogeneous look at the small-scale features in disks that are directly relevant to the planet formation process, quantifying their prevalence, morphologies, spatial scales, spacings, symmetry, and amplitudes, for targets with a variety of disk and stellar host properties. We find that these substructures are ubiquitous in this sample of large, bright disks. They are most frequently manifested as concentric, narrow emission rings and depleted gaps, although large-scale spiral patterns and small arc-shaped azimuthal asymmetries are also present in some cases. These substructures are found at a wide range of disk radii (from a few au to more than 100 au), are usually compact ($<$10 au), and show a wide range of amplitudes (brightness contrasts). Here we discuss the motivation for the project, describe the survey design and the sample properties, detail the observations and data calibration, highlight some basic results, and provide a general overview of the key conclusions that are presented in more detail in a series of accompanying articles. The DSHARP data -- including visibilities, images, calibration scripts, and more -- are released for community use at https://almascience.org/alma-data/lp/DSHARP.


Last Update 2021-12-05 00:07


Not affiliated with Hacker News or YCombinator