Questions requesting papers in the literature on specific, narrow issues.
0
votes
1answer
19 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
56 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&...
0
votes
0answers
17 views
detecting 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
41 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 ...
1
vote
1answer
34 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
64 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
39 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
17 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 ...
3
votes
0answers
16 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
34 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
52 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
10 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
63 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
22 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
54 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
11 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
15 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
66 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
88 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
74 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
26 views
Alternatives to Sequential Computation
When software boils down to assembly, it is just a sequence of instructions like this:
...
1
vote
1answer
41 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
34 views
Strong normalization and concatenative programming language
Are there some references about concatenative programming languages with the normalization property?
0
votes
1answer
45 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
22 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
81 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
27 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
26 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]...
1
vote
1answer
39 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
39 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
29 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
24 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
64 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
40 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
84 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
17 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
133 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 ...
1
vote
0answers
62 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 ...
5
votes
0answers
97 views
Implications of NL=P
What would be some implications if 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
64 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 ...
3
votes
0answers
44 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 ...
8
votes
2answers
331 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
53 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
107 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
44 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 $...
0
votes
0answers
85 views
About ADAM, the optimization algorithm for neural nets
Is it fair to say that ADAM (or its special case RMSProp) is the most used algorithm for training neural nets? (If yes, then can someone share some authoritative references on maybe establishing its ...
3
votes
0answers
80 views
Looking for a subclass of deterministic context-free languages, other than the subclass of regular languages
Let $X=\{x_1,\ldots,x_n\}$ be a finite set of alphabet and $X^\ast$ denote the set of all words (including empty word) over $X$. Clearly, $X^\ast$ is a regular language.
Is there a subclass, say $C$, ...
5
votes
2answers
674 views
Can two different complexity classes be equal relative to an oracle? Example request
Is there a known example of two complexity classes, $A$ and $B$, such that:
$A \neq B$;
there is an oracle $O$ for which $A^O = B^O$?
I strongly believe that there are such examples, as otherwise $P ...
9
votes
1answer
123 views
Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?
I'm working on a problem related to Latin squares, and I want a method for what essentially boils down to the decision problem:
Input: A finite, simple graph G.
Output: ...
