Questions tagged [reference-request]

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

265 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
37
votes
0answers
556 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$ ...
15
votes
0answers
250 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 ...
9
votes
0answers
202 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, ...
9
votes
0answers
90 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 ...
8
votes
0answers
104 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, ...
8
votes
0answers
83 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 $\...
8
votes
0answers
232 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\\ \...
8
votes
1answer
747 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-...
7
votes
0answers
342 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 ...
7
votes
0answers
134 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 ...
6
votes
0answers
127 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 ...
6
votes
0answers
280 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 ...
6
votes
0answers
104 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 <...
6
votes
0answers
155 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 ...
6
votes
0answers
157 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 ...
6
votes
0answers
370 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 ...
6
votes
0answers
98 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 ...
6
votes
0answers
249 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 ...
6
votes
0answers
91 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 (...
6
votes
0answers
470 views

Test cases for λ-Calculus

For testing automated theorem provers we have Seventy-Five Problems for Testing Automatic Theorem Provers by Pelletier. Are there any such standard/well regarded tests for a λ-calculus that verify ...
6
votes
1answer
548 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}...
5
votes
0answers
417 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 ...
5
votes
0answers
110 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?
5
votes
0answers
61 views

Can we simulate any dependent datatype with `Eq`?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
5
votes
0answers
314 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 ...
5
votes
0answers
43 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
0answers
88 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 ...
5
votes
0answers
541 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 ...
5
votes
0answers
584 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
0answers
226 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 ...
5
votes
1answer
1k 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 ...
5
votes
2answers
199 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/...
4
votes
0answers
39 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 ...
4
votes
0answers
65 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 ...
4
votes
0answers
47 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 ...
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 ...
4
votes
0answers
48 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 ...
4
votes
0answers
39 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 (...
4
votes
0answers
109 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 ...
4
votes
0answers
69 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-...
4
votes
0answers
66 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 ...
4
votes
0answers
112 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 ...
4
votes
0answers
270 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 ...
4
votes
0answers
68 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 ...
4
votes
0answers
243 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 ...
4
votes
0answers
87 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 ...
4
votes
0answers
170 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)...
4
votes
0answers
57 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 ~...
4
votes
0answers
62 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 ...
4
votes
0answers
363 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 ...

1
2 3 4 5 6