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

learn more… | top users | synonyms

0
votes
0answers
13 views

Reference request: OpenMP and MPI [on hold]

I have been learning C programming for over a year. Now I wish to learn parallel programming concepts and principles and learn the use of OpenMP and MPI. Given my exposure, how should I begin? Some ...
6
votes
1answer
44 views

Matrix equality up to row/column permutations problem name

Sorry for the trivial question; has the following decision problem an "official" (possibly short) name? Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same ...
0
votes
1answer
246 views

Is there a model of computation, that tries to be realistic? [closed]

For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things ...
1
vote
0answers
29 views

What are the models of distributed storage systems in the literature?

To understand the effectiveness and/or efficiency of a protocol implemented in distributed storage systems, it is often desirable to evaluate it in a quantitative way under a hypothetical model. ...
6
votes
2answers
137 views

If $\log xy=\log x+\log y$ then why multiplication is harder than addition?

Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this ...
0
votes
0answers
15 views

TF-IDF query engine in context of terms weight

I'm looking for public algorithm which gives the engine these abilities: Query by ranked terms Limit outcome by date/time range Basically, i'd like to concentrate articles (generally ...
2
votes
0answers
26 views

Lower-bounds of running-time for output sensitive Algorithms

Let me ask my general question using a specific example, namely range searching: Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle. If the ...
0
votes
0answers
42 views

Algorithm for storing polygon edges into grid

Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is? Grid has fixed dimensions and number of cells. Grid is represented by ...
2
votes
0answers
24 views

Advantages of adaboost over gentleboost in applications, or vice versa?

I've been researching on AdaBoost and GentleBoost classifiers, but can't seem to find a clear answer to the question: What is Adaboost better at classifying in computer vision? What is GentleBoost ...
2
votes
3answers
160 views

Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation ...
4
votes
2answers
54 views

What is Finite Automata Bowl?

I was trying to find info about this Finite Automata type FAB (Finite Automata Bowl) and wasn't able to find a lot. It is basically the rules that apply to PDA apply to FAB except you drop the ...
12
votes
5answers
2k views

Using humans as components to build a computer?

Ok before I start I realise this is on the fringe of on-topic (I have read the Questions help for this site), particularly as this is not a real-world problem. However: I cannot find anything ...
1
vote
0answers
28 views

Practical Application of Kadane algorithm

Kadane Algorithm is used to solve the maximum subarray problem which in simpler terms is to find the highest possible value of a continuous sub array in an array. One often cited application of ...
0
votes
0answers
6 views

Where to publish your “good” work if you are not well known? [migrated]

I really hope it is not off-topic now. If someone has a very interesting result, i.e., he/she solves a very important open problem. He/She is not known and he/she does not has any remarkable ...
0
votes
1answer
148 views

Can we break the Shannon capacity? [closed]

I have a friend working in wireless communications research. He told me that we can transmit more than one symbol in a given slot using one frequency (of course we can decode them at the receiver). ...
4
votes
3answers
74 views

Efficiently representing a set of sets

(The question is an extension of this unanswered question on stackoverflow) If we have a set of strings, we can efficiently represent them with tries. Common branches can also be merged, resulting in ...
0
votes
0answers
17 views

Is there a paper/implementation/tool on automatically finding/suggesting similar questions for a given question?

I would like to know whether there is a method to find similar questions for a given question, just like this stackexchange.com does. Is there any paper or tools? I tried keywords such as ...
0
votes
0answers
35 views

Total world computational capacity [closed]

I'm looking for some statistics for the total number of operations possible by all the computers in all the world now. A capacity factor for this (i.e. what fraction of the potential operations are ...
1
vote
1answer
71 views

Approximation algorithms for Euclidean Traveling Salesman [closed]

I am trying to find a way to solve Euclidean TSP in a polynomial time. I looked at some papers but I couldn't decide which one is better. What is the general approximation algorithm for solving this ...
0
votes
0answers
17 views

Variants of the 3-Partition problem

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known ...
4
votes
2answers
38 views

Mapping intuitionistic logic to the modal logic S4

In his famous Semantical Analysis of Intuitionistic Logic, S. Kripke speaks of the "well-known mappings of intuitionistic logic into the modal system S4". I'm not sure which mappings Kripke means. One ...
1
vote
0answers
21 views

Proof strategies for linearizability of implementations

Background: In section 4.2 of the paper Linearizable Implementations Do Not Suffice for Randomized Distributed Computation@STOC'2011, the authors mentioned two typical proof strategies for ...
3
votes
0answers
29 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 ...
4
votes
2answers
183 views

Time complexity of base conversion

EDIT As requested, a single question Why can't arbitrary base conversion be done as fast as converting from base $b$ to base $b^k$ ? There is a big time complexity difference, so I am also ...
2
votes
0answers
36 views

Proof of contention of the wait-free consensus algorithm

I know that this is a known theorem but I can't find its proof. The theorem is: The write-contention of any $n$-process wait-free consensus algorithm (implemented from any read-modify-write ...
2
votes
0answers
22 views

Polylogarithmic value-bounded concurrent data structures such as max register, counter, and monotone circuit

While reading the research paper Polylogarithmic Concurrent Data Structures from Monotone Circuits [@JACM'2012] by James Aspnes, Hagit Attiya, and Keren Censor-Hillel, I am not sure about some points ...
3
votes
1answer
61 views

Finding largest subset that matches moments

I would like to find a algorithm that will do the following: Given two sets $A, B \subseteq \mathbb{R}$, where $|B| > |A|$, find the largest subset $C \subseteq B$, such that: $\qquad ...
1
vote
0answers
47 views

Computational approach deciding whether a set of Wang Tile could tile the space up to some size

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
4
votes
1answer
133 views

A variation of the graph coloring problem

Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same ...
1
vote
0answers
41 views

Applications of algorithms to stock trading analysis

There is a new Quantitative Finance SE site. However, I am interested in asking the "CS crowd": What are some interesting key references or surveys on applying algorithms to stock trading ...
3
votes
2answers
72 views

Computer Music Composition

I've been looking into computer assisted music composition lately for my school project. While searching for literature I came across GenJam, an interactive jazz improvisation software which uses ...
5
votes
1answer
68 views

Can we construct a Karp reduction from a Cook reduction between NP problems?

We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as ...
2
votes
1answer
120 views

Counting and finding all perfect/maximum matchings in general graphs

Recently i've been dealing with a problem that led me to the following questions: Is there a good algorithm to enumerate all maximum/perfect matchings in a general graph? Is there a good algorithm ...
1
vote
1answer
33 views

Has there been a lexer that takes in much more than a regular language?

I understand the restrictions, because a regular language is expressive enough to allow all types of tokens. And even if some context is needed in many languages to tokenize properly, they all seem to ...
1
vote
2answers
74 views

Decomposing the search problem into several small problems

I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either: Searching through the original graph. or By decomposing it into several ...
2
votes
0answers
42 views

Methods for silhouette feature extraction

Let's suppose I have an image of a person and its corresponding background. Using OpenCV I can relatively easily get a silhouette of the person from the image. I am doing a project on human ...
3
votes
0answers
90 views

C(++) library for DFAs - free for academic use

(I'm aware that software questions are better suited for stackoverflow, but since DFAs are not something that software developers usually care about, I hope it's alright if I ask here.) I'm currently ...
0
votes
0answers
28 views

Search problems that can also be solved by junction trees and searching cliques

Assume having a graph $G_{variables}=(V,U)$ where $V=\{v_1,v_2,…,v_n\}$ is a set of variables; each variable $v_i\in V$ is associated with a set of possible values (it's domain) $dom(v_i)$. Let $P$ ...
4
votes
1answer
107 views

Existence of NP problems with complexity intermediate between P and NP-hard

Assuming P!=NP, there is a result that there are decision problems intermediate between P and NP-complete. That is, the class NP cannot be a union of two disjoint subsets: P and NP-complete. I could ...
2
votes
2answers
537 views

Undecidable unary languages (also known as Tally languages)

An exercise that was in a past session is the following: Prove that there exists an undecidable subset of $\{1\}^*$ This exercise looks very strange to me, because I think that all subsets are ...
4
votes
1answer
82 views

Deleting in Bloom Filters

I know that standard Bloom Filters only have operations like inserting elements and checking if an element belongs to filter, but are also some modification of Bloom filters which enable a delete ...
4
votes
0answers
63 views

Partition a bipartite graph to a complete matching and an independent set

I am looking for a reference for the following theorem: Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$). There is a nonempty subset $Y_1 ...
3
votes
2answers
77 views

Hardness proof of EVEN-ODD PARTITION

The PARTITION problem is NP-complete: INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$ QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = ...
9
votes
0answers
70 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 st-path $P$ which minimizes ...
0
votes
0answers
93 views

On ranking (sorting) by a varying distance metric

I came across an interesting procedure that ranks (sorts) a set of tuples, not by comparisons between tuples, but by the proximity between next tuple(s) and the set of tuples already ranked. ...
7
votes
4answers
140 views

Problems that are NP but polynomial on graphs of bounded treewidth

I heard here that the Hamiltonian cycle problem is polynomial on graphs of bounded treewidth. I am interested in examples/references to different problems which is essentially hard but having ...
2
votes
1answer
99 views

What abbreviations to use in CS citations? [closed]

What abbreviations should I use in computer science citations? I just found the IEEE style guide. It lists abbreviations such as Eng., and ...
2
votes
0answers
35 views

Code measurements in emperical software engineering: how to plan measurements?

I am talking about a measurement plan for software metrics and I am looking for references. In emperical software engineering there are code level measurements ("software metrics" that measure, e.g., ...
1
vote
1answer
55 views

Where can I find rules for source to source transformation optimization rules?

Upon reading Do source code optimizers exist? I knew that such programs existed but the ones I have worked with use a set of rules to drive a transformation algorithm. Ira Baxter provided a link to ...
3
votes
1answer
91 views

“Unusual” coupling between a decision problem and a corresponding optimization problem

There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case? Are there examples where the typical ...