Questions tagged [reference-request]
Questions requesting papers in the literature on specific, narrow issues.
264
questions with no upvoted or accepted answers
37
votes
0
answers
578
views
Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:
Given a planar graph $G$, and two vertices $s$ and $t$, find an
$s$-$t$ path $P$ ...
- 371
15
votes
0
answers
270
views
Using logic to prove non-regularity of a language
A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
- 12.2k
9
votes
0
answers
210
views
How to solve the loan graph problem
The problem
A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
- 138
9
votes
0
answers
94
views
Interval density of time bounded Kolmogorov complexity
The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
- 12.2k
8
votes
0
answers
107
views
Data Structures for Non-Orientable Manifolds
I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
- 81
8
votes
0
answers
85
views
Connections between circuit complexity and Unique Games Conjecture?
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
- 315
8
votes
0
answers
235
views
Complexity of computer algebra for systems of trigonometric equations
As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence:
$\qquad f_{p_0} = 0\\
\...
- 539
8
votes
1
answer
775
views
Turing Machine-Like Formalism for The Actor Model
Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.
The Actor Model is sometimes mentioned as a more powerful computational-...
- 205
7
votes
0
answers
344
views
What was the first public reference to bloom filters where the number of hash functions vary?
In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter.
This idea is ...
- 529
7
votes
0
answers
135
views
Evolutionary theory applied to programming languages
I'm looking for books applying evolutionary theory to the history of programming languages. Researching the topic I have found an interesting paper - Modelling the Evolution of Programming Languages ...
- 71
7
votes
0
answers
256
views
What are methods for showing that concurrent objects are not linearizable?
Linearizability is a well-known correctness condition for concurrent objects. It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point ...
- 9,179
7
votes
1
answer
560
views
Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?
The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}...
- 8,817
6
votes
0
answers
141
views
Time complexity of linear programming with small number of variables
I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
- 1,319
6
votes
0
answers
302
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 ...
- 3,413
6
votes
0
answers
106
views
Where did our present regex notation originate?
First question, and my apologies if it is off-topic! This question suggests to me I may not be totally off-base.
Where did our present regex notation originate? I am particularly wondering how <...
- 161
6
votes
0
answers
163
views
Approximate Weighted Partial Max SAT
Given a Weighted Partial Max SAT problem (WPM-SAT) - are there generally used algorithms or techniques to generate 'approximate' solutions, which are
not necessarily optimal, but found faster than ...
- 183
6
votes
0
answers
159
views
Has there been any attempt to systematically categorize programming puzzles?
Has there been any attempt to systematically categorize programming puzzles?
I notice that some problems are similar to one another, or have analogous methods of solution. I would think there must be ...
- 658
6
votes
0
answers
378
views
Are there Some Pairs Shortest Paths Algorithms?
I know that there are All Pairs Shortest Paths algorithms. But I am not sure if they are effective if I am trying to solve the Pairs-Shortest-Path problem for a subset of my vertexes.
The properties ...
- 161
6
votes
0
answers
103
views
Bounded existential polymorphism
In his "Types and Programming Languages", Pierce, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
- 3,728
6
votes
0
answers
92
views
Decomposition of graphs that uses centers
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason (...
- 2,279
5
votes
0
answers
439
views
What's known about web search query distribution?
Silverstein et al., Analysis of a Very Large AltaVista Query Log, SRC Technical Note '98 looked at 43 days of queries in 1998 and pulled out how many terms there are per query, what the top 25 queries ...
- 529
5
votes
0
answers
113
views
Minimum spanning tree and Hamiltonian path
For a graph $G(V,E)$, under what conditions is a minimum spanning tree of $G$ equal to a hamiltonian path on $G$?
IS there any body of literature connecting these two?
- 161
5
votes
0
answers
62
views
Can we simulate any dependent datatype with `Eq`?
Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
- 29.1k
5
votes
0
answers
357
views
Is there any recent study about percentage that computer spend on sorting?
I came across this on Art of Computer Programming long time ago
Computer manufacturers of the 1960s estimated that more than 25 percent
of the running time on their computers was spent on ...
- 151
5
votes
0
answers
45
views
Authors of Complementary Slackness
Who were the first researchers to prove the Complementary Slackness condition for linear programming?
I believe that strong optimality was proved by Gale, Kuhn, and Tucker in 1951, but I couldn't ...
5
votes
0
answers
91
views
Languages recognized by finite state automata of polynomially growing size
In the course of my research (condensed matter physics stuff), I stumbled over the following concept:
The class of regular languages can be defined via finite state machines (FSM):
A language $L$ is ...
- 91
5
votes
0
answers
545
views
Best complexity of parity/comparison in the Residue Number System
Let:
$\left\{m_1, ~...~, m_k\right\}$ be a set of coprime natural numbers,
$M=\prod_{i=1}^{k} m_i$
$X$ be a natural integer, such that $X < M$
Then $X$ can be expressed in the Residue Number ...
- 6,061
5
votes
0
answers
598
views
Understanding Dinic's algorithm using dynamic trees
I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan algorithm)...
5
votes
0
answers
231
views
How to disambiguate symbolic regular expressions
What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
- 315
5
votes
1
answer
2k
views
Are there current benchmarks for algorithms solving Travelling Salesman?
I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current ...
- 344
5
votes
2
answers
200
views
Decomposing an Algorithm into Local Transformations/Perturbations
Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/...
- 101
4
votes
0
answers
46
views
What are some advanced background topics I'll need for distributed systems and networks research?
I am a new graduate student in Computer Science who would like to be able to read and understand modern and new distributed systems research papers. My current background / courses and understanding ...
- 41
4
votes
0
answers
69
views
Reference on relating Post systems to string rewriting systems and formal grammars?
wikipedia states:
Every Post canonical system can be reduced to a string rewriting system (semi-Thue system). [...]
It has been proved that any Post canonical system is reducible to such a ...
- 3,464
4
votes
0
answers
194
views
Interesting applications of union-find
I've been trying to find interesting applications of union-find that are lesser known. Here are some popular algorithms based on union-find that I know:
Kruskal's algorithm for MST
Tarjan's off-line ...
- 752
4
votes
0
answers
51
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 ...
- 374
4
votes
0
answers
47
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 ...
- 378
4
votes
0
answers
50
views
Modern presentation of Ackermann's "Solvable Cases?"
Ackermann's book "Solvable Cases of the Decision Problem" discusses decidable instances of first order logic, particularly monadic logic, and so called "equality formulas". However, the book is from ...
- 29.1k
4
votes
0
answers
42
views
Quantum algorithms for logical inference - reference request?
Microsoft is committed to the building of the scalable, industrial size topological quantum computer, Visual Studio integrated programming language and SDK will be released by the end of this year (...
- 1,351
4
votes
0
answers
114
views
How to model reversible interactive programs
Reversible programs with finite execution steps are well studied. For example, a Turing machine whose transitions are reversible and halts can be executed backwards consuming its tape in the reverse ...
- 41
4
votes
0
answers
71
views
What is the role of abstract machines in the Curry-Howard isomorphism?
By abstract machines I mean things like the SECD machine, Krivine's machine or more generally machines with states/memory/registers/stack/accumulator...
According to Wikipedia page of the Curry-...
- 483
4
votes
0
answers
67
views
Metrics for image/visual complexity in computer vision/graphics?
Could anyone kindly point me to revenant literature in computer vision/graphics that detail on metrics for image/visual complexity and how to regularize that?
More specifically, I am trying to design ...
- 141
4
votes
0
answers
116
views
Unambiguous context-free language that can't be parsed in linear time by backtracking recursive descent?
Is there a context-free language that can be expressed with an unambiguous grammar but can't be expressed with a grammar that would result in linear-time backtracking recursive descent parsing?
The ...
- 141
4
votes
0
answers
281
views
Subset sum with wider constraint
The classical 0,1 knapsack problem with weights $w$ and unit value for all items $x$:
$
max \displaystyle\sum_{i} x_i, x_i \in \{0,1\}
$
subject to
$
\displaystyle\sum_{i} w_ix_i \leq W
$
for a ...
- 41
4
votes
0
answers
70
views
Is this a known question in matrix sketching?
Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m \ll D $ dimensional columns and ...
- 173
4
votes
0
answers
250
views
Intuitive self-contained proof of Farkas' Lemma
I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states:
For any convex cone generated ...
- 443
4
votes
0
answers
89
views
Efficient algorithms for mutual, inverse, or round-trip Personalized PageRank
I'd like to implement a similarity between two nodes (X and Y) of a graph based on a simple extension of the Personalized PageRank algorithm, either:
(Mutual PageRank): the product of the PPR of Y ...
- 141
4
votes
0
answers
174
views
Heuristics and libraries for the knapsack problem
A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 items)...
- 28.1k
4
votes
0
answers
58
views
Status of Research Problems in Motwani and Raghavan
One nice aspect of Motwani and Raghavan's classic textbook, Randomized Algorithms, is that the notes for many chapters include open questions marked as "research problems." However, the textbook is ~...
- 359
4
votes
0
answers
63
views
Extending the causal memory model to wide-area distributed storage systems
In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering ...
- 9,179
4
votes
0
answers
367
views
Stereo images rectification and disparity: which algorithms?
I'm trying to figure out what are currently the two most efficent algorithms that permit, starting from a Left/Right pair of stereo images created using a traditional camera (so affected by some ...
- 141