"A one instruction set computer (OISC), sometimes called an ultimate reduced instruction set computer (URISC), is an abstract machine that uses only one instruction – obviating the need for a machine language opcode.[1][2][3] With a judicious choice for the single instruction and given infinite resources, an OISC is capable of being a universal computer in the same manner as traditional computers that have multiple instructions.[2]:55 OISCs have been recommended as aids in teaching computer architecture[1]:327[2]:2 and have been used as computational models in structural computing research.[3]"

"The game of chess as always been viewed as an iconic representation of intellectual prowess. Since the very beginning of computer science, the challenge of being able to program a computer capable of playing chess and beating humans has been alive and used both as a mark to measure hardware/software progresses and as an ongoing programming challenge leading to numerous discoveries. In the early days of computer science it was a topic for specialists. But as computers were democratized, and the strength of chess engines began to increase, chess players started to appropriate to themselves these new tools. We show how these interactions between the world of chess and information technologies have been herald of broader social impacts of information technologies. The game of chess, and more broadly the world of chess (chess players, literature, computer softwares and websites dedicated to chess, etc.), turns out to be a surprisingly and particularly sharp indicator of the changes induced in our everyday life by the information technologies. Moreover, in the same way that chess is a modelization of war that captures the raw features of strategic thinking, chess world can be seen as small society making the study of the information technologies impact easier to analyze and to grasp."

"Dana Scott used the partial order among partial functions for his mathematical model of recursively defined functions. He interpreted the partial order as one of information content. In this paper we elaborate on Scott's suggestion of regarding computation as a process of information maximization by applying it to the solution of constraint satisfaction problems. Here the method of constraint propagation can be interpreted as decreasing uncertainty about the solution -- that is, as gain in information about the solution. As illustrative example we choose numerical constraint satisfaction problems to be solved by interval constraints. To facilitate this approach to constraint solving we formulate constraint satisfaction problems as formulas in predicate logic. This necessitates extending the usual semantics for predicate logic so that meaning is assigned not only to sentences but also to formulas with free variables."

"This short paper introduces a new way by which to design production system rules. An indirect encoding scheme is presented which views such rules as protein complexes produced by the temporal behaviour of an artificial genetic regulatory network. This initial study begins by using a simple Boolean regulatory network to produce traditional ternary-encoded rules before moving to a fuzzy variant to produce real-valued rules. Competitive performance is shown with related genetic regulatory networks and rule-based systems on benchmark problems."

"Good database design is crucial to obtain a sound, consistent database, and - in turn - good database design methodologies are the best way to achieve the right design. These methodologies are taught to most Computer Science undergraduates, as part of any Introduction to Database class. They can be considered part of the "canon", and indeed, the overall approach to database design has been unchanged for years. Moreover, none of the major database research assessments identify database design as a strategic research direction.

Should we conclude that database design is a solved problem?

Our thesis is that database design remains a critical unsolved problem. Hence, it should be the subject of more research. Our starting point is the observation that traditional database design is not used in practice - and if it were used it would result in designs that are not well adapted to current environments. In short, database design has failed to keep up with the times. In this paper, we put forth arguments to support our viewpoint, analyze the root causes of this situation and suggest some avenues of research."

"A short survey is provided about our recent explorations of the young topic of noise-based logic. After outlining the motivation behind noise-based computation schemes, we present a short summary of our ongoing efforts in the introduction, development and design of several noise-based deterministic multivalued logic schemes and elements. In particular, we describe classical, instantaneous, continuum, spike and random-telegraph-signal based schemes with applications such as circuits that emulate the brain's functioning and string verification via a slow communication channel."

"Developing large-scale distributed applications can be a daunting task. object-based environments have attempted to alleviate problems by providing distributed objects that look like local objects. We advocate that this approach has actually only made matters worse, as the developer needs to be aware of many intricate internal details in order to adequately handle partial failures. The result is an increase of application complexity. We present an alternative in which distribution transparency is lessened in favor of clearer semantics. In particular, we argue that a developer should always be offered the unambiguous semantics of local objects, and that distribution comes from copying those objects to where they are needed. We claim that it is often sufficient to provide only small, immutable objects, along with facilities to group objects into clusters."

"We consider the problem of computing a response curve for binary cellular automata -- that is, the curve describing the dependence of the density of ones after many iterations of the rule on the initial density of ones. We demonstrate how this problem could be approached using rule 130 as an example. For this rule, preimage sets of finite strings exhibit recognizable patterns, and it is therefore possible to compute both cardinalities of preimages of certain finite strings and probabilities of occurrence of these strings in a configuration obtained by iterating a random initial configuration $n$ times. Response curves can be rigorously calculated in both one- and two-dimensional versions of CA rule 130. We also discuss a special case of totally disordered initial configurations, that is, random configurations where the density of ones and zeros are equal to 1/2."

"We present a form of algebraic reasoning for computational objects which are expressed as graphs. Edges describe the flow of data between primitive operations which are represented by vertices. These graphs have an interface made of half-edges (edges which are drawn with an unconnected end) and enjoy rich compositional principles by connecting graphs along these half-edges. In particular, this allows equations and rewrite rules to be specified between graphs. Particular computational models can then be encoded as an axiomatic set of such rules. Further rules can be derived graphically and rewriting can be used to simulate the dynamics of a computational system, e.g. evaluating a program on an input. Examples of models which can be formalised in this way include traditional electronic circuits as well as recent categorical accounts of quantum information."

"…Even though we cannot present all the algorithms in full detail, we can at least show “in princi- ple”, how a whole variety of important and practical algorithms come out from our refinement process. These include above all the (DLG) algorithm of Doligez, Leroy and Gonthier [9] – which sometimes is considered the culmination of concurrent collector development [1] – and its descendants."

"The rigorous theoretical analyses of algorithms for #SAT have been proposed in the literature. As we know, previous algorithms for solving #SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving #SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i.e. the number of clauses. In this paper, we present algorithms for solving #2-SAT and #3-SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds O(1.1892m) for #2-SAT and O(1.4142m) for #3-SAT, where m is the number of clauses."

"Schoening presents a simple randomized algorithm for (d,k)-CSP problems with running time (d(k-1)/k)^n poly(n). Here, d is the number of colors, k is the size of the constraints, and n is the number of variables. A derandomized version of this, given by Dantsin et al., achieves a running time of (dk/(k+1))^n poly(n), inferior to Schoening's. We come up with a simple modification of the deterministic algorithm, achieving a running time of (d(k-1)/k * k^d/(k^d-1))^n \poly(n). Though not completely eleminating the gap, this comes very close to the randomized bound for all but very small values of d. Our main idea is to define a graph structure on the set of d colors to speed up local search."

"We describe a variation of a technique by Chiba and Nishizeki [3], leading to a data structure for graph algorithmic problems, called the h-graph data structure. It supports operations of insertion and removal of vertices, as well as insertion and removal of edges. Although the data structure can be used for general purpose, it is particularly suitable for applications in dynamic graph algorithms."

"Although care needs to be taken in the implementation of normal random number generators like fastnorm, and the end-user should be aware of the small but unavoidable defects discussed in §§5.6-5.7, these generators have such a performance advantage over more conventional generators that they can not be ignored in applications where the speed of generation of pseudo- random numbers is critical."

"… The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods."

"Every algorithm which can be executed on a computer can at least in principle be realized in hardware, i.e. by a discrete physical system. The problem is that up to now there is no programming language by which physical systems can constructively be described. Such tool, however, is essential for the compact description and automatic production of complex systems. This paper introduces a programming language, called Akton-Algebra, which provides the foundation for the complete description of discrete physical systems.…"

"Computational complexity has in the past adapted well to new computation models from the PRAM to biological and quantum computers. But we are seeing new computing paradigms in multicore and cloud computing and theory seems late to the party. There was a nice SODA paper on MapReduce, the basic cloud computing operation, but for the most part theorists haven't tackled the cloud computing model and only a few have looked at multicore. Theory can say much about new computational methods, both in how we can take advantage of them and what they can't do, but only if we make the effort to develop the proper models to capture these new approaches."

"For example, the manual for the Franklin Ace 100 begins with about 40 pages of computer basics (What are they? What can they do? etc). And then, on page 40, two thirds of the way down the page, there is a chapter heading called “The Ancestral Territorial Imperatives of the Trumpeter Swan.” Here’s how the chapter begins:…"

"The primary exploratory target of this research project is to find a strategy hopefully better than any other known for evolving, through genetic algorithms, cellular automata rules for global synchronization tasks. By better we mean that synchronization rules need to emerge more consistently, faster and with higher probability compared to previous studies under the same initial conditions."

"Our conference system forces researchers to focus too heavily on quick, technical, and safe papers instead of considering broader and newer ideas. Meanwhile, we have devoted much of our time and money to conferences where we can present our research that we can rarely attend conferences and workshops to work and socialize with our colleagues.

Computer science has grown to become a mature field where no major university can survive without a strong CS department. It is time for computer science to grow up and publish in a way that represents the major discipline it has become."

"In this paper, we significantly improve a previous result by the same author showing the existence of a weakly universal cellular automaton with five states living in the hyperbolic 3D-space. Here, we get such a cellular automaton with three states only."

interesting; need to scare up the PDFs

"About the Book: This is an open set of lecture notes on metaheuristics algorithms, intended for undergraduate students, practitioners, programmers, and other non-experts. It was developed as a series of lecture notes for an undergraduate course I taught at GMU. The chapters are designed to be printable separately if necessary. As it's lecture notes, the topics are short and light on examples and theory. It's best when complementing other texts. With time, I might remedy this."

"Our conference systems forces researchers to focus too heavily on quick, technical
and safe papers instead of considering broader and newer ideas. Meanwhile we
have focused much of our time and money on conferences where we can present
our research that we can rarely attend conferences and workshops to work and
socialize with our colleagues."

"This paper seeks to explode the myth that Turing Machines (TM) are the universal model for all computation."

Now would somebody please undermine the computational complexity greed people have about algorithms? I find it deeply embarrassing to be told by somebody who "knows too much" that they will never even try an algorithm that is worse than polynomial, under any circumstances or for any problem. Like the idiots who have been taught some Gaussian statistics and say they would never gamble in a Casino because they KNOW they would ALWAYS lose.

A technical conference schedule from my Dad's papers.

"I recently got back reviews of a paper in which I used automatic differentiation. Therein, a reviewer clearly thought I was using finite difference, or “numerical” differentiation. This has led me to wondering: Why don’t machine learning people use automatic differentiation more? Why don’t they use it…constantly? Before recklessly speculating on the answer, let me briefly review what automatic differentiation (henceforth “autodiff”) is. Specifically, I will be talking about reverse-mode autodiff."

"There is increasing concern about the disappearance of technical knowledge from the public domain, both on grounds that is presents a security danger and because it is economically valuable "Intellectual Property". I argue that this development is not anomalous at all but a great historic trend tied to our transition to the information age. We are in the process of losing a human right that all of us thought we had but actually didn't--the right to learn things we can and better ourselves economically from what we learn. Increasingly, figuring things our for yourself will become theft and terrorism. Increasingly, reason itself will become a crime."

"When the editors raise prices we don't like it. But when the lower them or agree to put things online, thats a bribe. They can't win. Well- if they just put EVERYTHING online and cheap then we will stop complaining and threatening. If they can't find a way to do that and make a profit they should not be in the business."

Maarten's challenge to the Nudge language

Applying an EDA to linear GP. As it happens, Push is a (roughly) linear GP language.

"When the basic problem is your ignorance, clever strategies for bypassing your ignorance lead to shooting yourself in the foot"

Loving the external iterators -- at a philosophical level. Not sure about their propriety otherwise.

Subjective randomness.

Want to understand this sufficiently to glean something for automatic quantum computer programming with GP. I sense there's something in there....

I'll be there

Probably won't be able to attend.

Layers can overlap. Via Doug Knox at the Newberry Library.

Musing about the relative focus of self-attention in different academic fields

Why is what we teach in graduate school so often reduced to <i>what it's "supposed to be" like in the University</i>?