Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
965
questions
-1
votes
0answers
24 views
Books for a first year college student in computer science [closed]
Books that involve maths, computer science, logic, programming or anything that would be helpful for a student like me
0
votes
0answers
13 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 ...
2
votes
0answers
31 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 ...
2
votes
0answers
35 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 ...
0
votes
0answers
16 views
Object Visibility Graphs
I have gone through this defination
A graph G = (V, E) is called an object visibility graph if there is a set of non-
intersecting objects so that there is a one-to-one correspondence between the sets ...
2
votes
1answer
78 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 ...
6
votes
1answer
290 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]$...
0
votes
2answers
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 ...
2
votes
0answers
23 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
26 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
36 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
101 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.
...
2
votes
1answer
52 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$ ...
1
vote
3answers
98 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
32 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
26 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
1answer
57 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
98 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
180 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
63 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
35 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
29 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
46 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
46 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
152 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
148 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
121 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
23 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
44 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
44 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
37 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
82 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
65 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
18 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
16 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 ...
