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

learn more… | top users | synonyms

0
votes
0answers
15 views

Definition of data and control?

Do you know of a definition, from a realiable source such as a textbook, of the terms Control and Data? In the sense they are often contrasted in programming languages, e.g. Haskell libraries.
1
vote
2answers
46 views

Splicing squares on a Turing Machine finite tape

Trying to explain a problem, I thought of a variant of Turing Machines. It is unlikely to be new, but I do not recall ever seing it before, and I wonder whether it has been used or has a name. The ...
10
votes
1answer
489 views

What is the use of finding minimum number of straight lines to cover a set of points?

There is that popular problem [1] [2] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D. Even though I have scanned many papers, none of ...
0
votes
1answer
34 views

Application of shortest vertex-disjoint path with time window

I am working on finding shortest disjoint path problem, When there are distinct origin destination pairs and there is a predefined time window (or length) associated with each object (which we want to ...
0
votes
1answer
30 views

Algorithm to recognize Strongly Regular Graph (SRG)

I am looking for an algorithm to determine whether a graph is Strongly Regular Graph (SRG) or not.
1
vote
0answers
21 views

$\mathsf{PP}$ compared to $\mathsf{\#P}$

Since know that $\mathsf{TC^0\subsetneq PP}$, I wonder if we also know that $\mathsf{TC^0\subsetneq\#P}$? I understand that $\mathsf{\#P}$ is in counting hierarchy.
0
votes
0answers
31 views

2-depth arithmetic circuits and VP vs VNP

the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary: is this new paper Sums of ...
1
vote
0answers
29 views

Status of $BQP^{NP},NP^{BQP}$

The relation between $BQP$ and $NP$ is an open problem, while it seems that $BQP$ is somewhat lower for $NP$ than the other way round. Is the status of lowness of these problems known?
1
vote
0answers
26 views

How to generate globally unique timestamps for transactions in distributed database systems?

According to Section 4 in the paper [1], timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the ...
3
votes
0answers
36 views

Complexity of clustering lattice points

[Note] I have completely rewrited the question after Yuval's comments. I hope it makes more sense now! $\newcommand\ZZ{\mathbb Z}$$\newcommand\dist{\operatorname{dist}}$Consider the $d$-dimensional ...
1
vote
1answer
45 views

Computer Science and Programming for a complete novice

everyone! I am going to learn mathematics in a university, but it will be rather ''pure'' math, so, I want to get some exposure to computer science on my own. The problem is, I've never tried any ...
1
vote
0answers
16 views

Efficiently decidable logics

So propositional logic (PL) is efficiently (in P) decidable because I can convert formulas to an equisatisifiable CNF-formula, negate and convert (efficiently, by De Morgans laws) to DNF. I can then ...
3
votes
1answer
26 views

What are some interesting applications of the skyline problem?

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each ...
6
votes
0answers
106 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 ...
2
votes
0answers
21 views

Research regarding algorithm generation/discovery/heuristics

Say I have a specification of preconditions and postconditions for a function. Is there a field of computer science that studies the automated generation of functions that satisfy those ...
4
votes
2answers
34 views

Algorithmic type checking for Calculus of Inductive Constructions

So from reading "Advanced Topics in Types and Programming Languages" (ATTPL) I know of the calculus of constructions (CoC). It also presents the "algorithmic" type checking rules. Reading Coq's ...
5
votes
0answers
35 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 ...
2
votes
1answer
64 views

Are there name and literature for this SAT-like problem?

Given $f : \{0,1\}^* \to \{0,1\}$ and $n \in \mathbb{N}$, we define $\textsf{Prob}(f,n)$ as the following problem: Find an $x \in \{0,1\}^n$ such that $f(x) = 1$. A machine solving ...
2
votes
1answer
72 views

Abstract algebra and programming languages

Quite often, I stumble upon abstract algebra concepts like initial algebra, free algebra, and similar while reading papers on programming languages. For instance, in papers on algebraic data types, ...
1
vote
1answer
34 views

Absolute orientation alignment with vectors

I have two trajectories of a moving object. Each trajectory is composed of poses at discrete time. Each pose is a translation vector and a rotation matrix. Each trajectory defines the same path (with ...
2
votes
3answers
40 views

Existence of functions that only tests memberships without revealing any information about the members

Given a set of strings $\{s_1, s_2, \cdots, s_n\}$, is there a way to encode them to a program $P$, such that given some string,$s$, the program can test the membership efficiently (deterministically ...
0
votes
0answers
18 views

Algorithms to generate random orthogonal basis for given Lattice

Suppose I want to generate a $n$-dimentional (random) Lattice, and then output a list of all orthogonal vectors of length $d$. What are the possible algorithms to do this, in poly-time? one way ...
1
vote
0answers
20 views

Minimum number of givens for General Sudoku of size $n^2 \times n^2$

Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens). What ...
3
votes
1answer
33 views

Are there any open source SAT solvers with UNSAT core extraction algorithm built in?

Just like the title says. I need to use a SAT solver on a series of CNF formulas but not only do I need an answer of the type satisfiable/unsatisfiable but also some subset of clauses whose ...
1
vote
0answers
20 views

Stable matching of producers, consumers and objects

Has the following version of the stable matching problem been studied? There are $k$ types of objects. There are $n$ producers, each of whom can produce a single object of any type, and has a ...
5
votes
4answers
79 views

Reviews of work in the field of partial evaluation (post 1993)

I'm looking for relatively new reviews of research work on partial evaluation. The most recent work I've found is "Tutorial notes on partial evaluation" by Charles Consel and Olivier Danvy (1993). The ...
0
votes
1answer
41 views

LL(k) Prediction Techniques (and Insight on method applied)

I'm requesting references for LL(k) in situations where k > 1 for reasons described below. I'm looking for ...
1
vote
0answers
40 views

Network clearance algorithms

In the network clearance problem, we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex). Each edge can transport up to its capacity each time step (i.e., ...
14
votes
4answers
4k views

Did 'Eugene Goostman' really pass the Turing test?

It is being said that 'Eugene Goostman', a computer programme developed to simulate a 13-year-old boy, managed to convince 33 per cent of the judges that it was human, and thus passed the Turing Test. ...
2
votes
1answer
25 views

Monotone Frameworks: Transfer functions for flow edges instead of labels

So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$. The goal ...
3
votes
1answer
126 views

Equivalent Straight Line Embedding of a Planar Graph Drawing on a Grid

An embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that: the endpoints of ...
1
vote
1answer
670 views

Is log(n) in complexity class P?

$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P? $n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P? If ...
3
votes
0answers
48 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 ...
7
votes
1answer
141 views

What do we know about NP ∩ co-NP and its relation to NPI?

A TA dropped by today to inquire some things about NP and co-NP. We arrived at a point where I was stumped, too: what does a Venn diagram of P, NPI, NP, and co-NP look like assuming P ≠ NP (the other ...
1
vote
1answer
21 views

Approximate probabilities of passing a NIST statistical test

I am working with random number generation and testing, so I'm using NIST statistical tests to examine my random numbers. Now I want to compare my solution with other RNGs, but i can't find any ...
0
votes
1answer
57 views

Running time of partial algorithms

What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts? Assume, if necessary, that the halting problem ...
3
votes
3answers
182 views

4-color to 3-color polynomial reduction

I know a simple reduction from 3-color to 4-color. But how do you reduce 4-color to 3-color ? I have been searching for the right way to make this reduction for a while now. I would love some ...
2
votes
1answer
21 views

Prefix computation used for lexical analysis?

I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms. Several lists of ...
2
votes
2answers
72 views

Where can I find a high quality copy of Turing's On Computable Numbers?

Currently, I'm reading a photocopied version of Turing's famous article On Computable Numbers, With an Application to the Entscheidungsproblem. This is the best photocopy of his paper that I can ...
8
votes
0answers
102 views

Who coined the term “machine learning”?

I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ...
11
votes
1answer
167 views

Fastest known complexity for combinatorial ILP algorithm?

I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming? I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. ...
3
votes
0answers
85 views

Who coined the term “artificial intelligence”?

The most obvious (and commonly given) answer to this question is John McCarthy, but I have traced the first usage of this term to a 1955 paper, which McCarthy co-authored with Marvin Minsky, Nathaniel ...
2
votes
2answers
45 views

Learning Quadratic Functions

I have seen in some ML tutorial that functions of the form $f(\vec x) = \vec x^T A \vec x$ ($\vec x \in \mathbb{R}^n$ and $A$ is an $n\times n$ real matrix) can be PAC learned. Can anyone point me ...
1
vote
0answers
35 views

Universal algorithm testing framework [closed]

Currently I'm working on my thesis. I'm writing about subgraph isomorphism problem and various algorithms, solving this problem. One of my task is to integrate that problem in a testing framework, ...
0
votes
1answer
38 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
9
votes
1answer
123 views

Determining the minimum number of edges to add in order to be 3-connected

A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a ...
1
vote
2answers
59 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
3
votes
0answers
29 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to communicate a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. ...
10
votes
3answers
1k views

Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
2
votes
2answers
110 views

What is a conventional format for presenting algorithms?

I'm writing a technical paper and the review committee wants my methodology to be represented in a conventional algorithm format. I've been searching all over the web for the conventional structure ...