res

#topic:actor
#language:english
#medium:paper
Actor Model of Computation: Scalable Robust Information Systems
The Actor Model is a mathematical theory that treats “Actors” as the
universal primitives of digital computation.  The model has been used
both as a framework for a theoretical understanding of concurrency, and as
the theoretical basis for several practical implementations of concurrent
systems. The advent of massive concurrency through client-cloud computing
and many-core computer architectures has galvanized interest in the Actor Model
^
@https://arxiv.org/pdf/1008.1459.pdf
#topic:actor
#language:english
#medium:paper
Formalizing common sense reasoning for scalable inconsistency-robust information integration using Direct LogicTM Reasoning and the Actor Model
People use common sense in their interactions with large information systems.
This common sense needs to be formalized so that it can be used by computer
systems. Unfortunately, previous formalizations have been inadequate. For
example, classical logic is not safe for use with pervasively inconsistent
information. The goal is to develop a standard foundation for reasoning in
large-scale Internet applications (including sense making for natural
language)
^
@https://arxiv.org/pdf/0812.4852.pdf
#topic:bigraphs
#topic:category theory
#language:english
#medium:paper
Bigraphical reactive systems: basic theory
A notion of bigraph is proposed as the basis for a model of mobile
interaction. A bigraph consists of two independent structures: a topograph
representing locality and a monograph representing connectivity. Bigraphs
are equipped with reaction rules to form bigraphical reactive systems (BRSs),
which include versions of the -calculus and the ambient calculus. Bigraphs are
shown to be a special case of a more abstract notion, wide reactive systems
(WRSs), not assuming any particular graphical or other structure but equipped
with a notion of width, which expresses that agents, contexts and reactions
may all be widely distributed entities
^
@https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-523.pdf
#topic:mbus
#topic:wireless mbus
#topic:security
#language:english
#medium:paper
Wireless M-Bus Security Whitepaper
This work aims to analyse the security of the Meter Bus as specified
in the relevant International organisation for Standardization (ISO)
documentation. M-Bus has its roots in the heat metering industries and
was continuously adopted to fit more complex applications. M-Bus is the
communication bus of choice of several meter manufacturers and its applications
span from drive-by wireless meter reading over to meter-to-meter and mesh
networking to meter-to-collector communication. M-Bus implementations support
different media types such as power line carrier (PLC) or twisted-pair
bus. To avoid the wiring efforts at the distribution level, utilities,
metering companies and manufacturers tend to more frequently choose wireless
protocols for communication. Accordingly, the analysis will mainly concentrate
on M-Bus wireless based communication – wM-Bus
^
@https://www.compass-security.com/fileadmin/Datein/Research/Praesentationen/blackhat_2013_wmbus_security_whitepaper.pdf
#topic:fpga
#topic:neural network
#topic:machine learning
#language:english
#medium:paper
FPGA Implementations of Neural Networks
During the 1980s and early 1990s there was significant work in the design
and implementation of hardware neurocomputers. Nevertheless, most of
these efforts may be judged to have been unsuccessful: at no time have
have hardware neurocomputers been in wide use. This lack of success may be
largely attributed to the fact that earlier work was almost entirely aimed
at developing custom neurocomputers, based on ASIC technology, but for such
niche areas this technology was never sufficiently developed or competitive
enough to justify large-scale adoption. On the other hand, gate-arrays of
the period mentioned were never large enough nor fast enough for serious
artificial-neuralnetwork (ANN) applications. But technology has now improved:
the capacity and performance of current FPGAs are such that they present
a much more realistic alternative. Consequently neurocomputers based on
FPGAs are now a much more practical proposition than they have been in the
past. This book summarizes some work towards this goal and consists of 12
papers that were selected, after review, from a number of submissions.
^
@http://lab.fs.uni-lj.si/lasin/wp/IMIT_files/neural/doc/Omondi2006.pdf
#topic:fpga
#topic:neural network
#topic:machine learning
#language:english
#medium:paper
A General Neural Network Hardware Architecture on FPGA
Field Programmable Gate Arrays (FPGAs) plays an increasingly important
role in data sampling and processing industries due to its highly
parallel architecture, low power consumption, and flexibility in custom
algorithms. Especially, in the artificial intelligence field, for training and
implement the neural networks and machine learning algorithms, high energy
efficiency hardware implement and massively parallel computing capacity are
heavily demanded. Therefore, many global companies have applied FPGAs into
AI and Machine learning fields such as autonomous driving and Automatic
Spoken Language Recognition (Baidu) [1] [2] and Bing search (Microsoft)
[3]. Considering the FPGAs great potential in these fields, we tend to
implement a general neural network hardware architecture on XILINX ZU9CG
System On Chip (SOC) platform [4], which contains abundant hardware resource
and powerful processing capacity. The general neural network architecture
on the FPGA SOC platform can perform forward and backward algorithms in deep
neural networks (DNN) with high performance and easily be adjusted according
to the type and scale of the neural networks.
^
@https://arxiv.org/ftp/arxiv/papers/1711/1711.05860.pdf
#topic:file system
#language:english
#medium:paper
TagFS: A simple tag-based filesystem
TagFS is a simple yet effective tag-based filesystem. Instead of organizing files and documents in
a strict hierarchy (like traditional filesystems), TagFS allows users to assign descriptive attributes
(called tags) to files and subsequently locate those files by searching for tags of interest.
^
@https://web.mit.edu/6.033/2011/wwwdocs/writing-samples/sbezek_dp1.pdf
#topic:optimisation
#topic:neural network
#topic:genetic algorithms
#topic:differential evolution
#topic:bee swarm algorithm
#topic:ant colony optimisation
#language:english
#medium:book
Clever Algorithms: Nature-Inspired Programming Recipes
Implementing an Artificial Intelligence algorithm is difficult. Algorithm
descriptions may be incomplete, inconsistent, and distributed across a
number of papers, chapters and even websites. This can result in varied
interpretations of algorithms, undue attrition of algorithms, and ultimately
bad science. This book is an effort to address these issues by providing
a handbook of algorithmic recipes drawn from the fields of Metaheuristics,
Biologically Inspired Computation and Computational Intelligence, described in
a complete, consistent, and centralized manner. These standardized descriptions
were carefully designed to be accessible, usable, and understandable. Most
of the algorithms described were originally inspired by biological and
natural systems, such as the adaptive capabilities of genetic evolution
and the acquired immune system, and the foraging behaviors of birds, bees,
ants and bacteria. An encyclopedic algorithm reference, this book is intended
for research scientists, engineers, students, and interested amateurs. Each
algorithm description provides a working code example in the Ruby Programming
Language.
^
@https://raw.githubusercontent.com/clever-algorithms/CleverAlgorithms/master/release/clever_algorithms.pdf
#topic:category theory
#topic:haskell
#topic:c++
#topic:template metaprogramming
#topic:type system
#author:Bartosz Milewski
#language:english
#medium:book
Category Theory for Programmers
For some time now I’ve been floating the idea of writing a book about
category theory that would be targeted at programmers. Mind you, not computer
scientists but programmers — engineers rather than scientists. I know
this sounds crazy and I am properly scared. I can’t deny that there is
a huge gap between science and engineering because I have worked on both
sides of the divide. But I’ve always felt a very strong compulsion to
explain things. I have tremendous admiration for Richard Feynman who was
the master of simple explanations. I know I’m no Feynman, but I will try
my best. I’m starting by publishing this preface — which is supposed
to motivate the reader to learn category theory — in hopes of starting a
discussion and soliciting feedback.
^
@https://github.com/hmemcpy/milewski-ctfp-pdf/releases/download/v1.3.0/category-theory-for-programmers.pdf
#topic:category theory
#topic:version control
#author:Samuel Mimram
#author:Cinzia Di Giusto
#language:english
#medium:paper
A Categorical Theory of Patches
When working with distant collaborators on the same documents, one often
uses a version control system, which is a program tracking the history of
files and helping importing modifications brought by others as patches. The
implementation of such a system requires to handle lots of situations depending
on the operations performed by users on files, and it is thus difficult to
ensure that all the corner cases have been correctly addressed. Here, instead
of verifying the implementation of such a system, we adopt a complementary
approach: we introduce a theoretical model, which is defined abstractly
by the universal property that it should satisfy, and work out a concrete
description of it. We begin by defining a category of files and patches,
where the operation of merging the effect of two coinitial patches is defined
by pushout. Since two patches can be incompatible, such a pushout does not
necessarily exist in the category, which raises the question of which is the
correct category to represent and manipulate files in conflicting state. We
provide an answer by investigating the free completion of the category of files
under finite colimits, and give an explicit description of this category:
its objects are finite sets labeled by lines equipped with a transitive
relation and morphisms are partial functions respecting labeling and relations.
^
@https://arxiv.org/pdf/1311.3903
#topic:algorithm
#author:Eugene W. Myers
#language:english
#medium:paper
An O(ND) Difference Algorithm and Its Variations∗
The problems of finding a longest common subsequence of two sequences A
and B and a shortest edit script for transforming A into B have long been
known to be dual problems. In this paper, they are shown to be equivalent to
finding a shortest/longest path in an edit graph. Using this perspective,
a simple O(ND) time and space algorithm is developed where N is the sum of
the lengths of A and B and D is the size of the minimum edit script for A
and B. The algorithm performs well when differences are small (sequences are
similar) and is consequently fast in typical applications. The algorithm is
shown to have O(N + D^2) expected-time performance under a basic stochastic
model. A refinement of the algorithm requires only O(N) space, and the use
of suffix trees leads to an O(NlgN + D^2) time variation
^
@http://www.xmailserver.org/diff2.pdf
#topic:sorting
#author:Sergei Bespamyatnikh
#author:Michael Segal
#language:english
#medium:paper
Enumerating Longest Increasing Subsequences and Patience Sorting (2000)
In this paper we present three algorithms that solve three combinatorial
optimization problems related to each other. One of them is the patience
sorting game, invented as a practical method of sorting real decks of
cards. The second problem is computing the longest monotone increasing
subsequence of the given sequence of n positive integers in the range 1; : :
: ; n. The third problem is to enumerate all the longest monotone increasing
subsequences of the given permutation.
^
@http://www.ii.uni.wroc.pl/~lorys/IPL/article76-1-1.pdf
#topic:single static assignment
#topic:compiler
#topic:compiler optimisation
#author:Lori Carter
#author:Beth Simon
#author:Brad Calder
#author:Larry Carter
#author:Jeanne Ferrante
#language:english
#medium:paper
Predicated Static Single Assignment
Increases in instruction level parallelism are needed to exploit the potential
parallelism available in future wide issue architectures. Predicated execution
is an architectural mechanism that increases instruction level parallelism
by removing branches and allowing simultaneous execution of multiple paths
of control, only committing instructions from the correct path. In order
for the compiler to expose such parallelism, traditional compiler data-flow
analysis needs to be extended to predicated code.  In this paper, we present
Predicated Static Single Assignment (PSSA) to enable aggressive predicated
optimization and instruction scheduling. PSSA removes false dependences by
exploiting renaming and information about the multiple control paths. We
demonstrate the usefulness of PSSA for Predicated Speculation and Control
Height Reduction. These two predicated code optimizations used during
instruction scheduling reduce the dependence length of the critical paths
through a predicated region. Our results show that using PSSA to enable
speculation and control height reduction reduces execution time from 10%
to 58%.
^
@http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.7756&rep=rep1&type=pdf
#topic:single static assignment
#topic:compiler
#topic:compiler optimisation
#language:english
#medium:book
Static Single Assignment Book

^
@http://ssabook.gforge.inria.fr/latest/book.pdf
#topic:neural network
#topic:auto-encoding
#author:Diederik P. Kingma
#author:Max Welling
#language:english
#medium:paper
Auto-Encoding Variational Bayes
How can we perform efficient inference and learning in directed probabilistic
models, in the presence of continuous latent variables with intractable
posterior distributions, and large datasets? We introduce a stochastic
variational inference and learning algorithm that scales to large datasets
and, under some mild differentiability conditions, even works in the
intractable case. Our contributions is two-fold. First, we show that a
reparameterization of the variational lower bound yields a lower bound
estimator that can be straightforwardly optimized using standard stochastic
gradient methods. Second, we show that for i.i.d. datasets with continuous
latent variables per datapoint, posterior inference can be made especially
efficient by fitting an approximate inference model (also called a recognition
model) to the intractable posterior using the proposed lower bound estimator.
Theoretical advantages are reflected in experimental results.
^
@https://arxiv.org/pdf/1312.6114.pdf
#topic:neural network
#author:Thomas N. Kipf
#author:Max Welling
#language:english
#medium:paper
Variational Graph Auto-Encoders
We introduce the variational graph auto-encoder (VGAE), a framework for
unsupervised learning on graph-structured data based on the variational
auto-encoder (VAE). This model makes use of latent variables and is capable
of learning interpretable latent representations for undirected graphs. We
demonstrate this model using a graph convolutional network (GCN) encoder and
a simple inner product decoder. Our model achieves competitive results on a
link prediction task in citation networks. In contrast to most existing models
for unsupervised learning on graph-structured data and link prediction, our
model can naturally incorporate node features, which significantly improves
predictive performance on a number of benchmark datasets.
^
@https://arxiv.org/pdf/1611.07308.pdf
#topic:neural network
#author:Carl Doersch
#language:english
#medium:paper
Tutorial on Variational Autoencoders
In just three years, Variational Autoencoders (VAEs) have emerged as one
of the most popular approaches to unsupervised learning of complicated
distributions. VAEs are appealing because they are built on top of standard
function approximators (neural networks), and can be trained with stochastic
gradient descent. VAEs have already shown promise in generating many kinds
of complicated data, including handwritten digits, faces, house numbers,
CIFAR images, physical models of scenes, segmentation, and predicting the
future from static images. This tutorial introduces the intuitions behind
VAEs, explains the mathematics behind them, and describes some empirical
behavior. No prior knowledge of variational Bayesian methods is assumed.
^
@https://arxiv.org/pdf/1606.05908.pdf
#topic:neural network
#author:Ronald Yu
#language:english
#medium:paper
A Tutorial on VAEs: From Bayes' Rule to Lossless Compression
The Variational Auto-Encoder (VAE) is a simple, efficient, and popular
deep maximum likelihood model. Though usage of VAEs is widespread, the
derivation of the VAE is not as widely understood. In this tutorial, we will
provide an overview of the VAE and a tour through various derivations and
interpretations of the VAE objective. From a probabilistic standpoint, we will
examine the VAE through the lens of Bayes' Rule, importance sampling, and the
change-of-variables formula. From an information theoretic standpoint, we will
examine the VAE through the lens of lossless compression and transmission
through a noisy channel. We will then identify two common misconceptions
over the VAE formulation and their practical consequences. Finally, we will
visualize the capabilities and limitations of VAEs using a code example
(with an accompanying Jupyter notebook) on toy 2D data.
^
@https://arxiv.org/pdf/2006.10273.pdf
#topic:signed distance field
#author:Chris Green
#language:english
#medium:paper
Improved Alpha-Tested Magnification for Vector Textures and Special Effects
A simple and efficient method is presented which allows improved rendering
of glyphs composed of curved and linear elements. A distance field is
generated from a high resolution image, and then stored into a channel of
a lower-resolution texture. In the simplest case, this texture can then be
rendered simply by using the alphatesting and alpha-thresholding feature of
modern GPUs, without a custom shader. This allows the technique to be used
on even the lowest-end 3D graphics hardware.  With the use of programmable
shading, the technique is extended to perform various special effect
renderings, including soft edges, outlining, drop shadows, multi-colored
images, and sharp corners.
^
@https://steamcdn-a.akamaihd.net/apps/valve/2007/SIGGRAPH2007_AlphaTestedMagnification.pdf
#topic:signed distance field
#author:Yue Jiang
#author:Dantong Ji
#author:Zhizhong Han
#author:Matthias Zwicker
#language:english
#medium:paper
SDFDiff: Differentiable Rendering of Signed Distance Fields for 3D Shape Optimization
We propose SDFDiff, a novel approach for image-based shape optimization using
differentiable rendering of 3D shapes represented by signed distance functions
(SDF).  Compared to other representations, SDFs have the advantage that
they can represent shapes with arbitrary topology, and that they guarantee
watertight surfaces. We apply our approach to the problem of multi-view 3D
reconstruction, where we achieve high reconstruction quality and can capture
complex topology of 3D objects. In addition, we employ a multi-resolution
strategy to obtain a robust optimization algorithm. We further demonstrate
that our SDF-based differentiable renderer can be integrated with deep
learning models, which opens up options for learning approaches on 3D objects
without 3D supervision. In particular, we apply our method to single-view
3D reconstruction and achieve state-of-the-art results.
^
@http://www.cs.umd.edu/~yuejiang/papers/SDFDiff.pdf
#topic:signed distance field
#topic:multi-channel signed distance field
#author:Viktor Chlumsk´
#language:english
#medium:paper
Shape Decomposition for Multi-channel Distance Fields
This work explores the possible improvements to a popular text rendering
technique widely used in 3D applications and video games. It proposes a
universal and efficient method of constructing a multi-channel distance
field for vector-based shapes, such as font glyphs, and describes its usage
in rendering with improved fidelity.
^
@https://github.com/Chlumsky/msdfgen/files/3050967/thesis.pdf
#topic:neural network
#author:Jianwen Xie
#author:Ruiqi Gao
#author:Zilong Zheng
#author:Song-Chun Zhu
#author:Ying Nian Wu
#language:english
#medium:paper
Learning Dynamic Generator Model by Alternating Back-Propagation Through Time
This paper studies the dynamic generator model for spatialtemporal processes
such as dynamic textures and action sequences in video data. In this model,
each time frame of the video sequence is generated by a generator model,
which is a non-linear transformation of a latent state vector, where the
non-linear transformation is parametrized by a top-down neural network. The
sequence of latent state vectors follows a non-linear auto-regressive model,
where the state vector of the next frame is a non-linear transformation of the
state vector of the current frame as well as an independent noise vector that
provides randomness in the transition. The non-linear transformation of this
transition model can be parametrized by a feedforward neural network. We show
that this model can be learned by an alternating back-propagation through time
algorithm that iteratively samples the noise vectors and updates the parameters
in the transition model and the generator model. We show that our training
method can learn realistic models for dynamic textures and action patterns.
^
@http://www.stat.ucla.edu/~jxie/DynamicGenerator/DynamicGenerator_file/doc/DynamicGenerator.pdf
#topic:neural network
#topic:cellular neural network
#author:N H Wulff
#author:J A Hertz t
#language:english
#medium:paper
Learning Cellular Automaton Dynamics with Neural Networks
We have trained networks of E - II units with short-range connections
to simulate simple cellular automata that exhibit complex or chaotic
behaviour. Three levels of learning are possible (in decreasing order of
difficulty): learning the underlying automaton rule, learning asymptotic
dynamical behaviour, and learning to extrapolate the training history. The
levels of learning achieved with and without weight sharing for different
automata provide new insight into their dynamics.
^
@https://papers.nips.cc/paper/703-learning-cellular-automaton-dynamics-with-neural-networks.pdf
#topic:neural network
#topic:cellular neural network
#author:Paolo Arena
#author:Luigi Fortuna
#language:english
#medium:paper
Cellular neural networks: from chaos generation to compexity modelling.

^
@https://www.researchgate.net/profile/Paolo_Arena2/publication/221165625_Cellular_neural_networks_from_chaos_generation_to_compexity_modelling/links/0a85e539fe2db469ce000000/Cellular-neural-networks-from-chaos-generation-to-compexity-modelling.pdf?origin=publication_detail
#topic:cellular automata
#author:Maria Vittoria Avolio
#author:Alessia Errera
#author:Valeria Lupiano
#author:Paolo Mazzanti
#author:Salvatore Di Gregorio
#language:english
#medium:paper
VALANCA: A Cellular Automata Model for Simulating Snow Avalanches
Numerical modelling is a major challenge in the prevention of hazards related
to the occurrence of catastrophic phenomena. Cellular Automata methods were
developed for modelling large scale (extended for kilometres) dangerous surface
flows of different nature such as lava flows, pyroclastic flows, debris
flows, rock avalanches, etc. This paper presents VALANCA, a first version
of a Cellular Automata model, developed for the simulations of dense snow
avalanches. VALANCA is largely based on the most advanced models developed
for flow-like landslides, and adopts some innovations such as outflows
characterized by the position of mass centre and explicit velocity. First
simulations of welldocumented snow avalanches occurred in the Davos region,
Switzerland (i.e. the 2006 Rüchitobel and the 2006 Gotschnawang snow
avalanches) show a satisfying agreement concerning the avalanche path, snow
cover erosion depth, deposit thickness and areal distribution. Furthermore,
preliminary simulations of the Gotschnawang snow-avalanche, by considering
the presence of mitigation structures, were performed.
^
@https://www.nhazca.it/wp-content/uploads/2020/06/VALANCA_2017.pdf
#topic:neural network
#topic:associative neural network
#language:english
#medium:paper
Neural Associative Memories
Neural associative memories (NAM) are neural network models consisting of
neuronlike and synapse-like elements. At any given point in time the state of
the neural network is given by the vector of neural activities, it is called
the activity pattern. Neurons update their activity values based on the inputs
they receive (over the synapses). In the simplest neural network models the
input-output function of a neuron is the identitiy function or a threshold
operation. Note that in the latter case the neural activity state is binary:
active or inactive. Information to be processed by the neural network is
represented by activity patterns (for instance, the representation of a tree
can an activity pattern where active neurons display a tree's picture). Thus,
activity patterns are the representations of the elements processed in the
network. A representation is called sparse if the ratio between active and
inactive neurons is small.
^
@https://courses.cit.cornell.edu/bionb330/readings/Associative%20Memories.pdf
#topic:neural network
#topic:associative neural network
#language:english
#medium:paper
Auto-associative Memory: The First Step in Solving Cocktail Party Problem
One of the most interesting and challenging problems in the area of Artificial
Intelligence is solving the Cocktail Party problem. This is the task of
attending to one speaker among several competing speakers and being able
to switch the attention from one speaker to another at any given time. Human
brain is remarkably efficient in solving this problem. There have been numerous
attempts to emulating this ability in machines. Independent Component Analysis
(ICA) and Blind Source Separation (BSS) are two of the most popular solutions
to this problem but they both fail to generate similar results as human brain
does. They are also very computationally expensive which makes them incapable
of producing results in real-time. Moreover, they generally require at least
two microphones to converge but as we know human brain can also work with
one ear covered. This is evident from the fact that covering one ear does
not make attending to one speaker in a cocktail party any harder.
^
@http://cs229.stanford.edu/proj2013/Youssefi-AutoassociativeMemory.pdf
#topic:cellular automata
#topic:physarum
#author:Jeff Jones
#author:Andrew Adamatzky
#language:english
#medium:paper
Emergence of Self-Organized Amoeboid Movement in a Multi-Agent Approximation of Physarum polycephalum
The giant single-celled slime mould Physarum polycephalum exhibits complex
morphological adaptation and amoeboid movement as it forages for food
and may be seen as a minimal example of complex robotic behaviour. Swarm
computation has previously been used to explore how spatiotemporal complexity
can emerge from, and be distributed within, simple component parts and their
interactions. Using a particle based swarm approach we explore the question
of how to generate collective amoeboid movement from simple non-oscillatory
component parts in a model of P.  polycephalum. The model collective behaves
as a cohesive and deformable virtual material, approximating the local
coupling within the plasmodium matrix. The collective generates de-novo and
complex oscillatory patterns from simple local interactions. The origin
of this motor behaviour is distributed within the collective rendering
is morphologically adaptive, amenable to external influence, and robust to
simulated environmental insult. We show how to gain external influence over the
collective movement by simulated chemo-attraction (pulling towards nutrient
stimuli) and simulated light irradiation hazards (pushing from stimuli). The
amorphous and distributed properties of the collective are demonstrated by
cleaving it into two independent entities and fusing two separate entities
to form a single device, thus enabling it to traverse narrow, separate or
tortuous paths. We conclude by summarising the contribution of the model to
swarm based robotics and soft-bodied modular robotics and discuss the future
potential of such material approaches to the field.
^
@https://arxiv.org/ftp/arxiv/papers/1212/1212.0023.pdf
#topic:casual commutative arrows
#topic:category theory
#topic:pure functional programming
#author:Jeremy Yallop
#author:Hai Liu
#language:english
#medium:paper
Causal Commutative Arrows Revisited
Causal commutative arrows (CCA) extend arrows with additional constructs and
laws that make them suitable for modelling domains such as functional reactive
programming, differential equations and synchronous dataflow. Earlier work
has revealed that a syntactic transformation of CCA computations into normal
form can result in significant performance improvements, sometimes increasing
the speed of programs by orders of magnitude. In this work we reformulate
the normalization as a type class instance and derive optimized observation
functions via a specialization to stream transformers to demonstrate that
the same dramatic improvements can be achieved without leaving the language.
^
@https://www.cl.cam.ac.uk/~jdy22/papers/causal-commutative-arrows-revisited.pdf
#topic:neural network
#topic:generative adversarial network
#author:Ian J. Goodfellow
#author:Jean Pouget-Abadie
#author:Mehdi Mirza
#author:Bing Xu
#author:David Warde-Farley
#author:Sherjil Ozair
#author:Aaron Courville
#author:Yoshua Bengio
#language:english
#medium:paper
Generative Adversarial Nets
We propose a new framework for estimating generative models via an adversarial
process, in which we simultaneously train two models: a generative model
G that captures the data distribution, and a discriminative model D that
estimates the probability that a sample came from the training data rather
than G. The training procedure for G is to maximize the probability of D
making a mistake. This framework corresponds to a minimax two-player game. In
the space of arbitrary functions G and D, a unique solution exists, with G
recovering the training data distribution and D equal to 1 2 everywhere. In
the case where G and D are defined by multilayer perceptrons, the entire
system can be trained with backpropagation.  There is no need for any Markov
chains or unrolled approximate inference networks during either training or
generation of samples. Experiments demonstrate the potential of the framework
through qualitative and quantitative evaluation of the generated samples.
^
@https://papers.nips.cc/paper/5423-generative-adversarial-nets.pdf
#topic:automata
#topic:compression
#author:Takahiro Ota
#author:Hiroyoshi Morita
#language:english
#medium:paper
Relationship between Antidictionary Automata and Compacted Substring Automata
There are two efficient static data compression algorithms called
an antidictionary coding and a lossless data compression via substring
enumeration coding. We prove that both of the encoders are isomorphic.
^
@http://ita.ucsd.edu/workshop/13/files/paper/paper_3113.pdf
#topic:emergence
#topic:cellular automata
#language:english
#medium:paper
An Emergent Approach to Game Design – Development and Play
Player enjoyment is the single-most important goal of games. Games that
are not enjoyable are not bought or played. Within games, enjoyment of the
gameplay hinges on the game world. However, game worlds are often static and
highly scripted, which leads to restricted and shallow gameplay that can
detract from player enjoyment. It is possible that player enjoyment could
be improved by the creation of more flexible game worlds that give players
more freedom and control. One way to create more flexible game worlds is
through the use of an emergent approach to designing game worlds. This thesis
investigates an emergent approach to designing game worlds, as well as the
issues, considerations and implications for game players and developers.
The research reported in this thesis consisted of three main components. The
first component involved conducting a focus group and questionnaire with
players to identify the aspects of current game worlds that affect their
enjoyment. The second component of the research involved investigating an
emergent approach to designing game worlds, in which the Emergent Games
Engine Technology (EmerGEnT) system was developed. The test-bed for the
EmerGEnT system was a strategy game world that was developed using a 3D
games engine, the Auran Jet. The EmerGEnT system consists of three main
components: the environment, objects and agents. The third component of the
research involved evaluating the EmerGEnT system against a set of criteria for
player enjoyment in games, which allowed the system’s role in facilitating
player enjoyment to be defined.  In the player-centred studies, it was found
that players are dissatisfied with the static, inconsistent and unrealistic
elements of current games and that they desire more interactivity, realism
and control. The development and testing of the EmerGEnT system showed that
an emergent game world design, based on cellular automata, can v facilitate
emergent behaviour in a limited domain. The domain modelled by the EmerGEnT
system was heat, fire, rain, fluid flow, pressure and explosions in a
strategy game world. The EmerGEnT system displayed advantages relating to
its ability to dynamically determine and accommodate the specific state of
the game world due to the underlying properties of the cells, objects and
agents. It also provided a model for emergent game worlds, which allowed
more complexity than emergent objects alone. Finally, the evaluation of
enjoyment revealed that incorporating an emergent game world (such as the
EmerGEnT system) into a game could improve player enjoyment in terms of
concentration, challenge, player skills, control and feedback by allowing
more intuitive, consistent and emergent interactions with the game world.
The implications of this research are that cellular automata can facilitate
emergence in games, at least in a limited domain. Also, emergence in games
has the potential to enhance player enjoyment in areas where current game
worlds are weak. Finally, the EmerGEnT system serves as a proof of concept
of using emergence in games, provides a model for simulating environmental
systems in games and was used to identify core issues and considerations
for future development and research of emergent game worlds.
^
@https://www.cp.eng.chula.ac.th/~vishnu/gameResearch/Sweetser_Thesis.pdf
#topic:raymarching
#author:Erik S. V. Jansson
#author:Matthäus G. Chajdas
#author:Jason Lacroix
#author:Ingemar Ragnemalm
#language:english
#medium:paper
Real-Time Hybrid Hair Rendering
Rendering hair is a challenging problem for real-time applications. Besides
complex shading, the sheer amount of it poses a lot of problems, as a human
scalp can have over 100,000 strands of hair, with animal fur often surpassing
a million. For rendering, both strand-based and volume-based techniques have
been used, but usually in isolation. In this work, we present a complete
hair rendering solution based on a hybrid approach. The solution requires no
pre-processing, making it a drop-in replacement, that combines the best of
strand-based and volume-based rendering. Our approach uses this volume not
only as a level-of-detail representation that is raymarched directly, but also
to simulate global effects, like shadows and ambient occlusion in real-time.
^
@https://eriksvjansson.net/papers/rthhr.pdf
#topic:raytracing
#author:Joost van Dongen
#language:english
#medium:paper
Interior Mapping A new technique for rendering realistic buildings
Interior Mapping is a new real-time shader technique that renders the
interior of a building when looking at it from the outside, without the need
to actually model or store this interior. With Interior Mapping, raycasting
in the pixel shader is used to calculate the positions of floors and walls
behind the windows. Buildings are modelled in the same way as without Interior
Mapping and are rendered on the GPU. The number of rooms rendered does not
influence the framerate or memory usage. The rooms are lit and textured
and can have furniture and animated characters. The interiors require very
little additional asset creation and no extra memory. Interior Mapping is
especially useful for adding more depth and detail to buildings in games
and other applications that are situated in large virtual cities
^
@http://www.proun-game.com/Oogst3D/CODING/InteriorMapping/InteriorMapping.pdf
#topic:cellular automata
#author:Hidenosuke Nishio
#author:Youichi Kobuchi
#language:english
#medium:paper
Fault Tolerant Cellular Spaces*
This paper treats the problem of designing a fault tolerant cellular
space which simulates an arbitrary given cellular space in real time. A
cellular space is called fault tolerant if it behaves normally even when its
component cells misoperate.  First such notions as simulation, misoperation,
and K-separated misoperation are defined. Then a new multidimensional coding
of configurations is introduced and explained using as typical example the
two-dimensional space.  The first main result is Theorem 1, which states
that the introduced coding method is useful for correcting errors occurring
at most :once in every K = 5 • 5 rectangle.  The general theory is given
in Section 6, where the second main result is given in the form of Theorem
8. It gives a necessary and sufficient condition for testing whether or not
a given coding is adequate for error correction.
^
@https://core.ac.uk/download/pdf/82831011.pdf
#topic:wildfire
#author:Richard C. Rothermel
#language:english
#medium:book
How to Predict the Spread and Intensity of Forest and Range Fires
This manual documents the procedures for estimating the rate of forward
spread, intensity, flame length, and size of fires burning in forests and
rangelands. It contains instructions for obtaining fuel and weather data,
calculating fire behavior, and interpreting the results for application to
actual fire problems. Potential uses include fire predict ion, fire planning,
dispatching, prescribed fires, and monitoring managed fires.  Included are
sections that deal with fuel model selection, fuel moisture, wind, slope,
calculations with nomograms, TI-59 calculations, point source, line fire,
interpretations of outputs, and growth predictions.
^
@https://www.fs.fed.us/rm/pubs_int/int_gtr143.pdf
#topic:cellular automata
#author:Manzil Zaheer
#author:Michael Wick
#author:Jean-Baptiste Tristan
#author:Alex Smola
#author:Guy L. Steele Jr.
#language:english
#medium:paper
Exponential Stochastic Cellular Automata for Massively Parallel Inference
We propose an embarrassingly parallel, memory efficient inference algorithm for
latent variable models in which the complete data likelihood is in the exponential
family. The algorithm is a stochastic cellular automaton and converges to a valid
maximum a posteriori fixed point. Applied to latent Dirichlet allocation we find
that our algorithm is over an order of magnitude faster than the fastest current
approaches. A simple C++/MPI implementation on a 4-node cluster samples 570
million tokens per second. We process 3 billion documents and achieve predictive
power competitive with collapsed Gibbs sampling and variational inference.
^
@http://learningsys.org/papers/LearningSys_2015_paper_11.pdf
#topic:cellular automata
#language:english
#medium:paper
Neural Cellular Automata Manifold
Very recently, a deep Neural Cellular Automata (NCA) [1] has been proposed
to simulate the complex morphogenesis process with deep networks. This model
learns to grow an image starting from a fixed single pixel. In this paper,
we move a step further and propose a new model that extends the expressive
power of NCA from a single image to an manifold of images. In biological terms,
our approach would play the role of the transcription factors, modulating the
mapping of genes into specific proteins that drive cellular differentiation,
which occurs right before the morphogenesis. We accomplish this by introducing
dynamic convolutions inside an Auto-Encoder architecture, for the first time
used to join two different sources of information, the encoding and cell’s
environment information. The proposed model also extends the capabilities
of the NCA to a general purpose network, which can be used in a broad range
of problems. We thoroughly evaluate our approach in a dataset of synthetic
emojis and also in real images of CIFAR-10.
^
@https://arxiv.org/pdf/2006.12155.pdf
#topic:automata
#topic:polymorphism
#author:John Von Neumann
#author:Arthur W. Burks
#author:Arthur Walter
#language:english
#medium:paper
Theory of self-reproducing automata

^
@https://archive.org/download/theoryofselfrepr00vonn_0/theoryofselfrepr00vonn_0.pdf
#topic:cellular automata
#author:William Gilpin
#language:english
#medium:paper
Cellular automata as convolutional neural networks
Deep learning techniques have recently demonstrated broad success in predicting
complex dynamical systems ranging from turbulence to human speech, motivating
broader questions about how neural networks encode and represent dynamical
rules. We explore this problem in the context of cellular automata (CA),
simple dynamical systems that are intrinsically discrete and thus difficult
to analyze using standard tools from dynamical systems theory. We show that
any CA may readily be represented using a convolutional neural network
with a network-in-network architecture. This motivates our development
of a general convolutional multilayer perceptron architecture, which we
find can learn the dynamical rules for arbitrary CA when given videos of
the CA as training data.  In the limit of large network widths, we find
that training dynamics are nearly identical across replicates, and that
common patterns emerge in the structure of networks trained on different
CA rulesets. We train ensembles of networks on randomly-sampled CA, and we
probe how the trained networks internally represent the CA rules using an
information-theoretic technique based on distributions of layer activation
patterns. We find that CA with simpler rule tables produce trained networks
with hierarchical structure and layer specialization, while more complex
CA produce shallower representations—illustrating how the underlying
complexity of the CA’s rules influences the specificity of these internal
representations. Our results suggest how the entropy of a physical process
can affect its representation when learned by neural networks.
^
@https://arxiv.org/pdf/1809.02942.pdf
#topic:cellular automata
#topic:self-replication
#topic:universal computer
#topic:universal constructor
#author:Tim J. Hutton
#language:english
#medium:paper
Codd’s self-replicating computer
Edgar Codd’s 1968 design for a self-replicating cellular automata machine
has never been implemented. Partly this is due to its enormous size but we
have also identified four problems with the original specification that would
prevent it from working. These problems potentially cast doubt on Codd’s
central assertion, that the 8-state space he presents supports the existence
of machines that can act as universal constructors and computers. However
all these problems were found to be correctable and we present a complete
and functioning implementation after making minor changes to the design and
transition table. The body of the final machine occupies an area that is
22,254 cells wide and 55,601 cells high, comprising over 45 million non-zero
cells in its unsheathed form. The data tape is 208 million cells long,
and self-replication is estimated to take at least 1.7 × 1018 timesteps.
^
@http://www.sq3.org.uk/papers/Hutton_CoddsSelfReplicatingComputer_2010.pdf
#topic:string search
#author:Bertrand Meyer
#language:english
#medium:paper
Incremental String Matching
The problem studied in this paper is to search a given text for occurrences of
certain strings, in the particular case where the set of strings may change
as the search proceeds.  A well-known algorithm by Aho and Corasick applies
to the simpler case when the set of strings is known beforehand and does
not change. This algorithm builds a transition diagram (finite automaton)
from the strings, and uses it as a guide to traverse the text. The search can
then be done in linear time.  We show how this algorithm can be modified to
allow incremental diagram construction, so that new keywords may be entered
at any time during the search. The incremental algorithm presented essentially
retains the time and space complexities of the non-incremental one.
^
@http://se.ethz.ch/~meyer/publications/string/string_matching.pdf
#topic:string search
#author:Bruce William Watson
#language:english
#medium:paper
Taxonomies and Toolkits of Regular Language Algorithms

^
@https://web.archive.org/web/20120324141930if_/http://www.diku.dk:80/hjemmesider/ansatte/henglein/papers/watson1995.pdf
#topic:javascript
#topic:exception
#topic:continuation-passing style
#author:Florian Loitsch
#language:english
#medium:paper
Exceptional Continuations in JavaScript
JavaScript, the main language for web-site development, does not feature
continuation. However, as part of client-server communication they would be
useful as a means to suspend the currently running execution.  In this paper
we present our adaption of exception-based continuations to JavaScript. The
enhanced technique deals with closures and features improvements that reduce
the cost of the work-around for the missing goto-instruction. We furthermore
propose a practical way of dealing with exception-based continuations in the
context of non-linear executions, which frequently happen due to callbacks.
Our benchmarks show that under certain conditions continuations are
still expensive, but are often viable. Especially compilers translating
to JavaScript could benefit from static control flow analyses to make
continuations less costly
^
@http://www.schemeworkshop.org/2007/procPaper4.pdf
#topic:file format
#author:James D Murray
#author:William VanRyper
#language:english
#medium:book
Encyclopedia of graphics file formats

^
@https://ia800202.us.archive.org/11/items/mac_Graphics_File_Formats_Second_Edition_1996/Graphics_File_Formats_Second_Edition_1996.pdf
#topic:dithering
#topic:parallel computation
#topic:error-diffusion
#author:Panagiotis Takis Metaxas
#language:english
#medium:paper
Parallel Digital Halftoning by Error-Diffusion
Digital halftoning, or dithering, is the technique commonly used to render a
color or grayscale image on a printer, a computer monitor or other bi-level
displays. A particular halftoning technique that has been used extensively
in the past is the socalled error diffusion technique. For a number of
years it was believed that this technique is inherently sequential and
could not be parallelized. In this paper we present and analyze a simple,
yet optimal, error-diffusion parallel algorithm for digital halftoning and we
discuss an implementation on a parallel machine. In particular, we describe
implementations on data-parallel computers that contain linear arrays and
two-dimensional meshes of processing elements. Our algorithm runs in 2·n+m
parallel steps, a considerable improvement over the 10·m·n sequential
algorithm. We expect that this research will lead to the development of
faster printers and larger high-resolution monitors
^
@http://cs.wellesley.edu/~pmetaxas/pck50-metaxas.pdf
#topic:dithering
#topic:error-diffusion
#topic:parallel computation
#topic:Ishan Misra
#topic:P J Narayanan
#author:Aditya Deshpande
#language:english
#medium:paper
Hybrid Implementation of Error Diffusion Dithering
Many image filtering operations provide ample parallelism, but progressive
non-linear processing of images is among the hardest to parallelize due to
long, sequential, and non-linear data dependency. A typical example of such
an operation is error diffusion dithering, exemplified by the Floyd-Steinberg
algorithm. In this paper, we present its parallelization on multicore CPUs
using a block-based approach and on the GPU using a pixel based approach. We
also present a hybrid approach in which the CPU and the GPU operate in parallel
during the computation. High Performance Computing has traditionally been
associated with high end CPUs and GPUs. Our focus is on everyday computers
such as laptops and desktops, where significant compute power is available
on the GPU as on the CPU. Our implementation can dither an 8K × 8K image on
an off-the-shelf laptop with an Nvidia 8600M GPU in about 400 milliseconds
when the sequential implementation on its CPU took about 4 seconds.
^
@http://www.cs.cmu.edu/~./imisra/projects/dithering/HybridDithering.pdf
#topic:data type
#author:Iavor S. Diatchki
#author:Mark P. Jones
#author:Rebekah Leslie
#language:english
#medium:paper
High-level Views on Low-level Representations
This paper explains how the high-level treatment of datatypes in
functional languages—using features like constructor functions and
pattern matching—can be made to coexist with bitdata. We use this term
to describe the bit-level representations of data that are required in the
construction of many different applications, including operating systems,
device drivers, and assemblers. We explain our approach as a combination of
two language extensions, each of which could potentially be adapted to any
modern functional language. The first adds simple and elegant constructs
for manipulating raw bitfield values, while the second provides a view-like
mechanism for defining distinct new bitdata types with fine-control over the
underlying representation. Our design leverages polymorphic type inference,
as well as techniques for improvement of qualified types, to track both the
type and the width of bitdata structures. We have implemented our extensions
in a small functional language interpreter, and used it to show that our
approach can handle a wide range of practical bitdata types.
^
@http://web.cecs.pdx.edu/~mpj/pubs/bitdata-icfp05.pdf
#topic:bayesian network
#topic:probability
#author:Daphne Koller
#author:Nir Friedman
#medium:book
#language:english
Probabilistic Graphical Models
Most tasks require a person or an automated system to reason: to take
the available information and reach conclusions, both about what might be
true in the world and about how to act.  For example, a doctor needs to
take information about a patient — his symptoms, test results, personal
characteristics (gender, weight) — and reach conclusions about what
diseases he may have and what course of treatment to undertake. A mobile
robot needs to synthesize data from its sonars, cameras, and other sensors
to conclude where in the environment it is and how to move so as to reach
its goal without hitting anything. A speech-recognition system needs to take
a noisy acoustic signal and infer the words spoken that gave rise to it.
In this book, we describe a general framework that can be used to allow a
computer system to answer questions of this type. In principle, one could
write a special-purpose computer program for every domain one encounters and
every type of question that one may wish to answer. The resulting system,
although possibly quite successful at its particular task, is often very
brittle: If our application changes, significant changes may be required to
the program.  Moreover, this general approach is quite limiting, in that it
is hard to extract lessons from one successful solution and apply it to one
which is very different.
^
@https://djsaunde.github.io/read/books/pdfs/probabilistic%20graphical%20models.pdf
#author:Marc Ohm
#author:Henrik Plate
#author:Arnold Sykosch
#author:Michael Meier
#topic:open source
#topic:security
#topic:vulnrability
#language:english
#medium:paper
Backstabber’s Knife Collection: A Review of Open Source Software Supply Chain Attacks
A software supply chain attack is characterized by the injection of malicious
code into a software package in order to compromise dependent systems
further down the chain. Recent years saw a number of supply chain attacks
that leverage the increasing use of open source during software development,
which is facilitated by dependency managers that automatically resolve,
download and install hundreds of open source packages throughout the software
life cycle.  This paper presents a dataset of 174 malicious software packages
that were used in real-world attacks on open source software supply chains,
and which were distributed via the popular package repositories npm, PyPI,
and RubyGems. Those packages, dating from November 2015 to November 2019,
were manually collected and analyzed. The paper also presents two general
attack trees to provide a structured overview about techniques to inject
malicious code into the dependency tree of downstream users, and to execute
such code at different times and under different conditions.  This work
is meant to facilitate the future development of preventive and detective
safeguards by open source and research communities.
^
@https://arxiv.org/pdf/2005.09535.pdf
#topic:chunked sequence
#topic:finger-tree
#author:Umut A. Acar
#author:Arthur Chargu´eraud
#author:Mike Rainey
#language:english
#medium:paper
Theory and Practice of Chunked Sequences
Sequence data structures, i.e., data structures that provide
operations on an ordered set of items, are heavily used by many
applications. For sequence data structures to be efficient in practice, it
is important to amortize expensive data-structural operations by chunking
a relatively small, constant number of items together, and representing
them by using a simple but fast (at least in the small scale) sequence
data structure, such as an array or a ring buffer. In this paper, we
present chunking techniques, one direct and one based on bootstrapping,
that can reduce the practical overheads of sophisticated sequence data
structures, such as finger trees, making them competitive in practice with
specialpurpose data structures. We prove amortized bounds showing that our
chunking techniques reduce runtime by amortizing expensive operations over a
user-defined chunk-capacity parameter. We implement our techniques and show
that they perform well in practice by conducting an empirical evaluation. Our
evaluation features comparisons with other carefully engineered and optimized
implementations.
^
@http://deepsea.inria.fr/chunkedseq/esa-2014-long.pdf
#topic:hazard pointer
#topic:lock-free
#topic:concurrency
#author:Maged M. Michael
#language:english
#medium:paper
Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects
Lock-free objects offer significant performance and reliability advantages
over conventional lock-based objects. However, the lack of an efficient
portable lock-free method for the reclamation of the memory occupied by
dynamic nodes removed from such objects is a major obstacle to their wide
use in practice. This paper presents hazard pointers, a memory management
methodology that allows memory reclamation for arbitrary reuse. It is very
efficient, as demonstrated by our experimental results. It is suitable for
user-level applications—as well as system programs—without dependence
on special kernel or scheduler support. It is wait-free. It requires only
single-word reads and writes for memory access in its core operations. It
allows reclaimed memory to be returned to the operating system. In addition,
it offers a lock-free solution for the ABA problem using only practical
single-word instructions. Our experimental results on a multiprocessor system
show that the new methodology offers equal and, more often, significantly
better performance than other memory management methods, in addition to
its qualitative advantages regarding memory reclamation and independence
of special hardware support. We also show that lock-free implementations of
important object types, using hazard pointers, offer comparable performance
to that of efficient lock-based implementations under no contention and no
multiprogramming, and outperform them by significant margins under moderate
multiprogramming and/or contention, in addition to guaranteeing continuous
progress and availability, even in the presence of thread failures and
arbitrary delays.
^
@https://www.eecg.utoronto.ca/~amza/ece1747h/papers/hazard_pointers.pdf
#topic:hazard pointer
#topic:lock-free
#author:Afroza Sultana
#author:Helen A. Cameron
#author:Peter C. J. Graham
#language:english
#medium:paper
Concurrent B-trees with Lock-free Techniques
B-trees and their variants are efficient data structures for finding records
in a large collection (e.g., databases). The efficiency of B-trees increases
when a number of users can manipulate the tree simultaneously. Many algorithms
have been developed over the last three decades to achieve both concurrency
and consistency in B-trees. However, current lock-based concurrency-control
techniques limit concurrency. Moreover, lock-based B-trees suffer from
certain negative scheduling anomalies, such as deadlock, convoying and
priority inversion. Lock-free concurrency-control techniques using, for
example, Compare And Swap (CAS) can provide improved concurrent access to
data structures including B-trees and other search structures. Besides this,
correctly designed lock-free techniques prevent deadlock, convoying and
priority inversion. Considering the advantages of lock-free techniques for
other concurrent data structures, we develop a lock-free B-tree to support
high performance concurrent in-memory searching in a Non Uniform Memory Access
(NUMA) parallel computing environment.  The use and parallelization of B-trees
have both been widely explored in the past—primarily for application to
database implementation and, hence, disk-based operations. Moving B-trees into
memory for use in new online searching applications, however, fundamentally
changes the characteristics of managing them and will allow us to effectively
exploit the use of lock-free techniques, something that has previously not
been applicable to B-trees.
^
@https://www.cs.umanitoba.ca/~hacamero/Research/BtreeTechrpt2011.pdf
#topic:hazard pointer
#author:Andrei Alexandrescu
#author:Maged Michael
#language:english
#medium:paper
Lock-Free Data Structures with Hazard Pointers

^
@http://erdani.com/publications/cuj-2004-12.pdf
#topic:category theory
#author:Philip Wadler
#language:english
#medium:paper
Monads for functional programming
The use of monads to structure functional programs is described. Monads
provide a convenient framework for simulating effects found in other languages,
such as global state, exception handling, output, or non-determinism. Three
case studies are looked at in detail: how monads ease the modification of
a simple evaluator; how monads act as the basis of a datatype of arrays
subject to in-place update; and how monads can be used to build parsers.
^
@http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf
#topic:genetic algorithm
#author:Melanie Mitchell
#medium:book
#language:english
An Introduction to Generic Algorithms
Genetic algorithms have been used in science and engineering as adaptive
algorithms for solving practical problems and as computational models of
natural evolutionary systems. This brief, accessible introduction describes
some of the most interesting research in the field and also enables readers
to implement and experiment with genetic algorithms on their own. It focuses
in depth on a small set of important and interesting topics—particularly
in machine learning, scientific modeling, and artificial life—and reviews
a broad span of research, including the work of Mitchell and her colleagues.

The descriptions of applications and modeling projects stretch beyond the
strict boundaries of computer science to include dynamical systems theory,
game theory, molecular biology, ecology, evolutionary biology, and population
genetics, underscoring the exciting "general purpose" nature of genetic
algorithms as search methods that can be employed across disciplines.

An Introduction to Genetic Algorithms is accessible to students and researchers
in any scientific discipline. It includes many thought and computer exercises
that build on and reinforce the reader's understanding of the text. The first
chapter introduces genetic algorithms and their terminology and describes
two provocative applications in detail. The second and third chapters look
at the use of genetic algorithms in machine learning (computer programs,
data analysis and prediction, neural networks) and in scientific models
(interactions among learning, evolution, and culture; sexual selection;
ecosystems; evolutionary activity). Several approaches to the theory of genetic
algorithms are discussed in depth in the fourth chapter. The fifth chapter
takes up implementation, and the last chapter poses some currently unanswered
questions and surveys prospects for the future of evolutionary computation.
^
@https://boente.eti.br/fuzzy/ebook-fuzzy-mitchell.pdf
#topic:markov process
#author:John C. Baez
#language:english
#medium:paper
Coarse-Graining Open Markov Processes
Coarse-graining is a standard method of extracting a simpler Markov
process from a more complicated one by identifying states. Here we extend
coarse-graining to ‘open’ Markov processes: that is, those where
probability can flow in or out of certain states called ‘inputs’ and
‘outputs’. One can build up an ordinary Markov process from smaller open
pieces in two basic ways: composition, where we identify the outputs of
one open Markov process with the inputs of another, and tensoring, where
we set two open Markov processes side by side. In previous work, Fong,
Pollard and the first author showed that these constructions make open
Markov processes into the morphisms of a symmetric monoidal category. Here
we go further by constructing a symmetric monoidal double category where the
2-morphisms include ways of coarse-graining open Markov processes. We also
extend the already known ‘black-boxing’ functor from the category of
open Markov processes to our double category. Black-boxing sends any open
Markov process to the linear relation between input and output data that
holds in steady states, including nonequilibrium steady states where there
is a nonzero flow of probability through the process. To extend black-boxing
to a functor between double categories, we need to prove that black-boxing
is compatible with coarse-graining.
^
@https://arxiv.org/pdf/1710.11343.pdf
#topic:file format
#language:english
#medium:book
Internet File Formats 1995

^
@https://ia801308.us.archive.org/2/items/mac_Internet_File_Formats_1995/Internet_File_Formats_1995.pdf
#topic:distributed systems
#author:Marcos K. Aguilera
#author:Arif Merchant
#author:Mehul Shah
#author:Alistair Veitch
#author:Christos Karamanolis
#medium:paper
#language:english
Sinfonia: a new paradigm for building scalable distributed systems
We propose a new paradigm for building scalable distributed systems. Our
approach does not require dealing with message-passing protocols—a major
complication in existing distributed systems.  Instead, developers just design
and manipulate data structures within our service called Sinfonia. Sinfonia
keeps data for applications on a set of memory nodes, each exporting a
linear address space. At the core of Sinfonia is a novel minitransaction
primitive that enables efficient and consistent access to data, while hiding
the complexities that arise from concurrency and failures. Using Sinfonia,
we implemented two very different and complex applications in a few months:
a cluster file system and a group communication service. Our implementations
perform well and scale to hundreds of machines.
^
@https://www.cs.princeton.edu/courses/archive/fall08/cos597B/papers/sinfonia.pdf
#topic:distributed systems
#author:Tim Kraska
#author:Gene Pang
#author:Michael J. Franklin
#author:Samuel Madden
#author:Alan Fekete
#medium:paper
#language:english
MDCC: Multi-Data Center Consistency
Replicating data across multiple data centers allows using data closer to
the client, reducing latency for applications, and increases the availability
in the event of a data center failure. MDCC (Multi-Data Center Consistency)
is an optimistic commit protocol for geo-replicated transactions, that does
not require a master or static partitioning, and is strongly consistent at
a cost similar to eventually consistent protocols. MDCC takes advantage of
Generalized Paxos for transaction processing and exploits commutative updates
with value constraints in a quorum-based system. Our experiments show that
MDCC outperforms existing synchronous transactional replication protocols,
such as Megastore, by requiring only a single message round-trip in the normal
operational case independent of the master-location and by scaling linearly
with the number of machines as long as transaction conflict rates permit.
^
@https://amplab.cs.berkeley.edu/wp-content/uploads/2013/03/mdcc-eurosys13.pdf
#topic:mathematics
#topic:informatics
#author:Eric Lehman
#author:F Thomson Leighton
#author:Albert R Meyer
#medium:book
#language:english
Mathematics for Computer Science

^
@https://courses.csail.mit.edu/6.042/spring17/mcs.pdf
#topic:containers
#author:Adinda Riztia Putri
#author:Rendy Munadi
#author:Ridha Muldina Negara
#medium:paper
#language:english
Performance analysis of multi services on container Docker, LXC, and LXD
The emergence of the container in various cloud platforms from Open Stack
to Google Cloud Platform has marked the industry interest in opting for
container as their cloud service solution. However, the cloud users should
aware of performance overheads of different virtualization solutions in
order to avoid quality of service degradation because different container
platforms delivered different performances. This research evaluated how
different container platforms (Docker, LXC, and LXD) impacted in running
different TCP services and also measured system performance of each container
compared to the native system without any container solution based on
overall performance metrics. This research focuses on the three most used
PaaS: FTP Server, Web Server, and Mail Server. Related to previous works,
our evaluation results show that performance could vary between containers.
In terms of system performance, LXD shows better performance while server
performance result varies depending on what service is being evaluated.
^
@http://www.beei.org/index.php/EEI/article/viewFile/1953/1596
#topic:optimization
#author:Bruce Tesar
#language:paper
#medium:paper
Computing Optimal Forms in Optimality Theory: Basic Syllabification
In Optimality Theory, grammaticality is defined in terms of optimization
over a large (often infinite) space of candidates. This raises the question
of how grammatical forms might be computed. This paper presents an analysis
of the Basic CV Syllable Theory (Prince & Smolensky 1993) showing that,
despite the nature of the formal definition, computing the optimal form does
not require explicitly generating and evaluating all possible candidates. A
specific algorithm is detailed which computes the optimal form in time
that is linear in the length of the input. This algorithm will work for
any grammar in Optimality Theory employing regular position structures and
universal constraints which may be evaluated on the basis of local information
^
@http://roa.rutgers.edu/files/52-0295/roa-52-tesar-3.pdf
#topic:simd
#author:Franz Franchetti
#author:Stefan Kral
#author:Juergen Lorenz
#author:Christoph W. Ueberhuber
#language:english
#medium:paper
Efficient Utilization of SIMD Extensions
This paper targets automatic performance tuning of numerical kernels in the
presence of multi-layered memory hierarchies and SIMD parallelism. The studied
SIMD instruction set extensions include Intel’s SSE family, AMD’s 3DNow!,
Motorola’s AltiVec, and IBM’s BlueGene/L SIMD instructions.  FFTW, ATLAS,
and SPIRAL demonstrate that near-optimal performance of numerical kernels
across a variety of modern computers featuring deep memory hierarchies can
be achieved only by means of automatic performance tuning. These software
packages generate and optimize ANSI C code and feed it into the target
machine’s general purpose C compiler to maintain portability.  The scalar
C code produced by performance tuning systems poses a severe challenge for
vectorizing compilers. The particular code structure hampers automatic
vectorization and thus inhibits satisfactory performance on processors
featuring short vector extensions.  This paper describes special purpose
compiler technology that supports automatic performance tuning on machines with
vector instructions. The work described includes (i) symbolic vectorization of
DSP transforms, (ii) straight-line code vectorization for numerical kernels,
and (iii) compiler backends for straight-line code with vector instructions.
Methods from all three areas were combined with FFTW, SPIRAL, and ATLAS to
optimize both for memory hierarchy and vector instructions. Experiments
show that the presented methods lead to substantial speed-ups (up to 1.8
for two-way and 3.3 for four-way vector extensions) over the best scalar
C codes generated by the original systems as well as roughly matching the
performance of hand-tuned vendor libraries.
^
@http://users.ece.cmu.edu/~franzf/papers/ieee-si.pdf
#topic:parsing
#author:Dan Klein
#author:Christopher D. Manning
#medium:paper
#language:english
A* Parsing: Fast Exact Viterbi Parse Selection
We present an extension of the classic A* search procedure to tabular PCFG
parsing. The use of A* search can dramatically reduce the time required to
find a best parse by conservatively estimating the probabilities of parse
completions. We discuss various estimates and give efficient algorithms
for computing them. On average-length Penn treebank sentences, our most
detailed estimate reduces the total number of edges processed to less than
3% of that required by exhaustive parsing, and a simpler estimate, which
requires less than a minute of precomputation, reduces the work to less
than 5%. Unlike best-first and finite-beam methods for achieving this kind
of speed-up, an A* method is guaranteed to find the most likely parse, not
just an approximation.  Our parser, which is simpler to implement than an
upward-propagating best-first parser, is correct for a wide range of parser
control strategies and maintains worst-case cubic time.
^
@https://nlp.stanford.edu/pubs/klein2003astar.pdf
#topic:parsing
#author:Mark Johnson
#language:english
#medium:paper
Parsing in Parallel on Multiple Cores and GPUs
This paper examines the ways in which parallelism can be used to speed the
parsing of dense PCFGs. We focus on two kinds of parallelism here: Symmetric
Multi-Processing (SMP) parallelism on shared-memory multicore CPUs, and
Single-Instruction MultipleThread (SIMT) parallelism on GPUs. We describe how
to achieve speed-ups over an already very efficient baseline parser using both
kinds of technology. For our dense PCFG parsing task we obtained a 60×speed-up
using SMP and SSE parallelism coupled with a cache-sensitive algorithm design,
parsing section 24 of the Penn WSJ treebank in a little over 2 secs.
^
@https://www.aclweb.org/anthology/U11-1006.pdf
#topic:parser
#author:Jenny Rose Finkel
#author:Alex Kleeman
#author:Christopher D. Manning
#language:english
#medium:paper
Efficient, Feature-based, Conditional Random Field Parsing
Discriminative feature-based methods are widely used in natural
language processing, but sentence parsing is still dominated by generative
methods. While prior feature-based dynamic programming parsers have restricted
training and evaluation to artificially short sentences, we present the first
general, featurerich discriminative parser, based on a conditional random
field model, which has been successfully scaled to the full WSJ parsing
data. Our efficiency is primarily due to the use of stochastic optimization
techniques, as well as parallelization and chart prefiltering.  On WSJ15,
we attain a state-of-the-art F-score of 90.9%, a 14% relative reduction in
error over previous models, while being two orders of magnitude faster. On
sentences of length 40, our system achieves an F-score of 89.0%, a 36%
relative reduction in error over a generative baseline.
^
@https://nlp.stanford.edu/pubs/discpcfg.pdf
#topic:constraint solving
#author:Greg J. Badros
#author:Alan Borning
#author:Peter J. Stuckey
#language:english
#medium:paper
The Cassowary Linear Arithmetic Constraint Solving Algorithm
Linear equality and inequality constraints arise naturally in specifying
many aspects of user interfaces, such as requiring that one window be to
the left of another, requiring that a pane occupy the leftmost third of
a window, or preferring that an ob ject be contained within a rectangle
if possible. Previous constraint solvers designed for user interface
applications cannot handle simultaneous linear equations and inequalities
effciently. This is a ma jor limitation, as such systems of constraints
arise often in natural declarative specifcations. We describe Cassowary,
an incremental algorithm based on the dual simplex method, which can solve
such systems of constraints effciently. We have implemented the algorithm
as part of a constraint solving toolkit. We discuss the implementation of
the toolkit, its application programming interface, and its performance.
^
@https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf
#topic:constraint solving
#author:Chen Wei
#author:Lingxi Xie
#author:Xutong Ren
#author:Yingda Xia
#author:Chi Su
#author:Jiaying Liu
#author:Qi Tian
#author:Alan L. Yuille2
#language:english
#medium: paper
Iterative Reorganization with Weak Spatial Constraints: Solving Arbitrary Jigsaw Puzzles for Unsupervised Representation Learning
Learning visual features from unlabeled image data is an important yet
challenging task, which is often achieved by training a model on some
annotation-free information.  We consider spatial contexts, for which we
solve so-called jigsaw puzzles, i.e., each image is cut into grids and then
disordered, and the goal is to recover the correct configuration. Existing
approaches formulated it as a classification task by defining a fixed mapping
from a small subset of configurations to a class set, but these approaches
ignore the underlying relationship between different configurations and also
limit their applications to more complex scenarios.  This paper presents a
novel approach which applies to jigsaw puzzles with an arbitrary grid size
and dimensionality. We provide a fundamental and generalized principle,
that weaker cues are easier to be learned in an unsupervised manner and also
transfer better. In the context of puzzle recognition, we use an iterative
manner which, instead of solving the puzzle all at once, adjusts the order of
the patches in each step until convergence. In each step, we combine both unary
and binary features of each patch into a cost function judging the correctness
of the current configuration. Our approach, by taking similarity between
puzzles into consideration, enjoys a more efficient way of learning visual
knowledge. We verify the effectiveness of our approach from two aspects. First,
it solves arbitrarily complex puzzles, including high-dimensional puzzles,
that prior methods are difficult to handle. Second, it serves as a reliable
way of network initialization, which leads to better transfer performance in
visual recognition tasks including classification, detection and segmentation.
^
@https://openaccess.thecvf.com/content_CVPR_2019/papers/Wei_Iterative_Reorganization_With_Weak_Spatial_Constraints_Solving_Arbitrary_Jigsaw_Puzzles_CVPR_2019_paper.pdf
#topic:constraint solving
#author:Ingrid Daubechies
#author:Gerd Teschke
#author:Luminita Vese
#language:english
#medium:paper
Iteratively Solving Linear Inverse Problems Under General Convex Constraints
We consider linear inverse problems where the solution is assumed to fulfill
some general homogeneous convex constraint. We develop an algorithm that
amounts to a projected Landweber iteration and that provides and iterative
approach to the solution of this inverse problem. For relatively moderate
assumptions on the constraint we can always prove weak convergence of the
iterative scheme. In certain cases, i.e. for special families of convex
constraints, weak convergence implies norm convergence. The presented approach
covers a wide range of problems, e.g. Besov– or BV–restoration for which
we present also numerical experiments in the context of image processing.
^
@https://www.math.ucla.edu/~lvese/PAPERS/DaubechiesTeschkeVese.pdf
#topic:constraint solving
#author:Sharlee Climer
#author:Weixiong Zhang
#language:english
#medium:paper
Cut-and-solve: An iterative search strategy for combinatorial optimization problems
Branch-and-bound and branch-and-cut use search trees to identify optimal
solutions to combinatorial optimization problems.  In this paper, we introduce
an iterative search strategy which we refer to as cut-and-solve and prove
optimality and termination for this method. This search is different from
traditional tree search as there is no branching. At each node in the search
path, a relaxed problem and a sparse problem are solved and a constraint
is added to the relaxed problem. The sparse problems provide incumbent
solutions. When the constraining of the relaxed problem becomes tight enough,
its solution value becomes no better than the incumbent solution value. At
this point, the incumbent solution is declared to be optimal. This strategy is
easily adapted to be an anytime algorithm as an incumbent solution is found
at the root node and continuously updated during the search.  Cut-and-solve
enjoys two favorable properties. Since there is no branching, there are
no “wrong” subtrees in which the search may get lost. Furthermore, its
memory requirement is negligible. For these reasons, it has potential for
problems that are difficult to solve using depth-first or best-first search
tree methods.  In this paper, we demonstrate the cut-and-solve strategy by
implementing a generic version of it for the Asymmetric Traveling Salesman
Problem (ATSP). Our unoptimized implementation outperformed state-of-the-art
solvers for five out of seven real-world problem classes of the ATSP. For
four of these classes, cut-and-solve was able to solve larger (sometimes
substantially larger) problems. Our code is available at our websites.
^
@https://www.cse.wustl.edu/~zhang/publications/cutsolve.pdf
#topic:game artificial intelligence
#topic:F.E.A.R
#author:Jeff Orkin
#language:english
#medium:paper
Three States and a Plan: The A.I. of F.E.A.R.
If the audience of GDC was polled to list the most common A.I. techniques
applied to games, undoubtedly the top two answers would be A* and Finite State
Machines (FSMs). Nearly every game that exhibits any A.I. at all uses some form
of an FSM to control character behavior, and A* to plan paths. F.E.A.R. uses
these techniques too, but in unconventional ways. The FSM for characters in
F.E.A.R. has only three states, and we use A* to plan sequences of actions as
well as to plan paths. This paper focuses on applying planning in practice,
using F.E.A.R. as a case study. The emphasis is demonstrating how the planning
system improved the process of developing character behaviors for F.E.A.R.
We wanted F.E.A.R. to be an over-the-top action movie experience, with combat
as intense as multiplayer against a team of experienced humans. A.I. take
cover, blind fire, dive through windows, flush out the player with grenades,
communicate with teammates, and more. So it seems counter-intuitive that
our state machine would have only three states.
^
@http://alumni.media.mit.edu/~jorkin/gdc2006_orkin_jeff_fear.pdf
#topic:logic programming
#topic:logic plannig
#author:Thomas Eiter
#author:Wolfgang Faber
#author:Nicola Leone
#author:Gerald Pfeifer
#author:Axel Polleres
#language:english
#medium:paper
A logic programming approach to knowledge-state planning, II: The DLVK system ✩
In Part I of this series of papers, we have proposed a new logic-based
planning language, called K. This language facilitates the description of
transitions between states of knowledge and it is well suited for planning
under incomplete knowledge. Nonetheless, K also supports the representation of
transitions between states of the world (i.e., states of complete knowledge)
as a special case, proving to be very flexible. In the present Part II, we
describe the DLVK planning system, which implements K on top of the disjunctive
logic programming system DLV. This novel planning system allows for solving
hard planning problems, including secure planning under incomplete initial
states (often called conformant planning in the literature), which cannot
be solved at all by other logic-based planning systems such as traditional
satisfiability planners. We present a detailed comparison of the DLVK system
to several state-of-the-art conformant planning systems, both at the level
of system features and on benchmark problems. Our results indicate that,
thanks to the power of knowledge-state problem encoding, the DLVK system is
competitive even with special purpose conformant planning systems, and it often
supplies a more natural and simple representation of the planning problems.
^
@https://core.ac.uk/download/pdf/82567995.pdf
#topic:logic programming
#topic:logic planning
#author:Tran Cao Son
#author:Enrico Pontelli
#language:english
#medium:paper
Planning with Preferences using Logic Programming
We present a declarative language, PP, for the high-level specification
of preferences between possible solutions (or trajectories) of a planning
problem. This novel language allows users to elegantly express non-trivial,
multi-dimensional preferences and priorities over such preferences. The
semantics of PP allows the identification of most preferred trajectories
for a given goal. We also provide an answer set programming implementation
of planning problems with PP preferences.
^
@https://www.cs.nmsu.edu/~tson/papers/tplp-plan-prefs.pdf
#topic:prolog
#author:Ulle Endriss
#language:english
#medium:book
An Introduction to Prolog Programming

^
@https://staff.science.uva.nl/u.endriss/teaching/prolog/prolog.pdf
#topic:package management
#topic:transactional memory
#author:Eelco Dolstra
#author:Merijn de Jonge
#author:Eelco Visser
#language:english
#medium:paper
Nix: A Safe and Policy-Free System for Software Deployment
Existing systems for software deployment are neither safe nor sufficiently
flexible. Primary safety issues are the inability to enforce reliable
specification of component dependencies, and the lack of support for multiple
versions or variants of a component. This renders deployment operations
such as upgrading or deleting components dangerous and unpredictable. A
deployment system must also be flexible (i.e., policy-free) enough to support
both centralised and local package management, and to allow a variety
of mechanisms for transferring components. In this paper we present Nix,
a deployment system that addresses these issues through a simple technique
of using cryptographic hashes to compute unique paths for component instances.
^
@https://edolstra.github.io/pubs/nspfssd-lisa2004-final.pdf
#topic:subtyping
#topic:type theory
#topic:type inference
#author:Lionel Parreaux
#language:english
#medium:paper
The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy
MLsub extends traditional Hindley-Milner type inference with subtyping while
preserving compact principal types, an exciting new development. However,
its specification in terms of biunification is difficult to understand,
relying on the new concepts of bisubstitution and polar types, and making
use of advanced notions from abstract algebra. In this paper, we show that
these are in fact not essential to understanding the mechanisms at play
in MLsub. We propose an alternative algorithm called Simple-sub, which can
be implemented efficiently in under 500 lines of code (including parsing,
simplification, and pretty-printing), looks more familiar, and is easier
to understand. We present an experimental evaluation of Simple-sub against
MLsub on a million randomly-generated well-scoped expressions, showing that
the two systems agree. The mutable automaton-based implementation of MLsub
is quite far from its algebraic specification, leaving a lot of space for
errors; in fact, our evaluation uncovered several bugs in it. We sketch more
straightforward soundness and completeness arguments for Simple-sub, based
on a syntactic specification of the type system. This paper is meant to be
light in formalism, rich in insights, and easy to consume for prospective
designers of new type systems and programming languages. In particular,
no abstract algebra is inflicted on readers.
^
@https://infoscience.epfl.ch/record/278576/files/%5Bv1.8%5D%20simple-essence-algebraic-subtyping.pdf
#topic:proof carrying code
#author:Manish Mahajan
#language:english
#medium:paper
Proof Carrying Code
Proof-Carrying Code (PCC) is a technique that can be used for safe execution
of untrusted code. In a typical instance of PCC, a code receiver establishes
a set of safety rules that guarantee safe behavior of programs, and the code
producer creates a formal safety proof that proves, for the untrusted code,
adherence to the safety rules. Then, the receiver is able to use a simple
and fast proof validator to check, with certainty that the proof is valid
and hence the untrusted code is safe to execute.
^
@https://www.researchgate.net/profile/Manish_Mahajan/publication/235940398_Proof_Carrying_Code/links/0c960515cf2dd5f654000000/Proof-Carrying-Code.pdf
#topic:delta updates
#topic:edit distance
#author:Colin Percival
#language:english
#medium:paper
Na¨ıve Differences of Executable Code
The increasing frequency with which serious security flaws are discovered
and the increasing rapidity with which they are exploited have made it
necessary for programs to be updated far more frequently than in the past.
While binary updates are generally far more convenient than source code
updates, the distribution of pointers throughout executable files makes it
much harder to produce compact patches.  In contrast to earlier work which
relies upon knowledge of the internal structure of a particular platform’s
executable files, we describe a na¨ıve method which produces competitively
small patches for any executable files.
^
@http://www.daemonology.net/papers/bsdiff.pdf
#topic:neural network
#author:Felix Gers
#author:Jurgen Schmidhuber
#language:english
#medium:paper
Recurrent nets that time and count
The size of the time intervals between events conveys information essential
for numerous sequential tasks such as motor control and rhythm detection. While
hidden Markov models tend to ignore this information, recurrent neural networks
(RNN) can in principle learn to make use of it. We focus on long short-term
memory (LSTM) because it usually outperforms other RNN. Surprisingly,
LSTM augmented by “peephole connections” from its internal cells to
its multiplicative gates can learn the fine distinction between sequences
of spikes separated by either 50 or 49 discrete time steps, without the
help of any short training exemplars. Without external resets or teacher
forcing or loss of performance on tasks reported earlier, our LSTM variant
also learns to generate very stable sequences of highly nonlinear, precisely
timed spikes. This makes LSTM a promising approach for real-world tasks that
require to time and count
^
@ftp://ftp.idsia.ch/pub/juergen/TimeCount-IJCNN2000.pdf
#topic:coq
#topic:cryptography
#author:Andres Erbsen
#author:Jade Philipoom
#author:Jason Gross
#author:Robert Sloan
#author:Adam Chlipala
#language:english
#medium:paper
Simple High-Level Code For Cryptographic Arithmetic – With Proofs, Without Compromises
We introduce a new approach for implementing cryptographic arithmetic
in short high-level code with machinechecked proofs of functional
correctness. We further demonstrate that simple partial evaluation is
sufficient to transform such initial code into the fastest-known C code,
breaking the decadesold pattern that the only fast implementations are those
whose instruction-level steps were written out by hand.  These techniques
were used to build an elliptic-curve library that achieves competitive
performance for 80 prime fields and multiple CPU architectures, showing
that implementation and proof effort scales with the number and complexity
of conceptually different algorithms, not their use cases. As one outcome,
we present the first verified high-performance implementation of P-256,
the most widely used elliptic curve. Implementations from our library were
included in BoringSSL to replace existing specialized code, for inclusion
in several large deployments for Chrome, Android, and CloudFlare.
^
@http://adam.chlipala.net/papers/FiatCryptoSP19/FiatCryptoSP19.pdf
#topic:interval arithmetic
#author:T. Hickey, Q. Ju
#author:M.H. van Emden
#language:english
#medium:paper
Interval Arithmetic: from Principles to Implementation
We start with a mathematical definition of a real interval as a closed,
connected set of reals. Interval arithmetic operations (addition, subtraction,
multiplication and division) are likewise defined mathematically and we provide
algorithms for computing these operations assuming exact real arithmetic. Next,
we define interval arithmetic operations on intervals with IEEE 754 floating
point endpoints to be sound and optimal approximations of the real interval
operations and we show that the IEEE standard’s specification of operations
involving the signed infinities, signed zeros, and the exact/inexact flag are
such as to make a correct and optimal implementation more efficient. From
the resulting theorems we derive data that are sufficiently detailed to
convert directly to a program for efficiently implementing the interval
operations. Finally we extend these results to the case of general intervals,
which are defined as connected sets of reals that are not necessarily closed.
^
@https://fab.cba.mit.edu/classes/S62.12/docs/Hickey_interval.pdf
#topic:neural network
#author:Vincent Dumoulin
#author:Francesco Visin
#language:english
#medium:paper
A guide to convolution arithmetic for deep learning

^
@https://arxiv.org/pdf/1603.07285.pdf
#topic:neural network
#author:David A. Medler
#author:Michael R. W. Dawson
#language:english
#medium:paper
Using Redundancy to Improve the Performance of Artificial Neural Networks
For Artificial Neural Networks (ANNs) to be effective modelling tools, they
must draw upon biological characteristics: One characteristic often overlooked
in the design of ANNs is the replication, or redundancy, of processes within
the brain. This paper examines the effects of redundancy on the performance of
ANNs trained on either a pattern classification task (e.g. parity, encoder)
or a function approximation task (e.g. forward kinematics). Results suggest
that there is an optimal level of redundancy that increases the likelihood
of network convergence while decreasing overall network processing time. ANNs
with this level of redundancy consistently perform better than standard ANNs
on pattern classification tasks.  Furthermore, redundant ANNs trained on the
function approximation task are more accurate in terms of overall system error
than standard ANNs. These results imply that redundancy may be effectively
used to increase the performance of ANNs, both in accuracy and speed.
^
@https://web.uvic.ca/~dmedler/files/ai94.pdf
#topic:data structure
#author:Charles Crowley
#language:english
#medium:paper
Data Structures for Text Sequences
The data structure used ot maintain the sequence of characters is an
important part of a text editor. This paper investigates and evaluates the
range of possible data structures for text sequences. The ADT interface
to the text sequence component of a text editor is examined.  Six common
sequence data structures (array, gap, list, line pointers, xed size bu
ers and piece tables) are examined and then a general model of sequence
data structures that encompasses all six structures is presented. The piece
table method is explained in detail and its advantages are presented. The
design space of sequence data structures is examined and several variations
on the ones listed above are presented. These sequence data structures are
compared experimentally and evaluated based on a number of criteria. The
experimental comparison is done by implementing each data structure in an
editing simulator and testing it using a synthetic load of many thousands
of edits. We also report on experiments on the senstivity of the results to
variations in the parameters used to generate the synthetic editing load.
^
@https://www.cs.unm.edu/~crowley/papers/sds.pdf
#topic:neural network
#topic:reinforcement learning
#author:Pieter Abbeel
#author:Adam Coates
#author:Morgan Quigley
#author:Andrew Y. Ng
#language:english
#medium:paper
An Application of Reinforcement Learning to Aerobatic Helicopter Flight
Autonomous helicopter flight is widely regarded to be a highly challenging
control problem. This paper presents the first successful autonomous completion
on a real RC helicopter of the following four aerobatic maneuvers: forward
flip and sideways roll at low speed, tail-in funnel, and nose-in funnel. Our
experimental results significantly extend the state of the art in autonomous
helicopter flight.  We used the following approach: First we had a pilot
fly the helicopter to help us find a helicopter dynamics model and a reward
(cost) function. Then we used a reinforcement learning (optimal control)
algorithm to find a controller that is optimized for the resulting model and
reward function. More specifically, we used differential dynamic programming
(DDP), an extension of the linear quadratic regulator (LQR).
^
@https://papers.nips.cc/paper/3151-an-application-of-reinforcement-learning-to-aerobatic-helicopter-flight.pdf
#topic:neural network
#author:Zelda Mariet
#author:Suvrit Sra
#language:english
#medium:paper
Diversity Networks: Neural Network Compression Using Determinantal Point Processes
We introduce Divnet, a flexible technique for learning networks with diverse
neurons. Divnet models neuronal diversity by placing a Determinantal Point
Process (DPP) over neurons in a given layer. It uses this DPP to select a
subset of diverse neurons and subsequently fuses the redundant neurons into
the selected ones. Compared with previous approaches, Divnet offers a more
principled, flexible technique for capturing neuronal diversity and thus
implicitly enforcing regularization. This enables effective auto-tuning of
network architecture and leads to smaller network sizes without hurting
performance. Moreover, through its focus on diversity and neuron fusing,
Divnet remains compatible with other procedures that seek to reduce memory
footprints of networks. We present experimental results to corroborate our
claims: for pruning neural networks, Divnet is seen to be notably superior
to competing approaches.
^
@https://arxiv.org/pdf/1511.05077.pdf
#topic:neural network
#topic:reinforcement learning
#author:Andrew Y. Ng
#author:Adam Coates
#author:Mark Diel
#author:Varun Ganapathi
#author:Jamie Schulte
#author:Ben Tse
#author:Eric Berger
#author:Eric Liang
#language:english
#medium:paper
Autonomous inverted helicopter flight via reinforcement learning
Helicopters have highly stochastic, nonlinear, dynamics, and autonomous
helicopter flight is widely regarded to be a challenging control problem. As
helicopters are highly unstable at low speeds, it is particularly
difficult to design controllers for low speed aerobatic maneuvers. In
this paper, we describe a successful application of reinforcement learning
to designing a controller for sustained inverted flight on an autonomous
helicopter. Using data collected from the helicopter in flight, we began by
learning a stochastic, nonlinear model of the helicopter’s dynamics. Then,
a reinforcement learning algorithm was applied to automatically learn a
controller for autonomous inverted hovering. Finally, the resulting controller
was successfully tested on our autonomous helicopter platform.
^
@http://heli.stanford.edu/papers/iser04-invertedflight.pdf
#topic:reinforcement learning
#topic:neural network
#author:Andrew Y. Ng
#author:H. Jin Kim
#author:Michael I. Jordan
#author:Shankar Sastry
#language:english
#medium:paper
Autonomous helicopter flight via reinforcement learning
Autonomous helicopter flight represents a challenging control problem, with
complex, noisy, dynamics. In this paper, we describe a successful application
of reinforcement learning to autonomous helicopter flight.  We first fit
a stochastic, nonlinear model of the helicopter dynamics. We then use the
model to learn to hover in place, and to fly a number of maneuvers taken
from an RC helicopter competition
^
@https://people.eecs.berkeley.edu/~jordan/papers/ng-etal03.pdf
#topic:fuse
#topic:file system
#topic:file system in userspace
#author:Aditya Rajgarhia
#author:Ashish Gehani
#language:english
#medium:paper
Performance and Extension of User Space File Systems
Several efforts have been made over the years for developing file systems in
user space. Many of these efforts have failed to make a significant impact
as measured by their use in production systems. Recently, however, user space
file systems have seen a strong resurgence. FUSE is a popular framework that
allows file systems to be developed in user space while offering ease of use
and flexibility.  In this paper, we discuss the evolution of user space file
systems with an emphasis on FUSE, and measure its performance using a variety
of test cases. We also discuss the feasibility of developing file systems in
high-level programming languages, by using as an example Java bindings for
FUSE that we have developed. Our benchmarks show that FUSE offers adequate
performance for several kinds of workloads
^
@http://www.csl.sri.com/users/gehani/papers/SAC-2010.FUSE.pdf
#topic:concurrency
#author:Matthew Might
#author:David Van Horn
#language:english
#medium:paper
A family of abstract interpretations for static analysis of concurrent higher-order programs
We develop a framework for computing two foundational analyses for concurrent
higher-order programs: (control-)flow analysis (CFA) and may-happen-in-parallel
analysis (MHP). We pay special attention to the unique challenges posed by the
unrestricted mixture of first-class continuations and dynamically spawned
threads. To set the stage, we formulate a concrete model of concurrent
higher-order programs: the P(CEK*)S machine. We find that the systematic
abstract interpretation of this machine is capable of computing both flow
and MHP analyses. Yet, a closer examination finds that the precision for
MHP is poor. As a remedy, we adapt a shape analytic technique—singleton
abstraction—to dynamically spawned threads (as opposed to objects in
the heap). We then show that if MHP analysis is not of interest, we can
substantially accelerate the computation of flow analysis alone by collapsing
thread interleavings with a second layer of abstraction.
^
@https://www.ccs.neu.edu/home/dvanhorn/pubs/might-vanhorn-sas11.pdf
#topic:type theory
#author:Xavier Leroy
#language:english
#medium:paper
Polymorphic typing of an algorithmic language
The polymorphic type discipline, as in the ML language, fits well within purely
applicative languages, but does not extend naturally to the main feature of
algorithmic languages: in-place update of data structures. Similar typing
diculties arise with other extensions of applicative languages: logical
variables, communication channels, continuation handling. This work studies
(in the setting of relational semantics) two new approaches to the polymorphic
typing of these non-applicative features. The first one relies on a restriction
of generalization over types (the notion of dangerous variables), and on
a rened typing of functional values (closure typing). The resulting type
system is compatible with the ML core language, and is the most expressive
type systems for ML with imperative features proposed so far. The second
approach relies on switching to \by-name" semantics for the constructs
of polymorphism, instead of the usual \by-value" semantics. The resulting
language diers from ML, but lends itself easily to polymorphic typing. Both
approaches smoothly integrate non-applicative features and polymorphic typing.
^
@https://xavierleroy.org/publi/phd-thesis.pdf
#topic:markov chains
#author:Peter Buhlmann
#author:Abraham J. Wyner
#language:english
#medium:paper
Variable Length Markov Chains
We study estimation in the class of stationary variable length Markov
chains VLMC on a finite space Ž . . The processes in this class are still
Markovian of high order, but with memory of variable length yielding a much
bigger and structurally richer class of models than ordinary highorder Markov
chains. From an algorithmic view, the VLMC model class has attracted interest
in information theory and machine learning, but statistical properties have not
yet been explored. Provided that good estimation is available, the additional
structural richness of the model class enhances predictive power by finding a
better trade-off between model bias and variance and allowing better structural
description which can be of specific interest. The latter is exemplified with
some DNA data.  A version of the tree-structured context algorithm, proposed
by Rissanen in an information theoretical set-up is shown to have new good
asymptotic properties for estimation in the class of VLMCs. This remains
true even when the underlying model increases in dimensionality. Furthermore,
consistent estimation of minimal state spaces and mixing properties of fitted
models are given.  We also propose a new bootstrap scheme based on fitted
VLMCs. We show its validity for quite general stationary categorical time
series and for a broad range of statistical procedures.
^
@https://www.stat.berkeley.edu/~binyu/212A/papers/vlmc.pdf
#topic:type theory
#language:english
#medium:notes
Row polymorphism

^
@https://www.cl.cam.ac.uk/teaching/1415/L28/rows.pdf
#topic:prime numbers
#author:Chris K. Caldwell
#author:Angela Reddick
#author:Yeng Xiong
#language:english
#medium:paper
The History of the Primality of One: A Selection of Sources
The way mathematicians have viewed the number one (unity, the monad) has
changed throughout the years. Most of the early Greeks did not view one as a
number, but rather as the origin, or generator, of number. Around the time
of Simon Stevin (1548–1620), one (and zero) were first widely viewed as
numbers. This created a period of confusion about whether or not the number
one was prime. In this dynamic survey, we collect a cornucopia of sources
which deal directly with the question “what is the smallest prime?” The
goal is to create a source book for studying the history of the definition
of prime, especially as applied to the number one.
^
@https://cs.uwaterloo.ca/journals/JIS/VOL15/Caldwell2/cald6.pdf
#topic:distributed systems
#topic:ponylang
#author:Sebastian Blessing
#language:english
#medium:paper
A String of Ponies - Transparent Distributed Programming with Actors
We develop an extension to a concurrent, actor-based language runtime
called Pony with the ability of transparent distributed programming, whereby
programmers do not need to be aware of the underlying distributed system. Thus,
any Pony application can be executed in a concurrent setting as well as
in a distributed setting without any changes to the code being necessary.
A distributed cluster of Ponies, managed based on a tree network topology,
is easy to maintain and can be extended with slave nodes at runtime without
any reconfiguration being necessary. We propose a joining algorithm which
guarantees that the underlying tree topology is almost balanced at any point
in time.  Distribution is reflected through actor mobility. We develop
a hierarchical work stealing algorithm with constant space complexity,
specifically tailored for tree network topologies. Work stealing is provably
optimal for task and data parallelism. Furthermore, the implementation of the
proposed distributed work stealing algorithm is itself based on the actor
programming model, which allowed us to extend Pony without sacrificing the
performance of single-node configurations.  Causal message delivery is a
valuable property for message-passing systems, contributing to efficiency
and improved reasonability. Pony guarantees causality for both the concurrent
and distributed setting without any additional software overhead.  A property
unique to Pony is fully concurrent garbage collection of actors. We present
an extended algorithm for concurrent garbage collection (including cycle
detection) in distributed actor-based applications. Concurrent Pony programs
are terminated based on quiescence. In order to retain that property in
a distributed context, we propose a protocol for detecting quiescence in
distributed actor systems. Both schemes strongly depend on causal message
delivery.  We evaluate our implementation based on a micro benchmark that
allows us to simulate different application characteristics. Pony achieves
considerable speed-up for computation-bound scenarios.
^
@https://www.ponylang.io/media/papers/a_string_of_ponies.pdf
#topic:coq
#author:Robbert Krebbers
#author:Ralf Jung
#author:Aleˇs Bizjak
#author:Jacques-Henri Jourdan
#author:Derek Dreyer
#author:Lars Birkedal
#language:english
#medium:paper
The Essence of Higher-Order Concurrent Separation Logic
Concurrent separation logics (CSLs) have come of age, and with age
they have accumulated a great deal of complexity. Previous work on the
Iris logic attempted to reduce the complex logical mechanisms of modern
CSLs to two orthogonal concepts: partial commutative monoids (PCMs) and
invariants. However, the realization of these concepts in Iris still bakes in
several complex mechanisms—such as weakest preconditions and mask-changing
view shifts—as primitive notions.  In this paper, we take the Iris story to
its (so to speak) logical conclusion, applying the reductionist methodology
of Iris to Iris itself. Specifically, we define a small, resourceful base
logic, which distills the essence of Iris: it comprises only the assertion
layer of vanilla separation logic, plus a handful of simple modalities. We
then show how the much fancier logical mechanisms of Iris—in particular,
its entire program specification layer—can be understood as merely derived
forms in our base logic. This approach helps to explain the meaning of
Iris’s program specifications at a much higher level of abstraction than
was previously possible. We also show that the step-indexed “later”
modality of Iris is an essential source of complexity, in that removing it
leads to a logical inconsistency.  All our results are fully formalized in
the Coq proof assistant.
^
@https://iris-project.org/pdfs/2017-esop-iris3-final.pdf
#topic:process calculi
#topic:concurrency theory
#author:Jorge A. P´erez P.
#language:english
#medium:paper
Higher-Order Concurrency: Expressiveness and Decidability Results
Higher-order process calculi are formalisms for concurrency in which processes
can be passed around in communications. Higher-order (or process-passing)
concurrency is often presented as an alternative paradigm to the first order
(or name-passing) concurrency of the π-calculus for the description of mobile
systems. These calculi are inspired by, and formally close to, the λ-calculus,
whose basic computational step β-reduction involves term instantiation.
The theory of higher-order process calculi is more complex than that of
first-order process calculi. This shows up in, for instance, the definition
of behavioral equivalences. A longstanding approach to overcome this burden
is to define encodings of higher-order processes into a first-order setting,
so as to transfer the theory of the first-order paradigm to the higherorder
one. While satisfactory in the case of calculi with basic (higher-order)
primitives, this indirect approach falls short in the case of higher-order
process calculi featuring constructs for phenomena such as, e.g., localities
and dynamic system reconfiguration, which are frequent in modern distributed
systems. Indeed, for higher-order process calculi involving little more than
traditional process communication, encodings into some first-order language
are difficult to handle or do not exist. We then observe that foundational
studies for higher-order process calculi must be carried out directly on
them and exploit their peculiarities.  This dissertation contributes to
such foundational studies for higher-order process calculi.  We concentrate
on two closely interwoven issues in process calculi: expressiveness and
decidability. Surprisingly, these issues have been little explored in the
higher-order setting. Our research is centered around a core calculus for
higher-order concurrency in which only the operators strictly necessary to
obtain higher-order communication are retained. We develop the basic theory
of this core calculus and rely on it to study the expressive power of issues
universally accepted as basic in process calculi, namely synchrony, forwarding,
and polyadic communication.
^
@https://core.ac.uk/download/pdf/11012451.pdf
#topic:markov chains
#author:Hengrun Zhang
#author:Kai Zeng
#language:english
#medium:paper
Pairwise Markov Chain: A Task Scheduling Strategy for Privacy-Preserving SIFT on Edge
In this paper, we propose a task scheduling strategy, which can achieve
image feature extraction on edge while ensuring privacy. Our task scheduling
strategy applies to a fairly popular privacy-preserving Scale-Invariant
Feature Transform (SIFT) scheme, where images to be processed are firstly
randomly split into two portions for encryption and transmitted to two
different edge nodes for feature extraction. Then, in the edge, our task
scheduling strategy will re-assign these two portions to proper edge nodes
for processing. During the whole process, two portions of the same image
should not be assigned to the same edge node in order to preserve privacy. We
show that this privacy constraint can be enforced through constructing a
pairwise Markov chain, and carefully designing system states and transition
probabilities. We further formulate the whole task scheduling problem as a
stochastic latency minimization problem and solve it by converting it into a
linear programming problem.  Simulation results show that our proposed task
scheduling strategy can achieve lower latency than baseline strategies while
satisfying the privacy constraint.
^
@mason.gmu.edu/~hzhang18/publications/Conf_Paper_2.pdf
#topic:neural network
#author:G. E. Hinton
#author:T. J. Sejnowski
#language:english
#medium:book
Learning and Relearning in Boltzmann Machines

^
@http://www.cs.toronto.edu/~hinton/absps/pdp7.pdf
#topic:protocol
#author:Kee Jefferys
#author:Maxim Shishmarev
#author:Simon Harman
#language:english
#medium:paper
Session: A Model for End-To-End Encrypted Conversations With Minimal Metadata Leakage
Session is an open-source, public-key-based secure messaging application
which uses a set of decentralised storage servers and an onion routing
protocol to send end-to-end encrypted messages with minimal exposure of user
metadata. It does this while also providing common features of mainstream
messaging applications.
^
@https://getsession.org/wp-content/uploads/2020/02/Session-Whitepaper.pdf
#topic:markov chains
#author:Yee Whye Teh
#language:english
#medium:presentation
Markov Chains and Markov Chain Monte Carlo

^
@https://www.stats.ox.ac.uk/~teh/teaching/dtc2014/Markov4.pdf
#topic:quantum computing
#topic:security
#author:Daniel Harlow
#author:Patrick Hayden
#language:english
#medium:paper
Quantum Computation vs. Firewalls
In this paper we discuss quantum computational restrictions on the types
of thought experiments recently used by Almheiri, Marolf, Polchinski, and
Sully to argue against the smoothness of black hole horizons. We argue that
the quantum computations required to do these experiments would take a time
which is exponential in the entropy of the black hole under study, and we
show that for a wide variety of black holes this prevents the experiments
from being done. We interpret our results as motivating a broader type of
nonlocality than is usually considered in the context of black hole thought
experiments, and claim that once this type of nonlocality is allowed there
may be no need for firewalls. Our results do not threaten the unitarity of
of black hole evaporation or the ability of advanced civilizations to test it.
^
@https://arxiv.org/pdf/1301.4504v4.pdf
#topic:computational complexity
#author:Leonard Susskind
#language:english
#medium:paper
Computational Complexity and Black Hole Horizons
Computational complexity is essential to understanding the properties of black
hole horizons. The problem of Alice creating a firewall behind the horizon
of Bob’s black hole is a problem of computational complexity. In general we
find that while creating firewalls is possible, it is extremely difficult and
probably impossible for black holes that form in sudden collapse, and then
evaporate. On the other hand if the radiation is bottled up then after an
exponentially long period of time firewalls may be common.  It is possible
that gravity will provide tools to study problems of complexity; especially
the range of complexity between scrambling and exponential complexity.
^
@https://arxiv.org/pdf/1402.5674.pdf
#topic:cryptography
#author:Marc Kaplan
#author:Ga¨etan Leurent
#author:Anthony Leverrier
#author:Mar´ıa Naya-Plasencia
#language:english
#medium:paper
Breaking Symmetric Cryptosystems using Quantum Period Finding
Due to Shor’s algorithm, quantum computers are a severe threat for
public key cryptography. This motivated the cryptographic community to
search for quantum-safe solutions. On the other hand, the impact of quantum
computing on secret key cryptography is much less understood. In this paper,
we consider attacks where an adversary can query an oracle implementing a
cryptographic primitive in a quantum superposition of different states. This
model gives a lot of power to the adversary, but recent results show that
it is nonetheless possible to build secure cryptosystems in it.  We study
applications of a quantum procedure called Simon’s algorithm (the simplest
quantum period finding algorithm) in order to attack symmetric cryptosystems
in this model. Following previous works in this direction, we show that
several classical attacks based on finding collisions can be dramatically
sped up using Simon’s algorithm: finding a collision requires Ω(2n/2 )
queries in the classical setting, but when collisions happen with some hidden
periodicity, they can be found with only O(n) queries in the quantum model.
We obtain attacks with very strong implications. First, we show that the most
widely used modes of operation for authentication and authenticated encryption
(e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security
model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ,
COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the
situation with encryption modes: Anand et al. show that standard modes are
secure with a quantum-secure PRF.  Second, we show that Simon’s algorithm
can also be applied to slide attacks, leading to an exponential speed-up of
a classical symmetric cryptanalysis technique in the quantum model.
^
@https://arxiv.org/pdf/1602.05973.pdf
#topic:security
#author:Saad Islam
#author:Ahmad Moghimi
#author:Ida Bruhns
#author:Moritz Krebbel
#author:Berk Gulmezoglu
#author:Thomas Eisenbarth
#author:Berk Sunar
#language:english
#medium:paper
SPOILER: Speculative Load Hazards Boost Rowhammer and Cache Attacks
Modern microarchitectures incorporate optimization techniques such as
speculative loads and store forwarding to improve the memory bottleneck. The
processor executes the load speculatively before the stores, and forwards the
data of a preceding store to the load if there is a potential dependency. This
enhances performance since the load does not have to wait for preceding
stores to complete. However, the dependency prediction relies on partial
address information, which may lead to false dependencies and stall hazards.
In this work, we are the first to show that the dependency resolution logic
that serves the speculative load can be exploited to gain information about
the physical page mappings.  Microarchitectural side-channel attacks such as
Rowhammer and cache attacks like Prime+Probe rely on the reverse engineering
of the virtual-to-physical address mapping. We propose the SPOILER attack
which exploits this leakage to speed up this reverse engineering by a factor
of 256. Then, we show how this can improve the Prime+Probe attack by a 4096
factor speed up of the eviction set search, even from sandboxed environments
like JavaScript. Finally, we improve the Rowhammer attack by showing how
SPOILER helps to conduct DRAM row conflicts deterministically with up to
100% chance, and by demonstrating a double-sided Rowhammer attack with
normal user’s privilege. The later is due to the possibility of detecting
contiguous memory pages using the SPOILER leakage.
^
@https://arxiv.org/pdf/1903.00446.pdf
#topic:constraint solving
#author:Noreen Jamil
#language:english
#medium:paper
Constraint Solvers for User Interface Layout
Constraints have played an important role in the construction of GUIs , where
they are mainly used to define the layout of the widgets. Resizing behavior is
very important in GUIs because areas have domain specific parameters such as
form the resizing of windows. If linear objective function is used and window
is resized then error is not distributed equally. To distribute the error
equally, a quadratic objective function is introduced. Different algorithms
are widely used for solving linear constraints and quadratic problems in
a variety of different scientific areas. The linear relxation, Kaczmarz,
direct and linear programming methods are common methods for solving linear
constraints for GUI layout. The interior point and active set methods are
most commonly used techniques to solve quadratic programming problems. Current
constraint solvers designed for GUI layout do not use interior point methods
for solving a quadratic objective function subject to linear equality and
inequality constraints. In this paper, performance aspects and the convergence
speed of interior point and active set methods are compared along with one
most commonly used linear programming method when they are implemented for
graphical user interface layout. The performance and convergence of the
proposed algorithms are evaluated empirically using randomly generated UI
layout specifications of various sizes. The results show that the interior
point algorithms perform significantly better than the Simplex method and
QOCA-solver, which uses the active set method implementation for solving
quadratic optimization.
^
@https://arxiv.org/pdf/1401.1031.pdf
#topic:literate programming
#author:Don Knuth
#author:Doug McIlroy
#language:english
#medium:paper
programming pearls - A Literate Program

^
@https://www.cs.tufts.edu/~nr/cs257/archive/don-knuth/pearls-2.pdf
#topic:finger tree
#author:Ralf Hinze
#author:Ross Paterson
#language:english
#medium:paper
Finger trees: a simple general-purpose data structure
We introduce 2-3 finger trees, a functional representation of persistent
sequences supporting access to the ends in amortized constant time, and
concatenation and splitting in time logarithmic in the size of the smaller
piece. Representations achieving these bounds have appeared previously, but
2-3 finger trees are much simpler, as are the operations on them.  Further,
by defining the split operation in a general form, we obtain a general purpose
data structure that can serve as a sequence, priority queue, search tree,
priority search queue and more.
^
@http://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf
#topic:security
#author:Robert J. Colvin
#author:Kirsten Winter
#language:english
#medium:paper
An abstract semantics of speculative execution for reasoning about security vulnerabilities
Reasoning about correctness and security of software is increasingly
difficult due to the complexity of modern microarchitectural features
such as out-of-order execution. A class of security vulnerabilities termed
Spectre that exploits side effects of speculative, out-of-order execution
was announced in 2018 and has since drawn much attention.  In this paper we
formalise speculative execution and its side effects with the intention of
allowing speculation to be reasoned about abstractly at the program level,
limiting the exposure to processor-specific or lowlevel semantics. To this
end we encode and expose speculative execution explicitly in the programming
language, rather than solely in the operational semantics; as a result the
effects of speculative execution are captured by redefining the meaning of a
conditional statement, and introducing novel language constructs that model
transient execution of an alternative branch. We add an abstract cache to
the global state of the system, and derive some general refinement rules that
expose cache side effects due to speculative loads. Underlying this extension
is a semantic model that is based on instruction-level parallelism. The
rules are encoded in a simulation tool, which we use to analyse an abstract
specification of a Spectre attack and vulnerable code fragments.
^
@https://arxiv.org/pdf/2004.00577.pdf
#topic:smart contracts
#topic:security
#author:Michael Coblenz
#author:Jonathan Aldrich
#author:Joshua Sunshine
#author:Brad A. Myers
#language:english
#medium:paper
An Empirical Study of Ownership, Typestate, and Assets in the Obsidian Smart Contract Language
Some blockchain programs (smart contracts) have included serious security
vulnerabilities. Obsidian is a new typestate-oriented programming language that
uses a strong type system to rule out some of these vulnerabilities. Although
Obsidian was designed to promote usability to make it as easy as possible
to write programs, strong type systems can cause a language to be difficult
to use. In particular, ownership, typestate, and assets, which Obsidian
uses to provide safety guarantees, have not seen broad adoption in popular
languages and result in significant usability challenges. We performed an
empirical study with 20 participants comparing Obsidian to Solidity, which
is the language most commonly used for writing smart contracts today. We
observed that most of the Obsidian participants were able to successfully
complete most of the programming tasks we gave them. We also found that
asset-related bugs, which Obsidian detects at compile time, were commonly
accidentally inserted by the Solidity participants. We identified potential
opportunities to improve the usability of typestate as well as to apply the
usability benefits of Obsidian’s ownership system to other languages
^
@https://arxiv.org/pdf/2003.12209.pdf
#topic:ray tracing
#topic:graphics
#topic:parallel computation
#topic:gpu
#author:Morgan McGuire
#author:Michael Mara
#author:Williams College
#language:english
#medium:paper
Efficient GPU Screen-Space Ray Tracing
We present an efficient GPU solution for screen-space 3D ray tracing against
a depth buffer by adapting the perspective-correct DDA line rasterization
algorithm. Compared to linear ray marching, this ensures sampling at a
contiguous set of pixels and no oversampling. This paper provides for the first
time full implementation details of a method that has been proven in production
of recent major game titles. After explaining the optimizations, we then
extend the method to support multiple depth layers for robustness. We include
GLSL code and examples of pixel-shader ray tracing for several applications.
^
@http://jcgt.org/published/0003/04/04/paper.pdf
#topic:philosophy
#author:Scott Aaronson
#language:english
#medium:paper
The Ghost in the Quantum Turing Machine
In honor of Alan Turing’s hundredth birthday, I unwisely set out some
thoughts about one of Turing’s obsessions throughout his life, the question
of physics and free will. I focus relatively narrowly on a notion that
I call “Knightian freedom”: a certain kind of in-principle physical
unpredictability that goes beyond probabilistic unpredictability. Other,
more metaphysical aspects of free will I regard as possibly outside the
scope of science.  I examine a viewpoint, suggested independently by Carl
Hoefer, Cristi Stoica, and even Turing himself, that tries to find scope for
“freedom” in the universe’s boundary conditions rather than in the
dynamical laws. Taking this viewpoint seriously leads to many interesting
conceptual problems. I investigate how far one can go toward solving those
problems, and along the way, encounter (among other things) the No-Cloning
Theorem, the measurement problem, decoherence, chaos, the arrow of time, the
holographic principle, Newcomb’s paradox, Boltzmann brains, algorithmic
information theory, and the Common Prior Assumption. I also compare the
viewpoint explored here to the more radical speculations of Roger Penrose.
The result of all this is an unusual perspective on time, quantum mechanics,
and causation, of which I myself remain skeptical, but which has several
appealing features. Among other things, it suggests interesting empirical
questions in neuroscience, physics, and cosmology; and takes a millennia-old
philosophical debate into some underexplored territory
^
@https://www.scottaaronson.com/papers/giqtm3.pdf
#topic:philosophy
#author:Nick Bostrom
#language:english
#medium:paper
The Superintelligent Will: Motivation And Instrumental Rationality In Advanced Artificial Agents
This paper discusses the relation between intelligence and motivation in
artificial agents, developing and briefly arguing for two theses. The first,
the orthogonality thesis, holds (with some caveats) that intelligence and
final goals (purposes) are orthogonal axes along which possible artificial
intellects can freely vary—more or less any level of intelligence could
be combined with more or less any final goal. The second, the instrumental
convergence thesis, holds that as long as they possess a sufficient level of
intelligence, agents having any of a wide range of final goals will pursue
similar intermediary goals because they have instrumental reasons to do
so. In combination, the two theses help us understand the possible range
of behavior of superintelligent agents, and they point to some potential
dangers in building such an agent.
^
@https://www.nickbostrom.com/superintelligentwill.pdf
#topic:graphics
#topic:diagrams
#topic:latex
#author:Hauke Stieler
#language:english
#medium:paper
Tikz for state-machines
You’ll find a short explanation on how to draw state-machines with Tikz
. Because I’m not a professional, please send ideas, mistakes, notes and
suggestions to my e–mail–adress mail@hauke-stieler.de.  Generally this
is a collection2 of examples for different state-machines and -models,
which are dealt with in the summer-semester 2015 in the FGI I lecture.
^
@https://hauke-stieler.de/public/tikz-for-state-machines_en.pdf
#topic:parsing
#author:Chang Ge
#author:Yinan Li
#author:Eric Eilebrecht
#author:Badrish Chandramouli
#author:Donald Kossmann
#language:english
#medium:paper
Speculative Distributed CSV Data Parsing for Big Data Analytics
There has been a recent flurry of interest in providing query capability on
raw data in today’s big data systems. These raw data must be parsed before
processing or use in analytics.  Thus, a fundamental challenge in distributed
big data systems is that of efficient parallel parsing of raw data. The
difficulties come from the inherent ambiguity while independently parsing
chunks of raw data without knowing the context of these chunks. Specifically,
it can be difficult to find the beginnings and ends of fields and records
in these chunks of raw data. To parallelize parsing, this paper proposes a
speculation-based approach for the CSV format, arguably the most commonly
used raw data format. Due to the syntactic and statistical properties of the
format, speculative parsing rarely fails and therefore parsing is efficiently
parallelized in a distributed setting. Our speculative approach is also
robust, meaning that it can reliably detect syntax errors in CSV data. We
experimentally evaluate the speculative, distributed parsing approach in
Apache Spark using more than 11,000 real-world datasets, and show that our
parser produces significant performance benefits over existing methods.
^
@https://www.microsoft.com/en-us/research/uploads/prod/2019/04/chunker-sigmod19.pdf
#topic:finite state machine
#author:Gerald Tripp
#language:english
#medium:paper
A parallel ‘String Matching Engine’ for use in high speed network intrusion detection systems.
This paper describes a finite state machine approach to string matching for
an intrusion detection system. To obtain high performance, we typically need
to be able to operate on input data that is several bytes wide. However,
finite state machine designs become more complex when operating on large
input data words, partly because of needing to match the starts and ends
of a string that may occur part way through an input data word.  Here we
use finite state machines that each operate on only a single byte wide data
input. We then provide a separate finite state machine for each byte wide
data path from a multi-byte wide input data word. By splitting the search
strings into multiple interleaved substrings and by combining the outputs
from the individual finite state machines in an appropriate way we can
perform string matching in parallel across multiple finite state machines.
A hardware design for a parallel string matching engine has been generated,
built for implementation in a Xilinx Field Programmable Gate Array and tested
by simulation. The design is capable of operating at a search rate of 4.7
Gbps with a 32-bit input word size
^
@https://www.cs.kent.ac.uk/people/staff/gewt/Tripp-JinCV06.pdf
#topic:parallel
#topic:gpu
#author:Cameron Alexander Fish
#language:english
#medium:paper
A GPU approach to the Abelian sandpile model
The Abelian sandpile model provides examples of groups with highly
“non-trivial” identity elements. These elements are, at least in the
case of sandpile groups on grid graphs, visually stunning. An appreciation
of these visuals can be more than an aesthetic one, as they also serve to
guide intuition and suggest further routes of study. However, these elements
are in general difficult to compute, especially when the underlying graph
becomes large. We make use of GPU computation to develop a new framework for
the simulation and display of sandpiles, as well as suggest several methods
for more efficient calculation of the identity sandpile on grid graphs.
^
@http://people.reed.edu/~davidp/homepage/students/fish.pdf
#topic:multithread
#topic:allocator
#author:Emery D. Berger
#author:Kathryn S. McKinley
#author:Robert D. Blumofe
#author:Paul R. Wilson
#language:english
#medium:paper
Hoard: A Scalable Memory Allocator for Multithreaded Applications
Parallel, multithreaded C and C++ programs such as web servers, database
managers, news servers, and scientific applications are becoming increasingly
prevalent. For these applications, the memory allocator is often a bottleneck
that severely limits program performance and scalability on multiprocessor
systems. Previous allocators suffer from problems that include poor
performance and scalability, and heap organizations that introduce false
sharing. Worse, many allocators exhibit a dramatic increase in memory
consumption when confronted with a producer-consumer pattern of object
allocation and freeing. This increase in memory consumption can range from
a factor of P (the number of processors) to unbounded memory consumption.
This paper introduces Hoard, a fast, highly scalable allocator that largely
avoids false sharing and is memory efficient. Hoard is the first allocator
to simultaneously solve the above problems.  Hoard combines one global
heap and per-processor heaps with a novel discipline that provably bounds
memory consumption and has very low synchronization costs in the common
case. Our results on eleven programs demonstrate that Hoard yields low
average fragmentation and improves overall program performance over the
standard Solaris allocator by up to a factor of 60 on 14 processors, and up
to a factor of 18 over the next best allocator we tested.
^
@https://people.cs.umass.edu/~emery/pubs/berger-asplos2000.pdf
#topic:allocator
#topic:multithread
#topic:message passing
#author:Paul Liétar
#author:Theodore Butler
#author:Sylvan Clebsch
#author:Sophia Drossopoulou
#author:Juliana Franco
#author:Matthew J. Parkinson
#author:Alex Shamis
#author:Christoph M. Wintersteiger
#author:David Chisnall
#language:english
#medium:paper
snmalloc: A Message Passing Allocator
Snmalloc is an implementation of malloc aimed at workloads in which objects are
typically deallocated by a different thread than the one that had allocated
them. We use the term producer/consumer for such workloads. Snmalloc uses
a novel message passing scheme which returns deallocated objects to the
originating allocator in batches without taking any locks. It also uses
a novel bump pointer-free list data structure with which just 64-bits of
meta-data are sufficient for each 64 KiB slab. On such producer/consumer
benchmarks our approach performs better than existing allocators
^
@https://github.com/microsoft/snmalloc/raw/master/snmalloc.pdf
#topic:allocator
#author:Daan Leijen
#author:Benjamin Zorn
#author:Leonardo De Moura
#language:english
#medium:paper
Mimalloc: Free List Sharding in Action
Modern memory allocators have to balance many simultaneous demands, including
performance, security, the presence of concurrency, and application-specific
demands depending on the context of their use. One increasing use-case for
allocators is as back-end implementations of languages, such as Swift and
Python, that use reference counting to automatically deallocate objects. We
present mimalloc, a memory allocator that effectively balances these demands,
shows significant performance advantages over existing allocators, and is
tailored to support languages that rely on the memory allocator as a backend
for reference counting.  Mimalloc combines several innovations to achieve
this result. First, it uses three page-local sharded free lists to increase
locality, avoid contention, and support a highly-tuned allocate and free
fast path. These free lists also support temporal cadence, which allows the
allocator to predictably leave the fast path for regular maintenance tasks
such as supporting deferred freeing, handling frees from non-local threads,
etc. While influenced by the allocation workload of the reference-counted Lean
and Koka programming language, we show that mimalloc has superior performance
to modern commercial memory allocators, including tcmalloc and jemalloc, with
speed improvements of 7% and 14%, respectively, on redis, and consistently out
performs over a wide range of sequential and concurrent benchmarks. Allocators
tailored to provide an efficient runtime for reference-counting languages
reduce the implementation burden on developers and encourage the creation
of innovative new language designs.
^
@https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf
#topic:encryption
#topic:cryptography
#topic:lattice2 cryptography
#author:Eric Crockett
#author:Chris Peikert
#language:english
#medium:paper
Λ◦λ : Functional Lattice Cryptography
This work describes the design, implementation, and evaluation of Λ◦λ,
a general-purpose software framework for lattice-based cryptography. The
Λ◦λ framework has several novel properties that distinguish it from
prior implementations of lattice cryptosystems, including the following.
Generality, modularity, concision: Λ◦λ defines a collection of general,
highly composable interfaces for mathematical operations used across lattice
cryptography, allowing for a wide variety of schemes to be expressed very
naturally and at a high level of abstraction. For example, we implement an
advanced fully homomorphic encryption (FHE) scheme in as few as 2–5 lines
of code per feature, via code that very closely matches the scheme’s
mathematical definition.  Theory affinity: Λ◦λ is designed from the
ground-up around the specialized ring representations, fast algorithms,
and worst-case hardness proofs that have been developed for the Ring-LWE
problem and its cryptographic applications. In particular, it implements
fast algorithms for sampling from theoryrecommended error distributions
over arbitrary cyclotomic rings, and provides tools for maintaining tight
control of error growth in cryptographic schemes.  Safety: Λ◦λ has several
facilities for reducing code complexity and programming errors, thereby aiding
the correct implementation of lattice cryptosystems. In particular, it uses
strong typing to statically enforce—i.e., at compile time—a wide variety
of constraints among the various parameters.  Advanced features: Λ◦λ
exposes the rich hierarchy of cyclotomic rings to cryptographic applications.
We use this to give the first-ever implementation of a collection of FHE
operations known as “ring switching,” and also define and analyze a
more efficient variant that we call “ring tunneling.” Lastly, this work
defines and analyzes a variety of mathematical objects and algorithms for
the recommended usage of Ring-LWE in cyclotomic rings, which we believe will
serve as a useful knowledge base for future implementations.
^
@https://eprint.iacr.org/2015/1134.pdf
#topic:cryptography
#topic:hash algorithm
#topic:homomorphic
#author:Maxwell N. Krohn
#author:Michael J. Freedman
#author:David Mazieres
#language:english
#medium:paper
On-the-Fly Verification of Rateless Erasure Codes for Efficient Content Distribution
The quality of peer-to-peer content distribution can suffer when malicious
participants intentionally corrupt content. Some systems using simple
block-by-block downloading can verify blocks with traditional cryptographic
signatures and hashes, but these techniques do not apply well to more elegant
systems that use rateless erasure codes for efficient multicast transfers. This
paper presents a practical scheme, based on homomorphic hashing, that enables
a downloader to perform on-the-fly verification of erasure-encoded blocks.
^
@https://pdos.csail.mit.edu/papers/otfvec/paper.pdf
#topic:erlang
#topic:concurrency
#author:Joe Armstrong
#language:english
#medium:paper
Making reliable distributed systems in the presence of sodware errors
The work described in this thesis is the result of a research program started
in 1981 to find better ways of programming Telecom applications. These
applications are large programs which despite careful testing will probably
contain many errors when the program is put into service. We assume that
such programs do contain errors, and investigate methods for building
reliable systems despite such errors.  The research has resulted in the
development of a new programming language (called Erlang), together with a
design methodology, and set of libraries for building robust systems (called
OTP). At the time of writing the technology described here is used in a number
of major Ericsson, and Nortel products. A number of small companies have also
been formed which exploit the technology.  The central problem addressed by
this thesis is the problem of constructing reliable systems from programs
which may themselves contain errors. Constructing such systems imposes a
number of requirements on any programming language that is to be used for the
construction. I discuss these language requirements, and show how they are
satisfied by Erlang.  Problems can be solved in a programming language, or in
the standard libraries which accompany the language. I argue how certain of
the requirements necessary to build a fault-tolerant system are solved in the
language, and others are solved in the standard libraries. Together these form
a basis for building fault-tolerant sodware systems.  No theory is complete
without proof that the ideas work in practice. To demonstrate that these ideas
work in practice I present a number of case studies of large commercially
successful products which use this technology. At the time of writing the
largest of these projects is a major Ericsson v vi ABSTRACT product, having
over a million lines of Erlang code. This product (the AXD301) is thought
to be one of the most reliable products ever made by Ericsson.  Finally,
I ask if the goal of finding better ways to program Telecom applications was
fulfilled—I also point to areas where I think the system could be improved.
^
@http://erlang.org/download/armstrong_thesis_2003.pdf
#topic:sicp
#topic:lisp
#topic:scheme lisp
#author:Harold Abelson
#author:Gerald Jay Sussman
#author:Julie Sussman
#language:english
#medium:book
Structure and Interpretation of Computer Programs

^
@https://web.mit.edu/alexmv/6.037/sicp.pdf
#topic:ocaml
#topic:minikanren
#topic:type theory
#author:Dmitry Kosarev
#author:Dmitri Boulytchev
#language:english
#medium:paper
Typed Embedding of a Relational Language in OCaml
We present an implementation of the relational programming language miniKanren
as a set of combinators and syntax extension for OCaml. The key feature of our
approach is polymorphic unification, which can be used to unify data structures
of almost arbitrary types. In addition we provide a useful generic programming
pattern to systematically develop relational specifications in a typed manner,
and address the problem of relational and functional code integration.
^
@https://oops.math.spbu.ru/papers/ocanren.pdf
#topic:minikanren
#topic:logic programming
#author:William E. Byrd
#language:english
#medium:paper
Relational Programming in miniKanren: Techniques, Applications, and Implementations

^
@https://github.com/webyrd/dissertation-single-spaced/raw/master/thesis.pdf
#topic:mathematics
#author:Oliver Knill
#language:english
#medium:paper
Some Fundamental Theorems In Mathematics
Criteria for the current list of 172 theorems are whether the result can be
formulated elegantly, whether it is beautiful or useful and whether it could
serve as a guide [6] without leading to panic. The order is not a ranking
but ordered along a time-line when things were written down. Since [350]
stated “a mathematical theorem only becomes beautiful if presented as a
crown jewel within a context” we try sometimes to give some context. Of
course, any such list of theorems is a matter of personal preferences, taste
and limitations. The number of theorems is arbitrary, the initial obvious
goal was 42 but that number got eventually surpassed as it is hard to stop,
once started. As a compensation, there are 42 “tweetable” theorems with
included proofs. More comments on the choice of the theorems is included
in an epilogue.  For literature on general mathematics, see [132, 128, 23,
156, 167, 393, 267, 95], for history [147, 398, 242, 49, 37, 139, 244, 236,
437, 78, 392, 54, 170, 219], for popular, beautiful or elegant things [9,
332, 135, 123, 14, 425, 426, 35, 136, 129, 162, 285, 390, 195, 135, 2, 86,
102, 87, 317]. For comprehensive overviews in large parts of mathematics,
[50, 114, 115, 40, 373] or predictions on developments [38]. For reflections
about mathematics in general [101, 290, 36, 197, 283, 70, 354].  Encyclopedic
source examples are [127, 443, 423, 71, 131, 106, 150, 130, 76, 401].
^
@http://people.math.harvard.edu/~knill/graphgeometry/papers/fundamental.pdf
#topic:sorting
#author:Stefan Edelkamp
#author:Armin Weiß
#author:Sebastian Wild
#language:english
#medium:paper
QuickXsort – A Fast Sorting Scheme in Theory and Practice∗
QuickXsort is a highly efficient in-place sequential sorting scheme that
mixes Hoare’s Quicksort algorithm with X, where X can be chosen from a
wider range of other known sorting algorithms, like Heapsort, Insertionsort
and Mergesort. Its major advantage is that QuickXsort can be in-place even if
X is not. In this work we provide general transfer theorems expressing the
number of comparisons of QuickXsort in terms of the number of comparisons
of X. More specifically, if pivots are chosen as medians of (not too fast)
growing size samples, the average number of comparisons of QuickXsort and X
differ only by o(n)-terms. For median-of-k pivot selection for some constant k,
the difference is a linear term whose coefficient we compute precisely. For
instance, median-of-three QuickMergesort uses at most n lg n − 0.8358n +
O(log n) comparisons.  Furthermore, we examine the possibility of sorting base
cases with some other algorithm using even less comparisons. By doing so the
average-case number of comparisons can be reduced down to n lg n − 1.4112n +
o(n) for a remaining gap of only 0.0315n comparisons to the known lower bound
(while using only O(log n) additional space and O(n log n) time overall).
Implementations of these sorting strategies show that the algorithms challenge
well-established library implementations like Musser’s Introsort.
^
@https://www.wild-inter.net/publications/edelkamp-weiss-wild-2019.pdf
#topic:perfect hash
#author:Antoine Limasset
#author:Guillaume Rizk
#author:Rayan Chikhi
#author:Pierre Peterlongo
#language:english
#medium:paper
Fast and scalable minimal perfect hashing for massive key sets
Minimal perfect hash functions provide space-efficient and collision-free
hashing on static sets.  Existing algorithms and implementations that build
such functions have practical limitations on the number of input elements
they can process, due to high construction time, RAM or external memory
usage. We revisit a simple algorithm and show that it is highly competitive
with the state of the art, especially in terms of construction time and
memory usage. We provide a parallel C++ implementation called BBhash. It
is capable of creating a minimal perfect hash function of 1010 elements in
less than 7 minutes using 8 threads and 5 GB of memory, and the resulting
function uses 3.7 bits/element. To the best of our knowledge, this is also
the first implementation that has been successfully tested on an input of
cardinality 1012. Source code: https://github.com/rizkg/BBHash
^
@https://arxiv.org/pdf/1702.03154.pdf
#topic:type system
#topic:capability system
#topic:ponylang
#author:unknown
#language:english
#medium:paper
Deny Capabilities for Safe, Fast Actors
Combining the actor-model with shared memory for performance is efficient
but can introduce data-races. Existing approaches to static data-race
freedom are based on uniqueness and immutability, but lack flexibility and
high performance implementations. Our approach, based on deny properties,
allows reading, writing and traversing unique references, introduces a new
form of write uniqueness, and guarantees atomic behaviours.
^
@https://www.ponylang.io/media/papers/fast-cheap-with-proof.pdf
#topic:c
#topic:risc
#topic:c++
#author:Robert N. M. Watson
#author:Alexander Richardson
#author:Brooks Davis
#author:John Baldwin
#author:David Chisnall
#author:Jessica Clarke
#author:Nathaniel Filardo
#author:Simon W. Moore
#author:Edward Napierala
#author:Peter Sewell
#author:Peter G. Neumann
#language:english
#medium:paper
CHERI C/C++ Programming Guide
This document is a brief introduction to the CHERI C/C++ programming languages.
We explain the principles underlying these language variants, and their
grounding in CHERI’s multiple architectural instantiations: CHERI-MIPS,
CHERI-RISC-V, and Arm’s Morello. We describe the most commonly encountered
differences between these dialects and C/C++ on conventional architectures,
and where existing software may require minor changes. We document new compiler
warnings and errors that may be experienced compiling code with the CHERI
Clang/LLVM compiler, and suggest how they may be addressed through typically
minor source-code changes. We explain how modest language extensions allow
selected software, such as memory allocators, to further refine permissions
and bounds on pointers. This guidance is based on our experience adapting the
FreeBSD operating-system userspace, and applications such as PostgreSQL and
WebKit, to run in a CHERI C/C++ capability-based programming environment. We
conclude by recommending further reading
^
@https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-947.pdf
#topic:optimization
#author:codasip
#language:english
#medium:paper
Better Benchmarks Through Compiler Optimizations: CODASIP Jump Threading

^
@https://codasip.com/wp-content/uploads/2019/08/Codasip_Jump_Threading.pdf
#topic:mbus
#author:unknown
#language:english
#medium:spec
The M-Bus: A Documentation

^
@https://m-bus.com/assets/downloads/MBDOC48.PDF
#topic:memory management
#topic:lobster
#author:Wouter van Oortmerssen
#language:english
#medium:web article
Memory Management in Lobster
Memory management is an aspect of a language that has one of the biggest
influences on how a language turns out: it affects the type system and the
kinds of types you can have, it affects efficiency in both time and space,
it affects the cognitive model of the programmer in what data structures
can be represented, it affects latency, interoperability, and much more.

Yet, it is often ignored and almost invisble at the same time. Many consider
it to be a “solved” problem with probably 95% of programming languages
out there using some form of garbage collection: allocate, then worry about
reclaiming unreachable objects later.
^
@https://aardappel.github.io/lobster/memory_management.html
#topic:tea-time
#author:David P. Reed
#language:english
#medium:paper
Naming and Synchronization in a Decenteralized Computer System

^
@http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-205.pdf
#topic:rump-kernel
#author:Antti Kantee
#language:english
#medium:article
The Rise and Fall of the Operating System
An operating system is an arbitrary black box of overhead that enables
well-behaving application programs to perform tasks that users are interested
in. Why is there so much fuss about black boxes, and could we get things
done with less?
^
@http://www.fixup.fi/misc/usenix-login-2015/login_oct15_02_kantee.pdf
#topic:rump-kernel
#author:Antti Kantee
#language:english
#medium:book
This document is intended as an up-to-date description on the fundamental
concepts related to the anykernel and rump kernels. It is based on the
dissertation written in 2011 and early 2012: Flexible Operating System
Internals: The Design and Implementation of the Anykernel and Rump Kernels.
The major change with rump kernels since the first edition is a shift in
focus and motivation. In work leading up to the first edition, rump kernels
were about running kernel components in userspace. That work defined the
core architecture, and that definition is still valid and accurate. Since
then, work has focused on harnessing the potential of rump kernels for
building entirely new computation stacks.  Since this edition of the book
is no longer an academic document, we do not support every statement we make
with a citation or experiment. In fact, we also take the liberty to present
opinions which are open for debate.
^
@http://www.fixup.fi/misc/rumpkernel-book/rumpkernel-bookv2-20160802.pdf
#topic:calculus
#author:H. Jerome Keisler
#language:english
#medium:book
Elementary Calculus: An Infinitesmal Approach

^
@http://www.math.wisc.edu/~keisler/keislercalc-09-04-19.pdf
#topic:standard ml
#author:David Macqueen
#author:Robert Harper
#author:John Reppy
#language:english
#medium:paper
The History of Standard ML
The ML family of strict functional languages, which includes F#, OCaml,
and Standard ML, evolved from the Meta Language of the LCF theorem proving
system developed by Robin Milner and his research group at the University
of Edinburgh in the 1970s. This paper focuses on the history of Standard ML,
which plays a central rôle in this family of languages, as it was the first
to include the complete set of features that we now associate with the name
“ML” (i.e., polymorphic type inference, datatypes with pattern matching,
modules, exceptions, and mutable state).  Standard ML, and the ML family of
languages, have had enormous influence on the world of programming language
design and theory. ML is the foremost exemplar of a functional programming
language with strict evaluation (call-by-value) and static typing. The use
of parametric polymorphism in its type system, together with the automatic
inference of such types, has influenced a wide variety of modern languages
(where polymorphism is often referred to as generics). It has popularized the
idea of datatypes with associated case analysis by pattern matching. The module
system of Standard ML extends the notion of type-level parameterization to
large-scale programming with the notion of parametric modules, or functors.
Standard ML also set a precedent by being a language whose design included
a formal definition with an associated metatheory of mathematical proofs
(such as soundness of the type system). A formal definition was one of the
explicit goals from the beginning of the project. While some previous languages
had rigorous definitions, these definitions were not integral to the design
process, and the formal part was limited to the language syntax and possibly
dynamic semantics or static semantics, but not both.  The paper covers the
early history of ML, the subsequent efforts to define a standard ML language,
and the development of its major features and its formal definition. We also
review the impact that the language had on programming-language research.
^
@https://smlfamily.github.io/history/SML-history.pdf
#topic:calculus
#author:Silvanus P. Thompson
#language:english
#medium:book
Calculus Made Easy

^
@http://djm.cc/library/Calculus_Made_Easy_Thompson.pdf
#topic:category theory
#author:David I. Spivak
#language:english
#medium:book
18-S996: Category Theory for Scientists

^
@http://math.mit.edu/~dspivak/teaching/sp13/CT4S--static.pdf
#topic:logic
#author:Peter Smith
#language:english
#medium:guide
Teach Yourself Logic 2020a: A Study Guide

^
@https://www.logicmatters.net/wp-content/uploads/2020/07/TeachYourselfLogic2020.5.pdf
#topic:x11
#topic:graphics
#topic:protocol
#author:Robert W. Scheifler
#language:english
#medium:specification
X Window System Protocol: X Version 11, Release 6.8

^
@https://www.x.org/releases/X11R7.5/doc/x11proto/proto.pdf
#topic:markov chain
#topic:constraint
#author:Boris Miller
#author:Gregory B. Miller
#author:Konstantin V. Siemenikhin
#language:english
#medium:paper
Optimal control of Markov chains with constraints
A problem of optimal control of Markov chain with finite state space
is considered. We consider a nonstationary finite horizon problem with
constraints, given as a set of inequalities. Basing on recent results
on existence of optimal solution we suggest to use the dual approach to
optimization and thereby an approach to effective numerical algorithms. The
approach is illustrated by numerical examples.
^
@https://www.researchgate.net/profile/Gregory_Miller13/publication/224109362_Optimal_control_of_Markov_chains_with_constraints/links/53fa1bf60cf2e3cbf5626442/Optimal-control-of-Markov-chains-with-constraints.pdf
#topic:turing completeness
#topic:neural network
#author:Jorge Perez
#author:Javier Marinković
#author:Pablo Barceló
#language:english
#medium:paper
On The Turing Completeness Of Modern Neural Network Architectures
Alternatives to recurrent neural networks, in particular, architectures based
on attention or convolutions, have been gaining momentum for processing input
sequences. In spite of their relevance, the computational properties of these
alternatives have not yet been fully explored. We study the computational power
of two of the most paradigmatic architectures exemplifying these mechanisms:
the Transformer (Vaswani et al., 2017) and the Neural GPU (Kaiser & Sutskever,
2016). We show both models to be Turing complete exclusively based on their
capacity to compute and access internal dense representations of the data. In
particular, neither the Transformer nor the Neural GPU requires access to
an external memory to become Turing complete. Our study also reveals some
minimal sets of elements needed to obtain these completeness results.
^
@https://arxiv.org/pdf/1901.03429.pdf
#topic:neural network
#topic:autoencoder
#author:Felix Berkhahn
#author:Richard Keys
#author:Wajih Ouertani
#author:Nikhil Shetty
#author:Dominik Geißler
#language:english
#medium:paper
One Model To Rule Them All
We present a new flavor of Variational Autoencoder (VAE) that interpolates
seamlessly between unsupervised, semi-supervised and fully supervised learning
domains. We show that unlabeled datapoints not only boost unsupervised
tasks, but also the classification performance. Vice versa, every label
not only improves classification, but also unsupervised tasks. The proposed
architecture is simple: A classification layer is connected to the topmost
encoder layer, and then combined with the resampled latent layer for the
decoder. The usual evidence lower bound (ELBO) loss is supplemented with
a supervised loss target on this classification layer that is only applied
for labeled datapoints. This simplicity allows for extending any existing
VAE model to our proposed semi-supervised framework with minimal effort. In
the context of classification, we found that this approach even outperforms
a direct supervised setup.
^
@https://arxiv.org/pdf/1908.03015v1
#topic:reverse engineering
#author:Dennis Yurichev
#language:english
#medium:book
Reverse Engineering for Beginners

^
@https://beginners.re/RE4B-EN.pdf
#topic:opengl
#topic:graphics
#author:Joey de Vries
#language:english
#medium:book
Learn OpenGL - Graphics Programming

^
@https://learnopengl.com/book/book_pdf.pdf
#topic:vulkan
#topic:graphics
#language:english
#medium:book
Vulkan Tutorial
This tutorial will teach you the basics of using the Vulkan graphics and
compute API. Vulkan is a new API by the Khronos group (known for OpenGL)
that provides a much better abstraction of modern graphics cards. This new
interface allows you to better describe what your application intends to do,
which can lead to better performance and less surprising driver behavior
compared to existing APIs like OpenGL and Direct3D. The ideas behind Vulkan
are similar to those of Direct3D 12 and Metal, but Vulkan has the advantage
of being fully cross-platform and allows you to develop for Windows, Linux
and Android at the same time.
^
@https://raw.githubusercontent.com/Overv/VulkanTutorial/master/ebook/Vulkan%20Tutorial%20en.pdf
#topic:spirv
#topic:graphics
#author:John Kessenich
#author:Boaz Ouriel
#author:Raun Krisch
#language:english
#medium:specification
SPIR-V Specification

^
@https://www.khronos.org/registry/spir-v/specs/unified1/SPIRV.pdf
#topic:perfect hash
#topic:hash function
#author:Emmanuel Esposito
#author:Thomas Mueller Graf
#author:Sebastiano Vigna
#language:english
#medium:paper
RecSplit: Minimal Perfect Hashing via Recursive Splitting
A minimal perfect hash function bijectively maps a key set S out of
a universe U into the first jSj natural numbers. Minimal perfect hash
functions are used, for example, to map irregularly-shaped keys, such as
strings, in a compact space so that metadata can then be simply stored in
an array. While it is known that just 1:44 bits per key are necessary to
store a minimal perfect hash function, no published technique can go below
2 bits per key in practice. We propose a new technique for storing minimal
perfect hash functions with expected linear construction time and expected
constant lookup time that makes it possible to build for the first time,
for example, structures which need 1:56 bits per key, that is, within 8:3%
of the lower bound, in less than 2 ms per key. We show that instances of
our construction are able to simultaneously beat the construction time,
space usage and lookup time of the state-of-the-art data structure reaching
2 bits per key. Moreover, we provide parameter choices giving structures
which are competitive with alternative, larger-size data structures in terms
of space and lookup time. The construction of our data structures can be
easily parallelized or mapped on distributed computational units (e.g.,
within the MapReduce framework), and structures larger than the available
RAM can be directly built in mass storage.
^
@https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14
#topic:neural network
#topic:compression
#author:Guiying Li
#author:Chao Qian
#author:Chunhui Jiang
#author:Xiaofen Lu
#author:Ke Tang
#language:english
#medium:paper
Optimization based Layer-wise Magnitude-based Pruning for DNN Compression∗
Layer-wise magnitude-based pruning (LMP) is a very popular method for deep
neural network (DNN) compression. However, tuning the layerspecific thresholds
is a difficult task, since the space of threshold candidates is exponentially
large and the evaluation is very expensive. Previous methods are mainly by hand
and require expertise. In this paper, we propose an automatic tuning approach
based on optimization, named OLMP. The idea is to transform the threshold
tuning problem into a constrained optimization problem (i.e., minimizing the
size of the pruned model subject to a constraint on the accuracy loss), and
then use powerful derivative-free optimization algorithms to solve it. To
compress a trained DNN, OLMP is conducted within a new iterative pruning
and adjusting pipeline. Empirical results show that OLMP can achieve the
best pruning ratio on LeNet-style models (i.e., 114 times for LeNet-300-100
and 298 times for LeNet-5) compared with some state-ofthe-art DNN pruning
methods, and can reduce the size of an AlexNet-style network up to 82 times
without accuracy loss.
^
@https://www.ijcai.org/Proceedings/2018/0330.pdf
#topic:neural network
#topic:compression
#author:Haotao Wang
#author:Shupeng Gui
#author:Haichuan Yang
#author:Ji Liu
#author:Zhangyang Wang
#language:english
#medium:paper
GAN Slimming: All-in-One GAN Compression by A Unified Optimization Framework
Generative adversarial networks (GANs) have gained increasing popularity
in various computer vision applications, and recently start to be deployed
to resource-constrained mobile devices. Similar to other deep models,
state-of-the-art GANs suffer from high parameter complexities. That
has recently motivated the exploration of compressing GANs (usually
generators). Compared to the vast literature and prevailing success in
compressing deep classifiers, the study of GAN compression remains in its
infancy, so far leveraging individual compression techniques instead of more
sophisticated combinations. We observe that due to the notorious instability
of training GANs, heuristically stacking different compression techniques
will result in unsatisfactory results. To this end, we propose the first
unified optimization framework combining multiple compression means for
GAN compression, dubbed GAN Slimming (GS). GS seamlessly integrates three
mainstream compression techniques: model distillation, channel pruning
and quantization, together with the GAN minimax objective, into one unified
optimization form, that can be efficiently optimized from end to end. Without
bells and whistles, GS largely outperforms existing options in compressing
image-to-image translation GANs. Specifically, we apply GS to compress
CartoonGAN, a state-of-the-art style transfer network, by up to 47 times,
with minimal visual quality degradation.
^
@https://arxiv.org/pdf/2008.11062.pdf
#topic:simulated annealing
#topic:ant colony optimization
#topic:optimization
#topic:compression
#author:FARHAD KOLAHAN
#author:AHMAD TAVAKOLI
#author:SAEED SOHEILI
#author:MAHDI ABACHIZADEH
#author:GOLNAZ TADAYON
#language:english
#medium:paper
Optimization of helical compression springs using simulated annealing and ant colony optimization
In this paper, the optimization of compression helical springs is
investigated. The design process involves determining wire material, end type
of the spring and wire diameter. In this regards, important design constraints
are taken into account. The objective is to minimize the figure of merit,
which shows the relative cost of spring. Two heuristic algorithms, namely
simulated annealing and ant colony optimization, are employed to optimize the
spring. The results obtained by these methods are compared with each other,
and with the exact solution of the problem.
^
@https://profdoc.um.ac.ir/articles/a/1015166.pdf
#topic:simulated annealing
#topic:optimization
#author:Ke Yang
#author:Qingxi Duan
#author:Yanghao Wang
#author:Teng Zhang
#author:Yuchao Yang1
#author:Ru Huang
#language:english
#medium:paper
Transiently chaotic simulated annealing based on intrinsic nonlinearity of memristors for efficient solution of optimization problems
Optimization problems are ubiquitous in scientific research, engineering,
and daily lives. However, solving a complex optimization problem often
requires excessive computing resource and time and faces challenges in
easily getting trapped into local optima. Here, we propose a memristive
optimizer hardware based on a Hopfield network, which introduces transient
chaos to simulated annealing in aid of jumping out of the local optima
while ensuring convergence. A single memristor crossbar is used to store
the weight parameters of a fully connected Hopfield network and adjust the
network dynamics in situ. Furthermore, we harness the intrinsic nonlinearity
of memristors within the crossbar to implement an efficient and simplified
annealing process for the optimization. Solutions of continuous function
optimizations on sphere function and Matyas function as well as combinatorial
optimization on Max-cut problem are experimentally demonstrated, indicating
great potential of the transiently chaotic memristive network in solving
optimization problems in general.
^
@https://advances.sciencemag.org/content/advances/6/33/eaba9901.full.pdf
#topic:simd
#topic:fft
#author:Stefan Kral
#author:Franz Franchetti
#author:Juergen Lorenz
#author:Christoph W. Ueberhuber
#language:english
#medium:paper
SIMD Vectorization of Straight Line FFT Code
This paper presents compiler technology that targets general purpose
microprocessors augmented with SIMD execution units for exploiting data
level parallelism. FFT kernels are accelerated by automatically vectorizing
blocks of straight line code for processors featuring two-way short vector
SIMD extensions like AMD’s 3DNow! and Intel’s SSE 2. Additionally,
a special compiler backend is introduced which is able to (i) utilize
particular code properties, (ii) generate optimized address computation,
and (iii) apply specialized register allocation and instruction scheduling.
Experiments show that automatic SIMD vectorization can achieve performance
that is comparable to the optimal hand-generated code for FFT kernels. The
newly developed methods have been integrated into the codelet generator of
Fftw and successfully vectorized complicated code like real-to-halfcomplex
non-power-of-two FFT kernels. The floatingpoint performance of Fftw’s
scalar version has been more than doubled, resulting in the fastest FFT
implementation to date.
^
@https://users.ece.cmu.edu/~franzf/papers/europar03.pdf
#topic:simd
#author:Umberto Santoni
#author:Thomas Long
#language:english
#medium:paper
Signal Processing on Intel® Architecture: Performance Analysis using Intel® Performance Primitives
Signal processing functions have often required special-purpose hardware
such as DSPs and FPGAs. However, recent enhancements to Intel® architecture
processors are providing developers an alternative: execute signal processing
workloads on an Intel® processor.  Signal processing on the latest
Intel processors is now a viable option due to continued improvements in
multi-core architectures. The increased parallelism from vector instructions,
along with other continuing performance improvements, enables the efficient
execution of data parallel workloads such as digital transforms and filters.
Additionally, by consolidating signal processing functions with other
workloads on a multi-core Intel processor, it is possible to save hardware
cost, simplify the application development environment and reduce time to
market. This approach can be applied to many applications in aerospace (radar,
sonar), communications infrastructure (baseband processing, transcoding)
and healthcare (medical imaging).  This paper describes an easy process
that allows developers to quickly determine how fast 2nd generation Intel®
Core™ i7-2710QE processor will execute their signal processing algorithms,
based on performance data1 that is relatively easy to obtain.
Developers can complete the process in a straightforward manner, as
demonstrated with two simple examples in this paper: fast convolution
and amplitude demodulation.  The paper concludes by reviewing some of the
development tools available to developers to conduct their own evaluations.
^
@https://www.intel.com/content/dam/doc/white-paper/signal-processing-on-intel-architecture.pdf
#topic:fft
#author:Eric Postpischil
#language:english
#medium:paper
Construction of a High-Performance FFT
The FFT algorithm for computing the DFT is well known and provides an
O(n log n)- time implementation of the DFT. However, constructing a high-performance
FFT implementation that executes at the best possible speed requires careful
and efficient organization.  This paper describes the mathematical composition
of an FFT, some overall design considerations for implementing high-performance
FFTs, and specific considerations for implementing a high-performance FFT
on an AltiVec processor.
^
@https://edp.org/work/Construction.pdf
#topic:cryptography
#topic:testing
#author:Andrew Rukhin
#author:Juan Soto
#author:James Nechvatal
#author:Miles Smid
#author:Elaine Barker
#author:Stefan Leigh
#author:Mark Levenson
#author:Mark Vangel
#author:David Banks
#author:Alan Heckert
#author:James Dray
#author:San Vo
#language:english
#medium:paper
A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications
This paper discusses some aspects of selecting and testing random and
pseudorandom number generators.  The outputs of such generators may be
used in many cryptographic applications, such as the generation of key
material. Generators suitable for use in cryptographic applications may need
to meet stronger requirements than for other applications. In particular,
their outputs must be unpredictable in the absence of knowledge of the
inputs. Some criteria for characterizing and selecting appropriate generators
are discussed in this document. The subject of statistical testing and its
relation to cryptanalysis is also discussed, and some recommended statistical
tests are provided. These tests may be useful as a first step in determining
whether or not a generator is suitable for a particular cryptographic
application. However, no set of statistical tests can absolutely certify
a generator as appropriate for usage in a particular application, i.e.,
statistical testing cannot serve as a substitute for cryptanalysis. The
design and cryptanalysis of generators is outside the scope of this paper.
^
@https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-22r1a.pdf
#topic:hazard pointers
#author:Paul Khuong
#language:english
#medium:web article
Flatter wait-free hazard pointers
Back in February 2020, Blelloch and Wei submitted this cool preprint:
Concurrent Reference Counting and Resource Management in Wait-free
Constant Time. Their work mostly caught my attention because they propose a
wait-free implementation of hazard pointers for safe memory reclamation.1
Safe memory reclamation  is a key component in lock-free algorithms when
garbage collection isn’t an option,2 and hazard pointers  let us bound
the amount of resources stranded by delayed cleanups much more tightly than,
e.g., epoch reclamation. However the usual implementation has a loop in its
read barriers (in the garbage collection sense), which can be annoying for
code generation and bad for worst-case time bounds.
^
@https://pvk.ca/Blog/2020/07/07/flatter-wait-free-hazard-pointers/
#topic:page fault
#topic:x86
#topic:turing-complete
#author:Julian Bangert
#author:Sergey Bratus
#author:Rebecca Shapiro
#author:Sean W. Smith
#language:english
#medium:paper
The Page-Fault Weird Machine: Lessons in Instruction-less Computation
Trust Analysis, i.e. determining that a system will not execute some class
of computations, typically assumes that all computation is captured by an
instruction trace.  We show that powerful computation on x86 processors
is possible without executing any CPU instructions. We demonstrate
a Turing-complete execution environment driven solely by the IA32
architecture’s interrupt handling and memory translation tables, in which
the processor is trapped in a series of page faults and double faults, without
ever successfully dispatching any instructions. The “hard-wired” logic
of handling these faults is used to perform arithmetic and logic primitives,
as well as memory reads and writes. This mechanism can also perform branches
and loops if the memory is set up and mapped just right. We discuss the
lessons of this execution model for future trustworthy architectures.
^
@https://www.usenix.org/system/files/conference/woot13/woot13-bangert.pdf
#topic:generatice adversarial network
#topic:stylegan
#author:Tero Karras
#author:Samuli Laine
#author:Timo Aila
#language:english
#medium:paper
A Style-Based Generator Architecture for Generative Adversarial Networks
We propose an alternative generator architecture for generative adversarial
networks, borrowing from style transfer literature. The new architecture leads
to an automatically learned, unsupervised separation of high-level attributes
(e.g., pose and identity when trained on human faces) and stochastic variation
in the generated images (e.g., freckles, hair), and it enables intuitive,
scale-specific control of the synthesis. The new generator improves the
state-of-the-art in terms of traditional distribution quality metrics,
leads to demonstrably better interpolation properties, and also better
disentangles the latent factors of variation. To quantify interpolation
quality and disentanglement, we propose two new, automated methods that
are applicable to any generator architecture. Finally, we introduce a new,
highly varied and high-quality dataset of human faces.
^
@https://arxiv.org/pdf/1812.04948.pdf
#topic:security
#topic:speculative execution
#topic:vulnerability
#author:Enes Göktaş
#author:Kaveh Razavi
#author:Georgios Portokalidis
#language:english
#medium:paper
Speculative Probing: Hacking Blind in the Spectre Era
To defeat ASLR or more advanced fine-grained and leakage-resistant
code randomization schemes, modern software exploits rely on information
disclosure to locate gadgets inside the victim’s code. In the absence
of such info-leak vulnerabilities, attackers can still hack blind and
derandomize the address space by repeatedly probing the victim’s memory
while observing crash side effects, but doing so is only feasible for
crash-resistant programs. However, high-value targets such as the Linux
kernel are not crash-resistant. Moreover, the anomalously large number
of crashes is often easily detectable.  In this paper, we show that the
Spectre era enables an attacker armed with a single memory corruption
vulnerability to hack blind without triggering any crashes. Using speculative
execution for crash suppression allows the elevation of basic memory write
vulnerabilities into powerful speculative probing primitives that leak through
microarchitectural side effects. Such primitives can repeatedly probe victim
memory and break strong randomization schemes without crashes and bypass
all deployed mitigations against Spectrelike attacks. The key idea behind
speculative probing is to break Spectre mitigations using memory corruption
and resurrect Spectrestyle disclosure primitives to mount practical blind
software exploits. To showcase speculative probing, we target the Linux kernel,
a crash-sensitive victim that has so far been out of reach of blind attacks,
mount end-to-end exploits that compromise the system with just-in-time code
reuse and data-only attacks from a single memory write vulnerability, and
bypass strong Spectre and strong randomization defenses. Our results show
that it is crucial to consider synergies between different (Spectre vs. code
reuse) threat models to fully comprehend the attack surface of modern systems.
^
@https://download.vusec.net/papers/blindside_ccs20.pdf
#topic:license
#topic:gplv3
#topic:gpl
#author:James E.J. Bottomley
#author:Mauro Carvalho Chehab
#author:Thomas Gleixner
#author:Christoph Hellwig
#author:Dave Jones
#author:Greg Kroah-Hartman
#author:Tony Luck
#author:Andrew Morton
#author:Trond Myklebust
#author:David Woodhouse
#language:english
#medium:paper
The Dangers and Problems with GPLv3
This document is a position statement on the GNU General Public License version
3 (in its current Draft 2 form) and its surrounding process issued by some of
the Maintainers of the Linux Kernel speaking purely in their role as kernel
maintainers. In no regard should any opinion expressed herein be construed
to represent the views of any entities employing or being associated with
any of the authors.
^
@https://static.lwn.net/images/pdf/kernel_gplv3_position.pdf
#topic:data oriented
#author:Richard Fabian
#language:english
#medium:book
Data-Oriented Design

^
@https://www.dataorienteddesign.com/dodbook/
#topic:parsing
#topic:error recovery
#author:Tim A. Wagner
#author:Susan L. Graham
#language:english
#medium:paper
History-Sensitive Error Recovery
We present a novel approach to incremental recovery from lexical and
syntactic errors in an interactive software development environment. Unlike
existing techniques, we utilize the history of changes to the program
to discover the natural correlation between user modifications and
errors detected during incremental lexical and syntactic analysis. Our
technique is non-correcting—the analysis refuses to incorporate invalid
modifications, while still permitting correct changes to be applied. Errors
are presented to the user simply by highlighting the invalid changes.
The approach is automated—no user action is required to detect or recover
from errors. Multiple textual and structural edits, arbitrary timing of
incremental analysis, multiple errors per analysis, and nested errors
are supported. Historybased error recovery is language independent and is
compatible with the best known methods for incremental lexing and parsing,
adding neither time nor space overhead to those algorithms. Effective
integration with the environment’s history services ensures that other
tools can efficiently discover regions of the program (un)affected by errors,
and that any transformations of the program required to isolate or present
errors are themselves efficiently reversible operations.
^
@http://harmonia.cs.berkeley.edu/papers/twagner-er.pdf
#topic:parsing
#author:Lukas Diekmann
#language:english
#medium:paper
Editing composed languages
The development of domain-specific languages and the migration of legacy
software have long been problems for which language composition offers
an enticing solution.  Unfortunately, approaches thus far have failed
to meet expectations, largely due to the difficulty of writing composed
programs. Language composition editors have traditionally fallen into
two extremes: traditional parsing, which is inflexible or ambiguous; or
syntaxdirected editing, which programmers dislike. This thesis extends an
incremental parser to create an approach that bridges the two extremes: an
editor that ‘feels’ like a normal text editor, but always operates on
a valid tree as in syntax-directed editing, which allows users to compose
arbitrary syntaxes. I first take an existing incremental parsing algorithm
and fix several errors in it. I then extend it with incremental abstract
syntax trees and support for whitespace-sensitive languages, which increases
the range of languages the algorithm can support. I then introduce the notion
of language boxes, which allow an incremental parser to be used for language
composition and implement them in a prototype editor.  Finally, I show how
language boxes can, in many useful cases, be automatically inserted and
removed without the need for user intervention.
^
@https://diekmann.co.uk/diekmann_phd.pdf
#topic:neural network
#topic:machine learning
#topic:voice synthesis
#author:Sercan ̈O. Arık
#author:Mike Chrzanowski
#author:Adam Coates
#author:Gregory Diamos
#author:Andrew Gibiansky
#author:Yongguo Kang
#author:Xian Li
#author:John Miller
#author:Andrew Ng
#author:Jonathan Raiman
#author:Shubho Sengupta
#author:Mohammad Shoeybi
#language:english
#medium:paper
Deep Voice: Real-time Neural Text-to-Speech
We present Deep Voice, a production-qualitytext-to-speech system constructed
entirely fromdeep neural networks.Deep Voice lays thegroundwork for
truly end-to-end neural speechsynthesis.The system comprises five ma-jor
building blocks: a segmentation model forlocating phoneme boundaries, a
grapheme-to-phoneme conversion model, a phoneme durationprediction model,
a fundamental frequency pre-diction model, and an audio synthesis model.For
the segmentation model, we propose a novelway of performing phoneme boundary
detectionwith deep neural networks using connectionisttemporal classification
(CTC) loss.  For the au-dio synthesis model, we implement a variantof WaveNet
that requires fewer parameters andtrains faster than the original. By using
a neu-ral network for each component, our system issimpler and more flexible
than traditional text-to-speech systems, where each component requireslaborious
feature engineering and extensive do-main expertise.  Finally, we show that
inferencewith our system can be performed faster than realtime and describe
optimized WaveNet inferencekernels on both CPU and GPU that achieve up to400x
speedups over existing implementations.
^
@https://arxiv.org/pdf/1702.07825.pdf
#topic:interview
#topic:humour
#author:Kyle Kingsbury
#language:english
#medium:web article
Rewriting the Technical Interview

^
@https://aphyr.com/posts/353-rewriting-the-technical-interview
#topic:pretty printing
#author:David Christiansen
#author:David Darais
#author:Weixi Ma
#language:english
#medium:paper
The Final Pretty Printer
Widely-used pretty printing libraries are built on assump-tions from a previous
age of computing that are no longeruniversally true, such as monospace fonts
and batch-modecompilers. Furthermore, they are not extensible, which hasled
to a plethora of similar libraries. We demonstrate anapproach to pretty
printing that is independently extensibleand supports proportional fonts
and interactive interfaces.
^
@http://davidchristiansen.dk/drafts/final-pretty-printer-draft.pdf
#topic:mpv
#topic:locale
#topic:humour
#language:english
#medium:commit
stream_libarchive: workaround various types of locale braindeath

^
@https://github.com/mpv-player/mpv/commit/1e70e82baa9193f6f027338b0fab0f5078971fbe
#topic:parsec
#topic:parser combinators
#author:Daan Leijen
#author:Erik Meijer
#language:english
#medium:paper
Parsec: Direct Style Monadic Parser Combinators For The Real World
Despite the long list of publications on parser combinators, there doesnot yet
exist a monadic parser combinator library that is applicable in realworld
situations. In particular naive implementations of parser combina-tors
are likely to suffer from space leaks and are often unable to reportprecise
error messages in case of parse errors. The Parsec parser com-binator library
described in this paper, utilizes a novel implementationtechnique for space
and time efficient parser combinators that in case ofa parse error, report
both the position of the error as well asallgrammarproductions that would
have been legal at that point in the input.
^
@https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/parsec-paper-letter.pdf
#topic:x86
#topic:memory model
#author:Scott Owens
#author:Susmit Sarkar
#author:Peter Sewell
#language:english
#medium:paper
A Better x86 Memory Model: x86-TSO
Real multiprocessors do not provide the sequentially consis-tent memory
that is assumed by most work on semantics and verifica-tion. Instead,
they have relaxed memory models, typically described inambiguous prose,
which lead to widespread confusion. These are primetargets for mechanized
formalization. In previous work we produced a rig-orousx86-CCmodel,
formalizing the Intel and AMD architecture spec-ifications of the time,
but those turned out to be unsound with respectto actual hardware, as well
as arguably too weak to program above.We discuss these issues and present
a newx86-TSOmodel that suffersfrom neither problem, formalized in HOL4. We
believe it is sound withrespect to real processors, reflects better the
vendor’s intentions, and isalso better suited for programming. We give
two equivalent definitionsofx86-TSO: an intuitive operational model based
on local write buffers, andan axiomatic total store ordering model, similar
to that of the SPARCv8.Both are adapted to handle x86-specific features. We
have implementedthe axiomatic model in ourmemeventstool, which calculates the
set of allvalid executions of test programs, and, for greater confidence,
verify thewitnesses of such executions directly, with code extracted froma
third,more algorithmic, equivalent version of the definition
^
@https://www.cl.cam.ac.uk/~pes20/weakmemory/x86tso-paper.tphols.pdf
#topic:thread local storage
#author:Ulrich Drepper
#language:english
#medium:paper
ELF Handling For Thread-Local Storage
Increasing  use  of  threads  lead  developers  to  wish  for  a  better
way  of  dealing  withthread-local data.  The POSIX thread interface defines
interfaces which allow storingvoid*objects separate for each thread. But
the interface is cumbersome to use. A keyfor the object has to be allocated
dynamically at run-time. If the key isn’t used anymoreit must be freed.
While this is already a lot of work and error prone it becomes a realproblem
when combined with dynamically loaded code.To counter these problems it
was decided to extend the programming languages tolet the compiler take
over the job.  For C and C++ the new keywordthreadcan beused in variable
definitions and declarations.  This is not an official extension of
thelanguage but compiler writers are encouraged to implement them to support
the newABI. Variables defined and declared this way would automatically be
allocated local toeach thread.
^
@https://akkadia.org/drepper/tls.pdf
#topic:stack machine
#topic:register machine
#topic:performance
#author:Ruijie Fang
#author:Siqi Liu
#language:english
#medium:paper
A Performance Survey on Stack-based and Register-based Virtual Machines
Virtual machines have been widely adapted for high-level programming language
implementations and forproviding a degree of platform neutrality.  As the
overall use and adaptation of virtual machines grow, theoverall performance of
virtual machines has become a widely-discussed topic. In this paper, we present
a surveyon the performance differences of the two most widely adaptedtypes
of virtual machines - the stack-basedvirtual machine and the register-based
virtual machine - using various benchmark programs. Additionally, weadopted
a new approach of measuring performance by measuring the overall dispatch
time, amount of dispatches,fetch time, and execution time while running
benchmarks on custom-implemented, lightweight virtual machines.Finally, we
present two lightweight, custom-designed, Turing-equivalent virtual machines
that are specificallydesigned in benchmarking virtual machine performance
- the“Conceptum” stack-based virtual machine, and the“Inertia”
register-based virtual machine. Our result showed that while on average
the register machine spends20.39% less time in executing benchmarks than
the stack machine, the stack-based virtual machine is still fasterthan the
virtual machine regarding the instruction fetch time
^
@https://arxiv.org/pdf/1611.00467.pdf
#topic:forth
#topic:robotics
#author:Howerd Oakford
#author:Stephen Pelc
#language:english
#medium:paper
Three Forths Make a Hole
There are many theories about the best way to program a computer – the ACE
project showed just what can be done with Forth, especially in a situation
which was constantly changing.
^
@http://www.inventio.co.uk/threeforthsmakeahole.htm
#topic:return-oriented programming
#topic:openbsd
#topic:security
#author:Todd Mortimer
#language:english
#medium:paper
Removing ROP Gadgets from OpenBSD
Return Oriented Programming (ROP) is a common exploita-tion technique that
reuses existing code fragments (gadgets)to construct shellcode in a compromised
program. Recentchanges in OpenBSD’s compiler have started to reduce thenumber
of gadgets in x86 and arm64 binaries, with the aim ofmaking ROP exploitation
more difficult or impossible. Thispaper will cover how ROP gadgets emerge
from legitimatecode, how OpenBSD’s compiler removes these gadgets, andthe
effects on performance, code size, and ROP tool capabil-ities. We find that
it is possible to meaningfully reduce thenumber of ROP gadgets in programs,
and to effectively hinderROP tool capabilities.
^
@https://doi.asiabsdcon.org/10.25263/asiabsdcon2019/p01b
#topic:parsing
#topic:information extraction
#author:Wonseok Hwang
#author:Jinyeong Yim
#author:Seunghyun Park
#author:Sohee Yang
#author:Minjoon Seo
#language:english
#medium:paper
Spatial Dependency Parsing forSemi-Structured Document Information Extraction
Information  Extraction  (IE)  for  semi-structured  documentimages is often
approached as a sequence tagging problemby  classifying  each  recognized
input  token  into  one  of  theIOB (Inside, Outside, and Beginning)
categories. However,such  problem  setup  has  two  inherent  limitations
that  (1)  itcannot easily handle complex spatial relationships and (2)
itis not suitable for highly structured information, which arenevertheless
frequently observed in real-world document im-ages. To tackle these issues, we
first formulate the IE task asspatial dependency parsingproblem that focuses
on the rela-tionship among text segment nodes in the documents. Underthis
setup, we then propose SPADE♠(SPAtial DEpendencyparser) that models highly
complex spatial relationships andan arbitrary number of information layers
in the documentsin an end-to-end manner. We evaluate it on various kinds
ofdocuments such as receipts, name cards, forms, and invoices,and show that
it achieves a similar or better performance com-pared to strong baselines
including BERT-based IOB taggger,with up to 37.7% improvement.
^
@https://arxiv.org/pdf/2005.00642.pdf
#topic:repl
#topic:program synthesis
#author:Hila Peleg
#author:Usaroi Gabay
#author:Shachar Itzhaky
#author:Eran Yahav
#language:english
#medium:paper
A frequent programming pattern for small tasks, especially expressions, is
to repeatedly evaluate the programon an input as its editing progresses. The
Read-Eval-Print Loop (REPL) interaction model has been a successfulmodel
for this programming pattern. We present the new notion of Read-Eval-Synth
Loop (RESL) that extendsREPLby providing in-place synthesis on parts of the
expression marked by the user.RESLeases programmingby synthesizing parts of
a required solution. The underlying synthesizer relies on a partial solution
from theprogrammer and a few examples.RESLhinges on bottom-up synthesis with
general predicates and sketching, generalizing programming byexample. To
makeRESLpractical, we present a formal framework that extends observational
equivalence tonon-example specifications.We evaluateRESLby conducting a
controlled within-subjects user-study on19programmers from8companies, where
programmers are asked to solve a small but challenging set of competitive
programmingproblems. We find that programmers usingRESLsolve these problems
with far less need to edit the codethemselves and by browsing documentation
far less. In addition, they are less likely to leave a task unfinishedand
more likely to be correct.
^
@https://cseweb.ucsd.edu/~hpeleg/resl-oopsla20.pdf
#topic:webassembly
#author:Andreas Rossberg
#author:WebAssembly Community Group
#language:english
#medium:paper
WebAssembly Specification Release 1.1
WebAssembly (abbreviated Wasm2) is asafe, portable, low-level code
formatdesigned for efficient execution andcompact representation. Its main
goal is to enable high performance applications on the Web, but it does not
makeany Web-specific assumptions or provide Web-specific features, so it
can be employed in other environments aswell.WebAssembly is an open standard
developed by a W3C Community Group1.This document describes version 1.1 of
thecoreWebAssembly standard. It is intended that it will be supersededby
new incremental releases with additional features in the future.
^
@https://webassembly.github.io/spec/core/_download/WebAssembly.pdf
#topic:filesystem
#topic:fat32
#author:Microsoft Corporation
#language:english
#medium:book
Microsoft FAT Specification
This document describes the on-media FAT file system format. This document is
written to help guide development of FAT implementations that are compatible
with those provided by Microsoft. This document does not describe all
algorithms contained in the Microsoft FAT file system driver implementation
neither does it describe all algorithms contained in associated utilities
(Microsoft format and chkdsk utilities). However, it is expected that the
reader will refer to the Microsoft Corporation FAT file system reference
source code for additional clarification as/when needed. There are three
variants of the FAT on-disk format, namely:
•  FAT12
•  FAT16
•  FAT32
Data structures comprising all three variants are described here. Also
provided are descriptions of specific algorithms that will be useful to the
engineer implementing a FAT driver for reading and/or writing to media. It is
expected that the FAT Test Specification document will be used by the reader to
validate interoperability and correctness of the resultant FAT implementation.
^
@http://read.pudn.com/downloads77/ebook/294884/FAT32%20Spec%20(SDA%20Contribution).pdf
#topic:linux
#topic:kernel module
#author:Peter Jay Salzman
#author:Michael Burian
#author:Ori Pomerantz
#language:english
#medium:book
The Linux Kernel Module Programming Guide
So, you want to write a kernel module. You know C, you've written a few normal
programs to run asprocesses, and now you want to get to where the real action
is, to where a single wild pointer can wipe outyour file system and a core
dump means a reboot.What exactly is a kernel module? Modules are pieces of
code that can be loaded and unloaded into the kernelupon demand. They extend
the functionality of the kernel without the need to reboot the system. For
example,one type of module is the device driver, which allows the kernel to
access hardware connected to the system.Without modules, we would have to
build monolithic kernels and add new functionality directly into thekernel
image. Besides having larger kernels, this has the disadvantage of requiring
us to rebuild and reboot thekernel every time we want new functionality
^
@https://tldp.org/LDP/lkmpg/2.6/lkmpg.pdf
#topic:rest
#topic:protocol
#author:Roy T. Fielding
#author:Richard N. Taylor
#language:english
#medium:paper
Principled Design of the ModernWeb Architecture
The World Wide Web has succeeded in large part because its software
architecture has been de-signed to meet the needs of an Internet-scale
distributed hypermedia application. The modernWeb architecture emphasizes
scalability of component interactions, generality of interfaces, inde-pendent
deployment of components, and intermediary components to reduce interaction
latency,enforce security, and encapsulate legacy systems. In this article
we introduce the RepresentationalState Transfer (REST) architectural style,
developed as an abstract model of the Web architectureand used to guide our
redesign and definition of the Hypertext Transfer Protocol and UniformResource
Identifiers. We describe the software engineering principles guiding REST and
the inter-action constraints chosen to retain those principles, contrasting
them to the constraints of otherarchitectural styles. We then compare the
abstract model to the currently deployed Web architec-ture in order to
elicit mismatches between the existing protocols and the applications they
areintended to support.
^
@https://www.ics.uci.edu/~taylor/documents/2002-REST-TOIT.pdf
#topic:subdivision
#topic:graphics
#author:E Catmull
#author:J Clark
#language:english
#medium:paper
Recursively generated B-spline surfaces on arbitrary topological meshes

^
@https://people.eecs.berkeley.edu/~sequin/CS284/PAPERS/CatmullClark_SDSurf.pdf
#topic:neural network
#topic:reinforcement leaning
#author:Wojciech Jaśkowski
#language:english
#medium:paper
Mastering 2048 with Delayed Temporal Coherence Learning, Multi-Stage Weight Promotion, Redundant Encoding and Carousel Shaping
2048 is an engaging single-player, nondeterministic video puzzle game, which,
thanks to the simple rules and hard-to-master gameplay, has gained massive
popularity in recent years. As 2048 can be conveniently embedded into the
discrete-state Markov decision processes framework, we treat it as a testbed
for evaluating existing and new methods in reinforcement learning. With
the aim to develop a strong 2048 playing program, we employ temporal
difference learning with systematic n-tuple networks. We show that this
basic method can be significantly improved with temporal coherence learning,
multi-stage function approximator with weight promotion, carousel shaping,
and redundant encoding. In addition, we demonstrate how to take advantage
of the characteristics of the n-tuple network, to improve the algorithmic
effectiveness of the learning process by i) delaying the (decayed) update
and applying lock-free optimistic parallelism to effortlessly make advantage
of multiple CPU cores. This way, we were able to develop the best known 2048
playing program to date, which confirms the effectiveness of the introduced
methods for discrete-state Markov decision problems.
^
@https://arxiv.org/pdf/1604.05085.pdf
#topic:security
#author:Trevor Perrin
#author:Moxie Marlinspike
#medium:paper
#language:english
The Double Ratchet Algorithm
The Double Ratchet algorithm is used by two parties to exchange
encrypted messages based on a shared secret key. Typically the parties will
use some key agreement protocol (such as X3DH [1]) to agree on the shared
secret key. Following this, the parties will use the Double Ratchet to send
and receive encrypted messages.The parties derive new keys for every Double
Ratchet message so that earlier keys cannot be calculated from later ones. The
parties also send Diffie-Hellman public values attached to their messages. The
results of Diffie-Hellman calculations are mixed into the derived keys so
that later keys cannot be calculated from earlier ones. These properties
gives some protection to earlier or later encrypted messages in case of a
compromise of a party’s keys. The Double Ratchet and its header encryption
variant are presented below, and their security properties are discussed.
^
@https://signal.org/docs/specifications/doubleratchet/doubleratchet.pdf
#topic:neural network
#topic:language model
#author:Yoshua Bengio
#author:Réjean Ducharme
#author:Pascal Vincent
#author:Christian Jauvin
#medium:paper
#language:english
A Neural Probabilistic Language Model
A goal of statistical language modeling is to learn the joint probability
function of sequences ofwords in a language. This is intrinsically difficult
because of thecurse of dimensionality:awordsequence on which the model will
be tested is likely to be different from all the word sequences seenduring
training. Traditional but very successful approaches based on n-grams
obtain generalizationby concatenating very short overlapping sequences
seen in the training set. We propose to fight thecurse of dimensionality
bylearning a distributed representation for wordswhich allows eachtraining
sentence to inform the model about an exponential number of semantically
neighboringsentences.  The model learns simultaneously (1) a distributed
representation for each word alongwith (2) the probability function for
word sequences, expressed in terms of these representations.Generalization
is obtained because a sequence of words that has never been seen before gets
highprobability if it is made of words that are similar (in the sense of having
a nearby representation) towords forming an already seen sentence. Training
such large models (with millions of parameters)within a reasonable time is
itself a significant challenge.  We report on experiments using neuralnetworks
for the probability function, showing on two  text corpora that the proposed
approachsignificantly improves on state-of-the-art n-gram models, and that
the proposed approach allows totake advantage of longer contexts.
^
@https://jmlr.org/papers/volume3/bengio03a/bengio03a.pdf
#topic:neural network
#author:Ashish Vaswani
#author:Noam Shazeer
#author:Niki Parmar
#author:Jakob Uszkoreit
#author:Llion Jones
#author:Aidan N. Gomez
#author:Łukasz Kaiser
#author:Illia Polosukhin
#medium:paper
#language:english
Attention Is All You Need
The dominant sequence transduction models are based on complex recurrent
orconvolutional neural networks that include an encoder and a decoder.
The bestperforming models also connect the encoder and decoder through
an attentionmechanism.  We propose a new simple network architecture, the
Transformer,based solely on attention mechanisms, dispensing with recurrence
and convolutionsentirely.  Experiments on two machine translation tasks show
these models tobe superior in quality while being more parallelizable and
requiring significantlyless time to train.  Our model achieves 28.4 BLEU on the
WMT 2014 English-to-German translation task, improving over the existing best
results, includingensembles, by over 2 BLEU. On the WMT 2014 English-to-French
translation task,our model establishes a new single-model state-of-the-art
BLEU score of 41.8 aftertraining for 3.5 days on eight GPUs, a small fraction
of the training costs of thebest models from the literature. We show that
the Transformer generalizes well toother tasks by applying it successfully
to English constituency parsing both withlarge and limited training data.
^
@https://arxiv.org/pdf/1706.03762.pdf
#topic:neural network
#author:Bryan McCann
#author:Nitish Shirish Keskar
#author:Caiming Xiong
#author:Richard Socher
#medium:paper
#language:english
The Natural Language Decathlon:Multitask Learning as Question Answering
Deep learning has improved performance on many natural language processing(NLP)
tasks individually. However, general NLP models cannot emerge within aparadigm
that focuses on the particularities of a single metric, dataset, and task.We
introduce the Natural Language Decathlon (decaNLP), a challenge that spansten
tasks:  question answering, machine translation, summarization, natural
lan-guage inference, sentiment analysis, semantic role labeling, relation
extraction,goal-oriented dialogue, semantic parsing, and commonsense pronoun
resolution.We cast all tasks as question answering over a context. Furthermore,
we present anew multitask question answering network (MQAN) that jointly learns
all tasks indecaNLP without any task-specific modules or parameters. MQAN
shows improve-ments in transfer learning for machine translation and named
entity recognition,domain adaptation for sentiment analysis and natural
language inference,  andzero-shot capabilities for text classification.
We demonstrate that the MQAN’smulti-pointer-generator decoder is key to
this success and that performance furtherimproves with an anti-curriculum
training strategy. Though designed for decaNLP,MQAN also achieves state
of the art results on the WikiSQL semantic parsing taskin the single-task
setting. We also release code for procuring and processing data,training
and evaluating models, and reproducing all experiments for decaNLP.
^
@https://arxiv.org/pdf/1806.08730.pdf
#topic:neural network
#author:Ilya Sutskever
#author:Rafal Jozefowicz
#author:Karol Gregor
#author:Danilo Rezende
#author:Tim Lillicrap
#author:Oriol Vinyals
#medium:paper
#language:english
Towards Principled Unsupervised Learning
General unsupervised learning is a long-standing conceptual problem in
machinelearning.  Supervised learning is successful because it can be solved by
the mini-mization of the training error cost function.  Unsupervised learning
is not as suc-cessful,  because the unsupervised objective may be unrelated
to the supervisedtask of interest. For an example, density modelling and
reconstruction have oftenbeen used for unsupervised learning, but they did not
produced the sought-afterperformance gains, because they have no knowledge of
the supervised tasks.In this paper, we present an unsupervised cost function
which we name the Out-put Distribution Matching (ODM) cost, which measures
a divergence between thedistribution of predictions and distributions of
labels. The ODM cost is appealingbecause it is consistent with the supervised
cost in the following sense: a perfectsupervised classifier is also perfect
according to the ODM cost.   Therefore,  byaggressively optimizing the ODM
cost, we are almost guaranteed to improve oursupervised performance whenever
the space of possible predictions is exponen-tially large.We demonstrate
that the ODM cost works well on number of small and semi-artificial datasets
using no (or almost no) labelled training cases. Finally, we showthat the
ODM cost can be used for one-shot domain adaptation, which allows themodel
to classify inputs that differ from the input distribution in significant
wayswithout the need for prior exposure to the new domain.
^
@https://arxiv.org/pdf/1511.06440.pdf
#topic:support vector machine
#topic:machine learning
#author:Alexandre Kowalczyk
#language:english
#medium:book
Support Vector Machines
Support Vector Machines (SVMs) are some of the most performant off-the-shelf,
supervised machine-learning algorithms. In Support Vector Machines Succinctly,
author Alexandre Kowalczyk guides readers through the building blocks of SVMs,
from basic concepts to crucial problem-solving algorithms. He also includes
numerous code examples and a lengthy bibliography for further study. By
the end of the book, SVMs should be an important tool in the reader’s
machine-learning toolbox.
^
@http://ebooks.syncfusion.com/downloads/support_vector_machines_succinctly/support_vector_machines_succinctly.pdf
#topic:machine learning
#topic:id3
#author:Jerzy W. Grzymala-Busse
#language:english
#medium:paper
Selected Algorithms of Machine Learning from Examples
This paper presents and compares two algorithms of machine learning
from examples, ID3 and AQ, and one recent algorithm from the same class,
called LEM2.  All three algorithms are illustrated using the same example.
Production rules induced by these algorithms from the well-known Small Soybean
Database are presented. Finally, some advantages and disadvantages of these
algorithms are shown.
^
@https://people.eecs.ku.edu/~jerzygb/j24-sel.pdf
#topic:k nearest neighbor
#topic:regression
#author:N. S. Altman
#language:english
#medium:paper
An Introduction to Kernel and Nearest Neighbor Nonparametric Regression
Nonparametric regression is a set of techniques for estimating a regression
curve without making strong assumptions about the shape of the true regression
function. These techniques are therefore useful for building and checking
parametric models, as well as for data description. Kernel and nearest neighbor
regression estimators are local versions of univariate location estimators,
and so they can readily be introduced to beginning students, and consulting
clients who are familiar with such summaries as the sample mean and median.
^
@https://ecommons.cornell.edu/bitstream/1813/31637/1/BU-1065-MA.pdf