# Questions tagged [reference-request]

Questions requesting papers in the literature on specific, narrow issues.

972 questions
Filter by
Sorted by
Tagged with
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
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
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 ...
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 vote
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
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
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
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
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
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
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
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: ...
1 vote
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
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
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 ...
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
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 ...
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
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
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
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
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]$...
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 ...
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
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
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
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. ...
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
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
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
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. ...
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
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
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
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
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) ...
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. ...
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
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
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 ...
1 vote
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
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
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
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) ...
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
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 ...
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 \$...
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
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