Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...