Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
1
vote
1answer
18 views
Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?
Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, ...
0
votes
0answers
14 views
Which book or books are being used in these lectures on Distributed Systems?
Kindly take a look at these lecture materials.
The instructor is suggesting to study books of Tanenbaum along with his supplied reading list. But, I am not finding any similarity of the content ...
2
votes
1answer
19 views
Isomorphism problem on bounded degree digraphs
By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed.
Is isomorphism ...
1
vote
2answers
41 views
Size of tree decomposition
Given a graph $G$ with $n$ vertices, let $(X, T)$ be a tree decomposition of $G$ with the smallest width. Is the number of nodes in $T$ upper bounded by $n$? I have googled it but all materials I ...
1
vote
0answers
25 views
Lower bound on online range minimum query with element value modification
Is there a known lower bound to the online Range Minimum Query (RMQ) problem with value modifications (given the array we perform online RMQ on, support dynamically modifying the values of a given ...
2
votes
0answers
17 views
Definition of “data-directed programming”
Section 2.4.3 of SICP provides an example of data-directed programing in the context of dispatching on type, but I didn't find a general definition of what it is. Wikipedia article says that it is a ...
2
votes
0answers
30 views
Reference Request - Typed First-Order-Logic Book
There are many great references for computer scientists interested in untyped first order logic, such as Melvin Fitting's "First-Order Logic and Automated Theorem Proving" or John Harrison's "Handbook ...
1
vote
0answers
48 views
Confusion about the geometric interpretation of the simplex method for linear programming
In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of ...
0
votes
0answers
14 views
What year exactly did Dijkstra distribute EWD682?
The Dijkstra's archive says EWD682 was written or distributed between 1976--1979. I wonder if you can tell the exact year. It might not be easy since the archive itself didn't make it.
5
votes
1answer
38 views
“Functional dependencies” with cardinality constraints
Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\...
1
vote
1answer
41 views
If there is any sense of an optimal set of instructions in an ISA
So there are One Instruction Set Computers, having only one (complicated) instruction like addleq, "add and branch if less than or equal to zero". And then there ...
0
votes
0answers
25 views
Precisely when and where was Feynman's Computer Heuristics lecture given?
Feynman's Computer Heuristics lecture was apparently given at the Esalen Institute, Big Sur, California, in 1985. But I have no formal evidence of this. Has anyone ever cited this lecture that you ...
4
votes
1answer
53 views
Type system and language that implements type constraints?
Occasionally when writing programs in a statically typed language, e.g. some ML, I find having to write code for cases I know will not happen. This is because I know e.g. that a function on some data-...
2
votes
1answer
128 views
Dependent type system with different computation model
There exist various Turing-equivalent models of computation, such as lambda calculus, Turing machines, or register machines.
It seems that dependent type systems (like Coq, Agda, Idris, homotopy type ...
1
vote
0answers
28 views
Best-known Boolean Circuits for Clique? [closed]
Not having received a satisfactory response to this question in math.SE, I am asking it here:
In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
1
vote
0answers
12 views
State of the art of parser handling of offset errors
Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the ...
1
vote
1answer
23 views
Randomized communication complexity of indexing
The function $\mathrm{INDEX}:\{0,1\}^n\times\{1,\dots,n\}\to \{0,1\}$ is defined as
$$\mathrm{INDEX}(x,i)=x_i,$$
where $x=x_1\dots x_n$. I am looking for the randomized communication complexity of $\...
5
votes
0answers
79 views
What is the state of the algorithmic art for floating point arithmetic on complex numbers?
Most modern compilers and processors implement the IEEE 754 binary formats for floating point numbers. IEEE 754 guarantees that the addition, subtraction, multiplication, division, and square root ...
1
vote
0answers
21 views
The underlying type theory of HOL/Isabelle
Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?
1
vote
1answer
30 views
additive hash function
Do functions with the following properties exists for x being arbitrary stream of bytes:
op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation ...
2
votes
0answers
19 views
Good examples of consistent/admissible heuristics in non-graphical domains?
I'm preparing lectures for intro to AI, and would like to give non-boring examples of heuristic functions.
Does anyone know examples of non-trivial consistent/admissible heuristics in non-geographic ...
5
votes
1answer
92 views
The definition of weakest precondition for a non-deterministic language
In the classical IMP language, the definition of weakest precondition is:
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"
This is stating that from state s, after ...
1
vote
0answers
23 views
Summary of types of equivalence and equality in type theory, with notations and examples
Coming from non-computer science background, I am trying to understand the different types of equivalence and equality usually used in type theory. Ideally, I am looking for clear definitions and ...
1
vote
1answer
37 views
AVL Rotations Abbreviations
I read that there are 4 types of rotations:
Left rotation
Right rotation
Left-Right rotation
Right-Left rotation
What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to ...
0
votes
1answer
39 views
More efficient maximum bipartite matching
I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
-1
votes
1answer
85 views
Applications of divide-and-conquer outside of merge sort and quicksort [closed]
What are other algorithms that use the divide-and-conquer paradigm aside from merge sort and quicksort?
0
votes
0answers
12 views
How to denote a graph class which allows only $k$ instances of a certain induced subgraph?
Suppose that a graph class $\mathcal{C}$ is defined as follows:
A graph $G$ belongs to $\mathcal{C}$ if, and only if $G$ is chordal,
but has at most $k$ $5$-cycles.
I am aware that the ...
2
votes
1answer
125 views
What is the right term/theory for prediction of Binary Variables based upon their continuous value?
I am working with a linear programming problem in which we have around 3500 binary variables.
Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
3
votes
1answer
462 views
In SAT, do we require an assignment for arbitrary variables?
I am reading about the Satisfiability Problem, in page (5) the author gives the following example :
$(P \lor Q \lor R) \wedge
(\bar{P} \lor Q \lor \bar{R}) \wedge
(P \lor \bar{Q} \lor S) \wedge
(\bar{...
4
votes
0answers
89 views
Maximum-minimum-satisfiability [closed]
In MAX-SAT, we are given a formula and want to maximize the number of satisfied clauses. I.e., given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the ...
2
votes
0answers
39 views
Puzzles like Sokoban?
I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements:
The number of possible moves at each step should be limited, let's say < ...
2
votes
1answer
79 views
Do white box methods for feature extraction exist for facial recognition?
Part of something I'm working on (or rather begin working on) involves white box approaches to facial recognition. I previously worked on something for character recognition using scene segmentation ...
-1
votes
1answer
72 views
Is there a name for this shuffle algorithm?
Is there a standard name for the following algorithm? At each step, the code picks an index, remove the object at that index, and remember to never pick that index again. See the following ...
1
vote
0answers
20 views
Complexity class without fixed-poly size circuit
$PP$ is shown to have no fixed-poly size circuit by Vinodchandran.
Bounded inside the polynomial hierarchy, $\Sigma^2_p$ is also shown to possess no fixed-poly size circuit by Kannan.
In notation, ...
-2
votes
3answers
91 views
The most subtle NP-“intermediate” problem
What is the $NP$ problem which status (in $P$ or $NP$-complete) is still unsettled, as of 2018?
This question is inspored by the following two recent breakthroughs:
The work of Mulzer et. al on $NP$-...
3
votes
1answer
653 views
Does a notion of a context-free complete language exist?
Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
0
votes
1answer
38 views
Finding libraries of formalized mathematics
I want to formalize Interval Newton Methods in Isabelle. As a research, I have the curiosity of whether there is anything done in the field. For that, I need to know what mathematical contents have ...
1
vote
2answers
255 views
Knapsack problem: equal profits
I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal.
More formal definition of the problem from a Wikipedia article on KPs:
If all the ...
2
votes
0answers
32 views
Challenging exercises for proof correctness [closed]
I would like to know where I can find challenging exercises that ask to prove the correctness of an algorithm.
The invariant of most of the exercises I’ve found on the internet are quite easy (...
1
vote
0answers
14 views
Purposes of testing [closed]
At a conference, I heard a professor said that detecting error was only one aspect of testing (or purpose, I don't remember exactly). He said that testing is also used to:
Understanding the system
...
0
votes
1answer
45 views
What can we conclude about a machine $m$ from that fact that it solves a particular problem $P$?
Note: I have not studied theoretical computer science, so this may be a trivial question.
I am interested in the general question: what restrictions are put on a machine $m$ (boolean circuit, TM, ...)...
7
votes
1answer
68 views
Is distinguishing Hadamard matrices _really_ NP-hard?
In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&...
2
votes
0answers
29 views
Are there codes that detect the position of an error?
I am looking for code that detect an error and it's position (or an aproximation of it), this is more than an error detector code but a little less than a correcting code.
Do you know something like ...
3
votes
1answer
43 views
Does this “reference” problem have a name?
I have the following problem which I think is so common that I expect it to have an official name (and standard algorithm of course).
The situation is as follows:
I receive distinct items (A...E in ...
3
votes
0answers
144 views
Request for examples to show various types of subproblems in dynamic programming
Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are
prefix/postfix of a string/sequence/...
2
votes
1answer
87 views
What was Robert Floyd's algorithm for inserting brackets?
In page 71 of Mathematics for Computer Science (page 77 in the pdf) it says that "The Turing award (the “Nobel Prize” of computer science) was ultimately bestowed on Robert Floyd, for, among other ...
3
votes
0answers
52 views
A book introducing proof theory needed (many-sorted FOL, classical non-Gentzen calculus, satisfiability in partial algebras, induction)
We define a signature as a triple $$\Sigma\ =\ (S,F,\mathrm{type})$$ where $S$ is a set of sorts, $F$ a set of $n$-ary function symbols $f$ of the type $\mathrm{type}(f)$ $=$ $(M_1,\dotsc,M_n\...
0
votes
0answers
21 views
Reference request - Lecture videos for Foundations of Software
I am an undergrad that got interested in this topic called "Foundations of Software" http://edu.epfl.ch/coursebook/en/foundations-of-software-CS-452 and was wondering if anyone is aware of any videos ...
4
votes
0answers
25 views
Simple proof that finding a combinatorial map of a planar graph given as an incidence matrix can be done in polynomial time?
Suppose that I have a graph $G = (V,E)$, given as an incidence matrix of edges and vertices. Suppose that $G$ is planar, that is, it can be embedded in the plane without edge crossings.
I would like ...
1
vote
0answers
36 views
Terminology Questions: Data-structure consisting of lists without repetitions
I've google around and have been unsuccessful in finding a name for a data-structure consisting of a list whose elements are unique.
I've seen "unique sorted lists", but I'm looking into the more ...
