Questions tagged [reference-request]

Questions requesting papers in the literature on specific, narrow issues.

Filter by
Sorted by
Tagged with
2
votes
1answer
118 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
139 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
votes
3answers
115 views

The most subtle NP-“intermediate” problem

What is the $NP$ problem whose status in $P$ or $NP$-complete is still unsettled, as of 2018? This question is inspired by the following two recent breakthroughs: The work of Mulzer et. al on $NP$-...
3
votes
1answer
659 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)?
2
votes
1answer
53 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 ...
2
votes
2answers
2k 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 profits ...
2
votes
0answers
53 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
16 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
106 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
31 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
51 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 ...
4
votes
1answer
363 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/...
4
votes
1answer
231 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
56 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\...
4
votes
0answers
44 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
41 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 ...
2
votes
1answer
541 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
20 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
34 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
83 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
56 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 ...
2
votes
2answers
73 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 ...
3
votes
2answers
110 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
107 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
51 views

Alternatives to Sequential Computation

When software boils down to assembly, it is just a sequence of instructions like this: ...
1
vote
1answer
62 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
68 views

Strong normalization and concatenative programming language

Are there some references about concatenative programming languages with the normalization property?
0
votes
1answer
57 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
36 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 ...
5
votes
1answer
402 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
34 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 ...
2
votes
0answers
70 views

Minimization of simple cyclic automata

Version 1 of the question: I am looking for any correct $O(n)$ algorithm in the literature which will solve the DFA minimization problem referred to in the quote below from [Almeida & Zeitoun 2008]...
2
votes
1answer
101 views

What are good resources for self teaching parallel/concurrent/multithreaded programming techniques? [closed]

I’m having a hard time finding anything thorough. I have found some courses with titles like "parallel and concurrent programming in Java", but I'm looking to learn general techniques, not their use ...
4
votes
0answers
46 views

Symbolic Math Systems As Speculative Optimization For Numerical Software?

Has there been published work on hiding symbolic math within numeric software, partitioning parallel processes between speculative symbolic optimization search and numeric evaluations? Real world ...
1
vote
0answers
87 views

Comparison of time-dependent traveling salesman heuristics

I'm looking into implementing a heuristic for the time-dependent traveling traveling salesman problem (TDTSP) that completes in a certain amount of time. There are a wide range of possible ways to ...
1
vote
0answers
53 views

Good pointers to learn foundations of Program induction and Program synthesis

I was interested in learning more about program induction and program synthesis. I was especially interested in learning about how to form program from data for example. My background is in ...
3
votes
0answers
195 views

Introduction to the Traffic Light Scheduling Problem

I would like to understand the basics of how traffic light scheduling works. Looking through research papers the topics typically revolve around actual highway systems in urban areas, but also ...
2
votes
0answers
48 views

Literature similar to Minsky's “Steps Toward Artificial Intelligence” (1961)?

With great pleasure I was just reviewing Marvin Minsky's publication "Steps Toward Artificial Intelligence" from 1961. Now I would like to know whether there are any more compilations about the ...
4
votes
1answer
144 views

Where did Don Knuth say that suffix trees were the “Algorithm of the Year 1973?”

If you do a quick search for suffix trees on Google, you'll find a bunch of sources saying that Don Knuth called them the "Algorithm of the Year 1973." However, I can't seem to find a source on this. ...
1
vote
0answers
31 views

Applications of the (cumulated) ruler function in algorithm analysis

In Chapter 2 (Page 76) of the book "An Introduction to the Analysis of Algorithms (2nd edition)" by Robert Sedgewick and Philippe Flajolet, the authors introduce two functions: Definition Given an ...
1
vote
1answer
621 views

Applications of the LU factorization in computer science [closed]

I have been searching for the applications of the LU factorization/decomposition in computer science. From Wikipedia, I have found some of the applications, but these don't seem to be relevant to ...
2
votes
0answers
95 views

Examples of bad statistics in Computer Science

I am preparing class materials for the applied statistics class for Ph.D. students and want to present them with examples of bad statistics in different fields of computer science. I am especially ...
6
votes
1answer
225 views

Implications of $NL=P$

What would be some implications of $NL$$=P$? Would it be possible to get recommendations on good sources/papers I can read to learn more about this? Thank you
3
votes
0answers
98 views

Are there are satisfying explanations for why genetic algorithms work?

The following commentator writes: Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights. One of the biggest reasons they fell out of ...
3
votes
0answers
48 views

Formal basis for “peephole reasoning” about code

The approaches I've seen to abstractly talking about the semantics of a programming language like Turing machines, various lambda calculi, and Hoare logic seem to be talking about the behavior of ...
10
votes
2answers
679 views

How to derive dependently typed eliminators?

In dependently-typed programming, there are two main ways of decomposing data and performing recursion: Dependent pattern matching: function definitions are given as multiple clauses. Unification ...
1
vote
1answer
59 views

Are there any stochastic models of non determinism in the rate of program execution?

We know that typical operating systems and high level languages (especially those with garbage collection) cannot be used for real time operating systems. Java & jet engines don't mix, and ...
2
votes
0answers
161 views

State of the Art in linear-time DFA minimization

What is the most complicated kind of deterministic finite-state automaton that can be minimized in $O(n)$ time? Here’s what I’ve been able to find so far: The acyclic case has been solved. So any ...
2
votes
0answers
51 views

About gradient descent on non-convex functions

There is this "folklore" result that gradient descent on a non-convex function takes $O(\frac n {\epsilon^2})$ steps to get to a point whose gradient norm is below $\epsilon$ and with SGD this takes $...

1 2 3
4
5
19