Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
4
votes
0answers
49 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
15 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
0answers
9 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 ...
2
votes
0answers
20 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
22 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
18 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
35 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
67 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
11 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
115 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
83 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
34 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
74 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
67 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
19 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
86 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
648 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
36 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
141 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
24 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
38 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
63 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
42 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
1answer
105 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
75 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
41 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
19 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
17 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
35 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 ...
-1
votes
1answer
55 views
A question about a variant of a knapsack problem
I have the following problem:
Let $q_1,\cdots,q_k$ be natural numbers $> 0$, $q := \sum_{1\le i \le k}{q_i}$ and $s_1,\cdots,s_k$ be positive $>0$ real numbers, and $S$ be a positive real number....
0
votes
0answers
12 views
Sensorimotor knowledge manipulation and knowledge base? Reference request
Is there such research trend as sensoritmotor knowledge formalization, manipulation, representation and storage in specialized sensorimotor knowledge bases? I am aware that multimedia data can be ...
2
votes
1answer
67 views
Complexity of polynomial interpolation
Polynomial Interpolation in the general case is $O(n^2)$ time complexity, but it can be done better in particular situations. For instance, when the polynomial can be evaluated at the complex roots of ...
1
vote
1answer
15 views
Labeling half of a bipartite graph
Consider the following problem: let $(U \cup V, E)$ be a bipartite graph. Is it possible to label the vertices of $U$ with either $``+"$ or $``-"$ such that every vertex of $V$ is adjacent to a vertex ...
2
votes
0answers
29 views
Reference request: Algorithms on Turing Machines
Is there a good survey or some papers with algorithms in the Turing machine model? I know the paper STRING-MATCHING AND OTHER PRODUCTS contains Turing Machine version of KMP. Are there any other such ...
2
votes
1answer
60 views
Are there any computer science encyclopedias?
Consider the volume "The Princeton Companion to Mathematics" which has the broadest range of topics attempted by any book in the field.
Does a Computer Science counterpart exist?
0
votes
0answers
16 views
Hierarchical Parallel Processing Machines
Introduction
I am wondering if there is a generalization of parallel processing / asynchronous communication that explains/models how to deal with a hierarchy of parallel processes. Mainly looking ...
0
votes
0answers
18 views
Generalization of Parallel Computing Architectures, Multi-Agent Architectures, and Cellular Automata
This question is for resource or explanation generalizing or simplifying the ideas of parallel computers, cellular automata, and multi-agent architectures. I am interested in the requirements for ...
2
votes
2answers
68 views
Does this progressive image compression exists?
I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.
The algorithm consists of converting one high ...
2
votes
2answers
92 views
Name for data structure
I have a data structure that implements the following operations all in $O(1)$:
$\text{insert(x)}$, inserts a value into the data structure and returns a unique key $k$ to the value
$\text{delete(k)}$...
5
votes
1answer
76 views
Pure type systems and let-expressions
I can not find any simple and detailed source of how to add non-recursive let-expressions to pure type systems.
The best I found is the Henk paper by Simon Peyton Jones, but his explanation of this ...
1
vote
0answers
27 views
Alternatives to Sequential Computation
When software boils down to assembly, it is just a sequence of instructions like this:
...
1
vote
1answer
44 views
Software code generation from the (operational) semantics - reference request for automatic programming
Are there research trends that try to research code generation directly from the (operational or some other kind of) semantics? One can imagine cognitive architecture that discovers and reasons about ...
0
votes
0answers
36 views
Strong normalization and concatenative programming language
Are there some references about concatenative programming languages with the normalization property?
0
votes
1answer
56 views
textbook on the human brain for computer scientists/machine learning professionals?
The human brain as studied by neuroscientists, or neurobiologists, generally focus on what I would call
implementation details (how specifically does information transport between synaptic channels, ...
2
votes
0answers
27 views
Reference request: Leaf-heavy master theorem algorithms
I know many algorithms that can be analyzed using master theorem, but the only algorithm I know where the time is dominated by the leaves is fast matrix multiplication.
Are there other recursive ...
4
votes
1answer
116 views
How does TLC check liveness properties?
The paper "Model Checking TLA+ Specifications" published in 1999 explained how TLC (Temporal Logic Checker) checks safety properties written in TLA+ developed by Lamport. At that time, TLC did not yet ...
2
votes
1answer
28 views
Comprehensive reference for automata
I'm looking for a general reference cataloguing types of automata. Any introductory textbook will cover DFAs, NFAs, PDAs, and TMs, but there are countless more automata of practical or theoretical ...
