Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
972
questions
0
votes
1
answer
43
views
Any-goal bidirectional A* pathfinding reference
I want to solve the problem of finding a shortest path on a directed weighted graph from a certain node to any of a specified set of destination nodes (preferably the closest one, but that's not that ...
- 121
1
vote
0
answers
49
views
What's the fastest algorithm for polynomial interpolation in finite field with prime order at points 1, 2, 3, ..., n?
Suppose we have finite field $\mathbb{F}_p$ with prime order $p$. Can we find polynomial in $\mathbb{F}_p[x]$ having given values $a_1, a_2, ... a_n$ at $x=1, 2, ..., n$ in less than $O(n^2)$ ...
- 255
2
votes
1
answer
92
views
Cellular automata on the Eisenstein integers?
Is there any cellular automaton on the Eisenstein integers? By this I mean that the triangles formed by the Eisenstein integers are considered as cells and each triangle has three neighbours plus ...
- 123
0
votes
0
answers
16
views
Solutions for "Operating Systems: Principles and Practice" by Anderson, Dahlin?
I'm self-teaching myself operating systems using the textbook "Operating Systems: Principles and Practice" by Anderson and Dahlin. I am solving the exercises but it would be really helpful ...
- 1
1
vote
0
answers
19
views
Reference for the formal definition of sigma protocol
I'm looking for a book that contains the formal definition of sigma protocol (something like: A sigma protocol for a relation $R$ and a challenge space $C$ is... that satisfies the properties of ...
- 11
3
votes
1
answer
202
views
Shannon's result that some Boolean functions require exponential circuits
In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see [1] and many texts on computational complexity. This result has ...
- 8,178
1
vote
0
answers
49
views
First piece of code in scientific papers
What is the first/oldest piece of source code shown in an scientific paper or journal? I am looking for source code of assembly or a high level programming language which was real (implemented) and ...
- 111
1
vote
0
answers
100
views
A total order of rectangles related to containment
Suppose you have a set of rectangles $R_1,\dots,R_n$ in the plane, each described by an upper left point $p_1 \in \mathbb R^2$ and a lower right point $p_2 \in \mathbb R^2$, all pairwise different.
...
- 111
3
votes
0
answers
20
views
Is there a comprehensive list of complexity theoretic reductions from and to prime number factorization?
I am interested in the complexity theoretic equivalences of prime number factorization.
My interest stems from prime number factorization being one of the few candidates for NPI.
I am especially ...
- 131
1
vote
0
answers
30
views
Shortest path with vertex capacity
I have an undirected graph where each edge $e=\{u,v\}$ has a positive weight $w_{uv}$ and each vertex $v$ has a positive capacity $c_v$. There are two special vertices: a source vertex $s$ and a ...
- 1,016
2
votes
0
answers
33
views
Quantum Boolean SAT algorithm?
Is there a quantum SAT algorithm, a quantum analogue of the DPLL or CDCL algorithms?
Note: I'm not looking for the quantum analogue of the Boolean satisfiability problem (though that would be ...
- 145
0
votes
0
answers
17
views
Big O notation References and Resources
I am new to time complexity, and Big O notation. I have this question pertaining to this code in Python 3.X:
...
- 101
1
vote
0
answers
10
views
Circuit class: constant depth, poly-size, bounded fan-in
I'm looking for the name of a certain circuit complexity class. It captures, to me, the idea of "shallow physically feasible circuits". I'm looking for the class of problems with:
Constant ...
- 816
1
vote
1
answer
38
views
What does type theory as a theory of inductive definitions mean?
Unfortunately copy/paste doesn't work for this paper Inductive Definitions and Type Theory, but here is a snippet.
The paper begins by stating:
The first sentence of the second paragraph says type ...
- 1,871
3
votes
1
answer
40
views
What is a program analysis technique for tracing assignments (mutations)?
I am looking to write a program analysis for Java programs that tracks assignments and is able to discern:
whether a class field (static or not) is read and where the read originated
whether a class ...
- 45
0
votes
0
answers
27
views
Optimal text/code formatting with alignment constraints
Formatting code or things like TeX have some interesting problems. For instance in auto-formatting code you want to use up as much line space as possible but not go over a certain limit if possible. ...
- 3,738
0
votes
0
answers
12
views
Textbook request for Linear Cellular Automata, if possible with an abstract algebraic approach
I am a final semester pure math undergrad, and I became interested in Linear Cellular Automatas.I became interested after reading Klaus Sutner's article. In the article, a little abstract algebra is ...
- 109
0
votes
0
answers
25
views
Good sources that treat "sliding window" whiteboarding-style problems?
This is a reference request for algorithms textbooks that address the common "sliding window" problems that come up in whiteboarding. If not textbooks per se, I'm looking for a more ...
- 115
2
votes
0
answers
33
views
How to think in automata theory or some recommendations of resources related to this?
Recently, I find that automata theory is very useful in computer science, it is used in many fields, such as computer network, digital design, computer architecture and operating system, even we can ...
- 21
2
votes
0
answers
39
views
Fastest randomized algorithm for trace distance
Assume to have query access to the values $p(x)$, and $q(x)$ of two probability distributions over n elements $x \in X$, $|X|=n$.
That is, for a given $x\in X$ we pay constant time $O(1)$ to perform a ...
- 227
1
vote
1
answer
94
views
Request for Good Encyclopedic works of computer science
I attempt to find a few general encyclopedic works on computer science such that looking up relevant terminologies is easily available ready to hand. I'm not familiar with the whole picture of ...
- 19
6
votes
1
answer
368
views
Fast and compact data structure for dynamic graphs
A graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ may be represented in central memory as follows:
an associative array (hash table) $V$ gives for any $v\in \mathcal{V}$ the list of its neighbors $V[v]$...
- 603
0
votes
2
answers
24
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
2
votes
0
answers
24
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 ...
- 197
1
vote
0
answers
35
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 ...
- 3,738
1
vote
1
answer
43
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 ...
- 113
0
votes
0
answers
108
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
3
votes
1
answer
62
views
What is the analysis that a heap's optimal branching factor is between 2 and 5?
I'm reading the book Advanced Algorithms and Data Structures. It makes the claim that the optimal branching factor $D$ for a heap satisfies $2 \le D \le 5$, and that it is most likely $3$ or $4$ ...
- 131
1
vote
3
answers
100
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 ...
- 121
1
vote
1
answer
41
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 ...
- 113
1
vote
1
answer
30
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.
...
- 339
0
votes
0
answers
15
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 ...
- 3,474
3
votes
1
answer
60
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 ...
- 131
2
votes
2
answers
107
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,474
3
votes
1
answer
79
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 ...
- 279
3
votes
0
answers
31
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) ...
- 31
2
votes
0
answers
184
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.
...
- 21
2
votes
1
answer
79
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 ...
- 173
2
votes
1
answer
50
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 ...
- 251
2
votes
0
answers
39
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 ...
- 133
1
vote
1
answer
38
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, ...
- 386
2
votes
1
answer
48
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-...
- 375
2
votes
1
answer
49
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 ...
- 131
0
votes
1
answer
76
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) ...
- 103
2
votes
1
answer
171
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 ...
- 6,978
1
vote
4
answers
208
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 ...
- 127
4
votes
2
answers
124
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 $...
Milin
4
votes
1
answer
36
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
1
answer
25
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 ...
- 10.8k
4
votes
2
answers
227
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 ...
- 115