Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
1,052 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
2
votes
1
answer
393
views
Understand the Levin reduction
Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)~ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...
0
votes
1
answer
44
views
Optimal dictionary for coding
Given alphabet $A$ and a sequence $S,ドル determine the optimal dictionary $D$ of max word length $m$ that can compose the sequence.
Optimality can be given as a two-part cost $(L)$ = dictionary cost $(...
4
votes
4
answers
623
views
What is a resource on encodings for Turing machines?
I've been studying Turing machines, and decidability problems, and I'm struggling with the concept of an encoding of a Turing machine (or, for what it's worth, of any mathematical structure), in the ...
1
vote
2
answers
145
views
Matching polynomial in Computer Science
Do you know any references on the use of matching polynomials in computer science, particularly regarding their applications or algorithmic developments?
0
votes
1
answer
65
views
Inpainting of complex images
In want to create an algorithm which can complete the missing part of an image, I gather this can be done with machine learning algorithms. I know nothing about these algorithms but I am willing to ...
4
votes
3
answers
211
views
Recommended study resources for Computer Architecture: RTL, Basic Computer Design, Microprogrammed Control, and CPU design
I'm currently studying Computer Architecture / Computer Organization, and I'm struggling to find resources to understand a few specific topics.
These are the four areas I’m focusing on:
Register ...
user avatar
user163790
0
votes
2
answers
127
views
What Precisely Is An Effective Method/Procedure?
As title. I'm, fortunately, reading the Wikipedia page titled "Effective Method", unfortunately. (1. I love the fact that it's open-source/available to everyone on Earth, 2. I hate ...
1
vote
1
answer
87
views
Software that finds/proves runtime complexity of given code?
Is there software that can prove the runtime complexity of given code?
2
votes
1
answer
66
views
Alternative FPT running times
According to Lemma 29.4.1. in Downey & Fellows ' Fundamentals of Parameterized Complexity the running times
a) $(\log n)^k,ドル and
b) 2ドル^{o(k\log n)}$
should be FPT running times, when $n$ is the ...
0
votes
0
answers
70
views
Book containing the statistics of random linear codes
I'm looking for a book containing the statistics of random linear code. By "random" I mean that the parity matrix (or the generating matrix) of the code is taken at random with uniform ...
2
votes
2
answers
355
views
Strongest criticisms of object-oriented languages?
Linus Torvalds has famously attacked the object-oriented language C++, but he didn't offer many specifics about why, besides saying C++ uses "inefficient abstracted programming models". What ...
1
vote
1
answer
104
views
Research/theory on layout algorithms? (i.e. CSS flexbox, etc)
Lately I've been trying to develop a layout engine for my own purposes, from scratch. Similar to CSS layout systems like flex, my layout system works on the basis of a tree of rectangles, with some ...
1
vote
1
answer
80
views
What is this sub-rule in grammars called?
Suppose I'm writing a grammar rule for arithmetics, and for additions, I got this:
...
3
votes
0
answers
66
views
reference for SAT formula for connectedness
SAT formulas for connectedness of a set of nodes in a graph can be constructed, basically by specifying the distance of each node to a source node, see for example the answers here:
Boolean ...
0
votes
0
answers
182
views
Is this reduction from Exact 1-in-3-SAT to Subset Sum using Horowitz and Sahni's algorithm known?
I'm exploring a reduction from Exact 1-in-3-SAT (x3SAT) to the Subset Sum problem that allows the use of the Horowitz and Sahni algorithm, achieving a time complexity of
$\mathcal{O^*}(2^{n/2})$ for ...