Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
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 ...
user avatar
  • 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)$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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]$...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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) ...
user avatar
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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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-...
user avatar
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 ...
user avatar
  • 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) ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 115

1
2 3 4 5
20