Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
961
questions
0
votes
2answers
22 views
Searching for sorting algorithm taking into account all possible solution of similar numbers
I need a reference for sorting algorithm where all possible orders are considered.
example:
if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
-1
votes
0answers
18 views
Control Flow Graph - How to represent returns in code
Consider the following program
int someCode1(int x){
if (x < 0)
return 0;
else
return x;
Last Statement;}
Last statement could be either "printf(...
1
vote
0answers
12 views
Are there any references for this theorem of Lercher?
Let $\Delta = \lambda x.(x)x$ and consider $\Omega = (\Delta)\Delta$. Then $\Omega$ is exactly the only $\lambda$-term of the form $(\lambda x.t)v$ such that $(\lambda x.t)v=t\{v\ /\ x\}$.
Does ...
1
vote
0answers
19 views
Modern standard texts on distributed systems
I'm starting a job soon that involves a large number of disciplines interacting at once. I'm knowledgeable in most of these areas; at least enough that when I don't know something I know how to look ...
1
vote
1answer
35 views
Online Taylor series calculator
When I compute the the eigenvalues of the matrix $$\begin{bmatrix}x^3& 2 + x^3& 3 - 2 x^3\\ 2 + x^3& 4 - 5 x^3& 5 + 3 x^3\\ 3 - 2 x^3& 5 + 3 x^3& x^3\end{bmatrix}$$ using ...
0
votes
0answers
99 views
Multivariate piecewise linear interpolation
I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm.
...
1
vote
1answer
36 views
What is the anayslsis that a heap's optimal branching factor is 2 <= factor <=5?
I'm reading the book Advanced Algorithms and Data Structures and it makes the claim that the optimal branching factor for a heap is 2 <= D <= 5 and that it is ...
1
vote
3answers
94 views
Do modern computers prevent instructions being executed by audio? If so, how?
Most know that early phones and modems, and still, fax machines, sent information through the use of tones. This got me thinking - could audio be a viable vector for executing instructions by a bad ...
1
vote
1answer
30 views
Arithmetic hierarchy via oracles
My professor gave an introduction to the arithmetic hierarchy via Turing reductions, stating that, for instance, $\Sigma_2 = \text{r.e.}^\text{r.e.}$ (namely an $\text{r.e.}$ pseudocode with access to ...
1
vote
1answer
25 views
Heuristics for a variant of the traveling salesman problem
I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset.
...
0
votes
0answers
14 views
Intro to basic automated proof search for theorems in equational theories
I have heard about this topic, and I'm merely looking for a reference that I can read through: I know about formal logic as a proof-checking system, but I haven't yet learned about actual algorithms ...
2
votes
0answers
40 views
List of algorithms that depend on sorting / ranking / argsorting
I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, not for a list of sorting algorithms.
I want to study and illustrate the importance of fast sorting in ...
2
votes
2answers
97 views
Mathematical models of computation that capture more advanced OS and CPU design features
The universal Turing machine is the standard theoretical model of a stored-program computer. While in one sense as general as possible (Turing completeness), it doesn't explicitly contain many of the ...
3
votes
1answer
72 views
Is there a book with 100 reductions?
In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems.
Question:
I was wondering if there exists something like a database or a book with some ...
3
votes
0answers
30 views
Periodic 4D Triangulations
I am looking for references and/or algorithms for generating 4-dimensional periodic triangulations on unit 4 lattices. That is, generating a space filling triangulation of the 4D integer lattice (Z^4) ...
2
votes
0answers
178 views
Produce a Dynkin system from a finite set of finite sets
[Updated question]
A Dynkin System is, provided all sets are finite, a collection of subsets of a universal set closed under complements with the universal set and closed under union of disjoint sets.
...
1
vote
1answer
59 views
what precisely do linear types prevent?
"A theory of type polymorphism in programming" introduced the Hindly-Milner type system whose punchline can be summarized "well-typed terms don’t get stuck". They do this by ...
2
votes
1answer
32 views
Using B+Tree to implement index, when the index-key size and the data-block size are of the same order
I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a ...
2
votes
0answers
35 views
Kolmogorov complexity of probability distributions, with and without time bound
Kolmogorov complexity of a string is the length of the shortest algorithm that generates it. Here I'm focusing instead on randomly distributed strings $x$, with length $n$, with a probability ...
1
vote
1answer
28 views
Counter automata with a bound on the counters?
It is widely known that emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example).
However, ...
2
votes
1answer
44 views
What is this linear optimization problem?
Given a $d$-dimensional vector $v = (v_1,\dots,v_d) \in \Bbb{R}^d$, we define $f(v) = \min_{i\in [d]} \{v_i\}$ to be the smallest coordinate of $v$.
Let $v^1,\dots,v^n \in \Bbb{R}^d_{\ge 0}$ be non-...
2
votes
1answer
47 views
Filling in the image by the brain
The Cones and rods are not evenly or precisely sensitized on the retina by incoming light. Because of this, the image is formed with distortions. But the brain corrects these deformations through a ...
0
votes
1answer
38 views
Definition of static property of object in OOP
Grady Booch in Object-Oriented Analysis and Design with Applications says:
The state of an object encompasses all of the (usually static) properties of the object plus the current (usually dynamic) ...
2
votes
1answer
141 views
Proving FPT is strictly contained in XP
In their book Fundamentals of Parameterized Complexity, Downey and Fellows claim (in chapter 27.1) that $\mathrm{FPT}\subsetneq \mathrm{XP}$, and that this is a "basic result" that follows ...
1
vote
4answers
134 views
A beginner book on algorithms
I am a tenth grader. I currently learnt about sorting algorithms in java in school. I started with the book "Algorithmic Mathematics" so as learn about algorithms mathematically. I know very ...
4
votes
2answers
120 views
Is there a good algorithm to divide two integers without using division directly?
Problem. Given positive integers $a$ and $b$, obtain $\frac{a}{b}$ without using division ($/$) directly, though addition ($+$), subtraction ($-$), multiplication ($\times$) and bit-shifts ($\gg$ and $...
4
votes
1answer
34 views
What is the primary reference for the observation/discussion of how neural networks struggle with ambiguous training datasets?
It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same ...
1
vote
1answer
22 views
Convergence of graph neural networks (GNNs)
I'm new to the area, and we don't have a course on graph neural networks at our university. However, I will still like to know the main theoretical results when considering convergence of graph neural ...
4
votes
2answers
213 views
Why did finite-state controller with datapath win?
I just finished watching the 1986 SICP lectures, and the concepts are rolling around in my head.
My question: why is "finite-state controller with datapath" the implementation of computer ...
0
votes
2answers
44 views
What's the error about the definition of NP?
Many sources (including Wolfram's MathWorld) say that NP problem is defined as a decision problem "verifiable in nondeterministic polynomial time" (check Google to see more sources).
But ...
1
vote
1answer
40 views
How to search all possible combinations for a product?
I'm looking for the name of the problem stated below or, if available, even the algorithm to solve it. This is a hypothetical idea of mine, I don't actually have the necessary data to implement it. ...
2
votes
1answer
37 views
Generalization of Cellular Automata
So in the little I know about formalization of cellular automata, it appears there are 4 major categories of cellular automata:
1-dimensional (cellular automata on the line)
2-dimensional (cellular ...
1
vote
0answers
16 views
Video lectures about Information Theory and Thermodynamics!
I'd like to know if there is any video courses that relate information theory and thermodynamics, e.g. courses cover laws of thermodynamics, Shannon's entropy, Kolomogorov Complexity, Landauer’s ...
0
votes
0answers
23 views
Calculating ring inequalities with fixed precision
Suppose we are given $n$ $M$-bit (the word size of the computer) integers $x_i$, and wish to calculate a linear or nonlinear inequality involving the numbers (an expression made up from the $x_i$, ...
2
votes
1answer
42 views
Existence of good error correcting codes
I recently asked this question and got an answer from Yuval Filmus stating that we can build a solution using error-correcting codes.
More specifically, I'm looking for error correcting codes (for ...
0
votes
0answers
17 views
Edge features in Graph Neural Networks
I would like to know which GNN architectures support edge features, and where can I read about them. If anyone knows where I can search that \ how to distinguish between a GNN that doesn't inherently ...
1
vote
1answer
36 views
Is a register machine built out of automata of some sort?
I am looking at register machines like the Random Access Machine. Wikipedia says:
Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. ...
1
vote
2answers
75 views
Silly question: what counts as a "unit of work" when computing big-Oh time complexity
I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".
It says in the textbook that certain ...
1
vote
1answer
63 views
Solving problems by dynamic programming plus quantization to avoid combinatorial explosion
The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to:
$$ x_{k+1} = f(x_k,u_k) $$
where $k \in \{ 0,\dots,N-1 \} $, ...
0
votes
1answer
17 views
Formal Description Of Data Structure For Infinite Sets Of Reals
The paper I'm working on uses sets as implemented in https://docs.sympy.org/latest/modules/sets.html. A set is stored in a data structure as a sequence of intervals with open or closed bounds, so it ...
0
votes
0answers
15 views
Research on Tree Automata/Tree Transducers for implementing Tree Generators
I would like to write from scratch a tree pattern matching algorithm. Well actually, not just a matching algorithm, and not even a tree transducer, but a sort of tree constructor that takes basically ...
2
votes
1answer
35 views
Uniform convergence for a class of finite dimension
The following theorem is cited in Balcan, M.F., Sandholm, T. and Vitercik, E., 2019. Estimating approximate incentive compatibility which I am currently reading and it is referenced to David Pollard. ...
0
votes
0answers
4 views
Inferring reward function and transition model from optimal policy
Consider an MDP where the transition model and the reward function are unknown.
Consider an optimal policy $\pi^*$ generated from this MDP (say by some oracle who does know the transition model and ...
0
votes
0answers
19 views
Companion volume to Concurrency verification of Willem-Paul de Roever
At the moment I am working hard with the book "Concurrency Verification
Introduction to Compositional and Non-compositional Methods" written by Willem-Paul de Roever et al. In the ...
1
vote
0answers
10 views
Asking for references on errors, testing, system failures etc
I am looking for references that talk about the following subject:
Software programs are in general complex systems. That is, if we decompose them into components and we make sure that each component ...
1
vote
1answer
27 views
Algorithmic information theory with stochastic algorithms?
Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, ...
1
vote
0answers
15 views
Degree of regularity of a Markov chain
A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive.
Is there a known notion of degree of regularity quantified in terms of how soon all ...
1
vote
0answers
28 views
Reliability of information on large social networks like Wikipedia [closed]
I was going through the playlist of an online course on Social Network Analysis offered by the Indian Institute of Technology (Madras), when I came across the claim that "when a lot of people get ...
2
votes
1answer
166 views
What is a self-delimiting program?
I came across the term self-delimiting program, referring to the paper "Laws of information (nongrowth) and aspects of the foundation of probability theory" by Levin, 1974.
Unfortunately ...
2
votes
0answers
18 views
Generalization of finding $L_\infty$ centroid in $R^2$ via rotating and minimizing sum of $L_1$ distances
Given a set of points $x_1, \dots, x_n \in \mathbb{R}^2$, suppose one wants to find:
$\text{argmin}_i \sum\limits_{j=1}^{n} \lVert x_i - x_j\rVert_\infty$
i.e. the point which minimizes the sum of the ...