Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
0
votes
0answers
21 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
13 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
35 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
32 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
20 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
45 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
111 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
22 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
10 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
20 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 $\...
4
votes
0answers
60 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
17 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
29 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
13 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
32 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
19 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
36 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
71 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
120 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
86 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
36 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
75 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
70 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
87 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
37 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
179 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
27 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
0answers
117 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
80 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
43 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
20 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
20 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
68 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
13 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
68 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
62 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
17 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 ...
