Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
944
questions
-1
votes
0answers
21 views
Doubt between primary key and foreign key
I have two tables, course and prereg.
The attributes are like that,
course(course_id, title, dept_name, credits)
prereg(course_id, pre_id)
course_id attribute, of course, is the primary key.
course_id,...
1
vote
0answers
29 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
25 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
130 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
116 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
112 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
33 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
19 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
202 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
42 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
36 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
15 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
41 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
15 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
32 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
50 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 ...
0
votes
1answer
36 views
reference request: solving problems by dynamic programming + 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), k=0,\dots,N-1
$$
given some $x_0$ and ...
0
votes
1answer
15 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
13 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
34 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
17 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
14 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
111 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 ...
0
votes
0answers
32 views
Books on Lambda calculus
I would like to learn Lambda calculus (informally). What are the pre requisites for studying lambda calculus ? Can someone recommend an interesting textbook that introduces subject historically with ...
0
votes
0answers
20 views
Is there a uniform way of giving for any mathematical formula a hypercomputer that computes it?
Some mathematical formulas directly suggest an algorithm for computing it (even if sometimes an inefficient one).
For example, if we recursively define $\sum_{i=1}^nx_i=x_n+\sum_{i=1}^{n-1}x_i$, then ...
1
vote
0answers
13 views
Good exposition of tableau for first-order logic with equality?
I'm looking for a resource (online or printed) that explains in a self-contained way the classic tableau for first-order logic with equality. All I can find are expositions of tableaux for first-order ...
6
votes
2answers
116 views
Minimum set cover with incompatible sets
I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously).
To state it more formally:
We have a finite base set $X$ and a family $\...
0
votes
0answers
21 views
Reference request: Learning runtime analysis (Complete material)
I am very curious about learning runtime analysis more than just what MIT courseware provides (The course with Erik Demaine 6.006) And what CLRS offers, which is a nice explanation about asymptotic ...
2
votes
1answer
52 views
Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time
I am looking for an algorithm for approximating the chromatic number of an undirected simple graph with $n$ vertices in $O(n^{c_1})$ time and $O(n^{c_2})$ space, for some constants $c_1$ and $c_2$. ...
0
votes
0answers
18 views
What the the most efficient and effective VM ISA/computational model format backed by research?
The JVM and CLR are stack based machine are very efficient, mainly due to the investment in these platforms than an efficiency and effectiveness of stack based VMs.
For en entity that does not have ...
1
vote
0answers
24 views
Cloud computing application [closed]
Question
I want to analyze the potential of a cloud computing application that performs payroll and invoicing over the Internet from a large Internet company.I want also to describe the systems ...
0
votes
0answers
21 views
Extending the token bucket algorithm
I've been looking at implementing a local rate limiting solution satisfying certain guarantees. I've found surprisingly little literature on the extensions of the token bucket algorithm to hierarchies....
3
votes
0answers
18 views
Spanning hypertree which connects the vertices as slowly as possible
I want to find a reference for the following problem or a similar problem for my paper. I found a greedy algorithm for this problem, but writing such an algorithm in a paper is not common in my area, ...
4
votes
1answer
98 views
Is there a graph theory textbook that covers treewidth thoroughly?
Can someone recommend a graph theory textbook that covers treewidth thoroughly?
Something that focuses on the graph-theoretic structure of bounded treewidth graphs rather than solving problems on them....
1
vote
1answer
43 views
What is a task type?
I have an unlabeled dataset: 500 X-rays of seeds in husk. In each image there are different number of seeds, for instance, from $10$ to $50$.
A seed has some features. The main features are a seeds' ...
0
votes
0answers
22 views
Modern vs. original formulations of Rice's theorem
Rice's theorem states that any nontrivial semantic property of Turing machines is undecidable.
However, when I opened “Classes of recursively enumerable sets and their decision problems” by H. G. Rice,...
0
votes
1answer
40 views
Reference asking : High Performance Computer Architecture
Topics
Pipelining: Basic concepts, instruction and arithmetic pipeline, data hazards, control
hazards, and structural hazards, techniques for handling hazards. Exception handling.
Pipeline ...
1
vote
1answer
23 views
linear time nash equilibirum aproximations for two player zero sum games
I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. ...
3
votes
0answers
60 views
bounding the height of stack when checking acceptance pushdown automaton
Let $A$ be a nondeterministic PDA (with empty stack acceptance). I am looking for a reference for a statement of the following form.
There exists a constant $c$, computable from $A$, such that:
if $w$...
1
vote
0answers
18 views
"Close" Graph Coloring?
I haven't been able to find whether this problem has been studied: we are given a graph $G$ and an ordered list of $k$ colors $L = [\ell_1, \cdots, \ell_k]$. Additionally, we are given a positive ...
0
votes
0answers
27 views
Distributed Serializable Snapshot Isolation
I was wondering if there is any research on distributed transaction algorithms for Serializable Snapshot Isolation. I found Binnig, C. et al.: Distributed snapshot isolation: global transactions pay ...
1
vote
1answer
40 views
Given a list of integer rectangle areas, find all integer rectangles that they can tile
Is there an efficient algorithm that takes in a list (multiset) of integer rectangle areas and finds all possible integer rectangle tilings?
Every integer rectangle area in the list (multiset) must be ...
0
votes
0answers
20 views
Textbooks about the verification of computer programs that use Z as the specification language
I'm looking for textbooks/lecture notes about the verification of computer programs, i.e. proving their correctness, that use Z as the specification language against which the correctness is verified.
