Digital Revolution

This post is a guess. Ribbon concordance on 3-manifolds can be separated into partial order systems associated with each element of the fundamental group of the 3-manifold. For each element of the fundamental group, a partial order system can be associated. The reason behind the guess is that if the knotty part can shrink to very small and the remaining part is largely isotopic to a representative element of the fundamental group, then it's likely that the structure obtained in 3-sphere case is applicable to each element of the fundamental group. It's a interesting research topic.

Ribbon concordance has been proved to be a partial order system on knots and forms a complexity hierarchy. However, in this case, the knots are assumed to be in the three dimensional sphere. A natural question to ask is whether similar relations may be defined in 3-manifolds other than the three sphere. Since in general the fundamental group of 3-manifolds does not vanish, significant complexity different from the case of the three sphere is expected. It's a interesting research topic.

Intermediate Value Theorem is a basic theorem in calculus. Usually, there is nothing more to say about the theorem. But with the rigorous bounds obtained in numerical algorithms that we discussed before, much can be done through the basic theorem. In mathematical research, existence is often very hard to establish. Part of the reason is most existences afford no constructive description. Here we are left with indirect methods like the Intermediate Value Theorem. Traditionally, numerical algorithms offered insights but were not applicable in rigorous proof. With rigorous bounds proven, numerical algorithms can be utilized to provide rigorous estimates of simulated values. Together with the likes of Intermediate Value Theorem, existence of objects can be established rigorously. Providing rigorous bounds for numerical algorithms is a game changer.

Much of the emphasis in teaching algorithms is placed on time complexity analysis with occasional mentioning of space complexity, accuracy, and parallelism, etc. This optimization view of algorithms is valuable, but a wider view is possible, that of algorithms as a means of exploration and discovery. A classic example is the proof of the four color theorem. It shows how computers can extend the frontiers of human knowledge. Although in some cases, human understanding is limited, and the soundness of computer generated results is in doubt, computers still provide a great deal of value for research. We no longer just talk about how fast a algorithm operates, but also what new stuff it can find out. In a certain technical sense, computer exploration is crucial, because there is no Turing machine that can predict how a arbitrary computer program will end. Exploration is a tool to find out what a algorithm actually performs. Moreover, research often deals with uncertain postulates, rather t...

Stephen Wolfram's Principle of Computational Equivalence is a landmark in complexity study. Even though it's wrong at large, it did show how seemingly simple programs can exhibit extremely complex behavior. The fallacy results from the desire to generalize without proper scrutiny. For example, it claims that complexities in different dimensions are similar. But, topology and geometry make very striking distinctions between dimensions. In 2D, we have Poincare-Bendixson theorem. In 3D, we have knots. All are specific to dimensionality. Unless we are going to say these constructs do not reflect complexity, we are forced to accept that complexity is much more than computation and things like geometry should be a subject of study. The field is still very young. A theory to rank knots is a good beginning. There is good reason to speculate that final results will involve vast new areas like statistics, and will provide insights into deep philosophical questions like rationalism vers...

Most people argue about symbolic computation versus numerical computation. There are plenty of advantages and disadvantages in each camp, which suggests the way out may be to forge a symbolic-numerical alliance that would provide the rigor of symbolic computation and the performance of numerical computation in a single package. It's not as trivial as simply adding two apps together. The underlying programming language has to be dramatically redesigned to express the alliance in a elegant and powerful way. So far, there is a trend for symbolic packages like Wolfram Language to adopt more numerics, and for numerical packages like Matlab to adopt more symbolics, but neither is a satisfactory alliance that fully integrates the two. The advantages of such a alliance are easy to see. Artificial intelligence often employs both worlds, like symbolics for knowledge representation, and numerics for data fitting, to say the obvious. A symbolic-numerical alliance would make artificial intellig...

Simulation algorithms for dynamical systems rely on the shadowing lemma to establish the proximity of a pseudo-orbit and a true orbit. The power of the shadowing lemma is tremendous in that it takes all sorts of errors in a computer simulation into account. Numerical analysis, on the other hand, is not that fortunate. There is no systematic error analysis that encompasses all possibilities. Finite element method's error equation, for example, only deals with discretization error, but ignores computational round-off error, and can not provide a good estimate of the proximity of the real solution based on mesh properties. Here we briefly discuss the error estimate in a numerical simulation of contraction mapping. The fixed point and iterated epsilon-pseudo-orbit can be estimated to be within epsilon/(1-C) plus a arbitrarily small number, where C is the contraction constant. That is, if the contraction constant is close to 1, much smaller round-off and general computational errors ar...

Knuth isn't a huge fan of parallel computing. He acknowledged several fields where parallel computing speeds things up, like computer graphics, but remains unsatisfied with its daily-life impact. On the other hand, Tim Mattson, a proponent of OpenMP, embraces parallel computing for its power saving capability. Here, a computational complexity perspective is provided to reconcile various contentious issues regarding parallel computing, like its longevity. Computational complexity measures the growth of logical depth with respect to growing inputs. If the number of parallel machines is of O(1), it can be shown that parallel speedup doesn't change the order of computational complexity, but only affects the constant factor. From traditional point of view, the order of computational complexity is of prime importance, for the presumption that data sets may grow astronomically, while the constant factor is of little interest. However, we wish to emphasize that in many practical and ...

There are numerous collections of algorithms on the Internet. Places like AlgoWiki provide valuable service. Yet we feel that the Wiki model isn't the best way to present algorithms. Here's why. Wiki is designed not to credit authors. This is a huge dis-incentive, because very few people like to publish and perish. Rather, we believe that the library/arXiv model is superior in that it properly rewards outstanding authors with fame. There are various disadvantages using Wiki, like lack of personal style, lack of comprehensiveness due to low participation, and awkward search. These problems can be solved if the library model is implemented well. Details will be given once spectrum-dev is up and running.

Here we define a robust network to be a connected network that stays connected after a arbitrary link is removed. The minimal robust network connecting a set of nodes is a Hamiltonian cycle. Further, a robust network is called reduced if it can not stay robust after any link is removed. A robust network may contain multiple reduced robust networks. And reduced robust networks may be obtained by removing links from robust networks. It's a open problem to computationally characterize robust networks, and reduced robust networks. Not every robust network can be reduced to the minimal robust network because not every robust network contains a Hamiltonian cycle. It's another open problem to computationally find reduced robust networks contained in arbitrary robust networks.

Modern artificial intelligence rely on data fitting. For some, the approach seems shallow, for the result is a description that summarizes data, rather than a mechanism that generates them. The success of modern artificial intelligence requires a justification of data fitting in order to explain how a seemingly shallow method turns out to be highly efficient. One doesn't want to invoke the analogy of catching a baseball. Even if a baseball player has no idea of classical mechanics, the ball can be traced by following its trajectory. Data fitting is deeper than this. First it must be emphasized that data fitting is a essential tool even for hard sciences. Planck had no idea how to generate light quanta, but based on curve fitting derived with the quantum hypothesis, he successfully launched the quantum revolution. The beauty of his approach is the small number of parameters that can explain a host of radiation patterns. Although data fitting can not explain fundamental mechanisms, i...

In sciences, computable numbers and sequences form a important part of study. From ancient Fibonacci numbers to modern quantum series, computable numbers and sequences provide a crucial tool to understand our world. However, scientific measurements are often inexact. We often see deviations from a computational theory being classified as errors. While random errors may occur, there is also the possibility that the phenomena at hand may be just almost computable, rather than computable. Thus, almost computable numbers and sequences may reveal the true structure of nature beyond computation. There are many conjectures whether a object is computable or not, but there is little understanding whether a incomputable object is a little incomputable or wildly incomputable. As a first step of quantification, almost computable numbers and sequences may be introduced as objects that differ from computable objects by a set of frequency zero. Almost computable numbers and sequences give a first...

Research publications are dominated by the paper model with deep roots in print. Although most publications are available online, the format is still raw digitization of print material. It's almost as if even the most innovative academics reject the idea that digital revolution could bring positive changes to research quality. Take science publications for example. During active research, researchers often employ large data sets for study. At the end of the process, only tiny bits of selected statistics appear in published paper. Since data generally can not be reduced to statistics due to Shannon entropy, the conclusion based on statistics may be dubious. One hears lies, damn lies, and statistics not for trivial reasons. Often, there is no way for a reader to verify a published paper without original data. Yet, academics cling to the traditional paper model. Digital technology should be employed to improve verifiability of research publications! Programs and data may be bundled to...