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

learn more… | top users | synonyms

1
vote
1answer
22 views

Ordered knapsack problem?

I'm trying to find the name of this problem, and with it a reasonable algorithmic solution. Setup: There are $n$ items with weights $w_1,\dots,w_n$, and $m<n$ buckets with target weights ...
0
votes
0answers
26 views

Where's the engineering practices research? [on hold]

So in my contracting career, I've often come across situations where a client was ignorant of engineering practices and needed convincing of some pretty fundamental stuff. Like Developers needing good ...
1
vote
1answer
65 views

How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs? [on hold]

As in I don't know what is the difference between say the conferences SODA, STOC or FOCS. Measured in terms of such conferences, where would such a result be publishable? This is not a "technical" ...
4
votes
1answer
37 views

Who invented the state elimination algorithm for converting finite automata into regular expressions?

The state elimination algorithm is an algorithm for converting finite automata into regular expressions. It's found in many textbooks, including Sipser's Introduction to the Theory of Computation. ...
1
vote
0answers
27 views

sets of axioms for LADR automated theorem provers

I am pretty new to ATP, but I'm really enjoying playing around with prover9. I have found a nice set of axioms for basic information-theoretic proofs here, I was wondering if there are some ...
1
vote
0answers
21 views

NPDA, guessing capability and stack as an exclusive resource

Context Free languages is exactly the class of languages recognized by Nondeterministic Push Down Automata (NPDA). We can view a nondeterministic transition as a guess; for example if $L = \{x x^R ...
3
votes
0answers
12 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 ...
8
votes
4answers
272 views

Why is binary search called binary search?

I heard several possible explanations, so I would like some trustable reference. Update 05.19: I'm interested in the question because one of mine students wrote in his thesis that the name comes from ...
2
votes
1answer
26 views

Counting the nodes in a network in a distributed way

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do ...
5
votes
2answers
44 views

Formalizing basic category theory in Coq

I'm a total beginner in Coq and I'm trying to implement some category theory stuff as an exercise. I surfed a little among git repos of the many avaible such implementations (HoTT, Awodey's Coq ...
4
votes
2answers
78 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
3
votes
1answer
35 views

Lower bound for maxima on 2D plane

Given $n$ points $(x_1, y_1), \ldots, (x_n, y_n)$ on a 2-dimensional plane. A point $(x_1, y_1)$ dominates $(x_2, y_2)$ if $x_1 > x_2 \land y_1 > y_2$. A point is called a maxima if no ...
-1
votes
0answers
21 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.
3
votes
3answers
96 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 ...
11
votes
1answer
583 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
38 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
34 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
39 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?
2
votes
0answers
42 views

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

According the paper [1] (Section 4), 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
38 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
50 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
17 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
35 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
108 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
22 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
38 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
37 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
66 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
76 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
50 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
19 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
25 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
43 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
83 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
44 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
26 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
131 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
673 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
50 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
155 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
23 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
208 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 ...