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

learn more… | top users | synonyms

7
votes
0answers
46 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 ...
4
votes
0answers
14 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. ...
0
votes
1answer
18 views

How does a compiler work? [on hold]

I am interested to know how a compiler like turbo c works. I know that its a long process including electronics so you cant tell it to me over here. But please suggest me a book. Thank you
3
votes
0answers
74 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
42 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
31 views

Using algebraic structures to solve computer science questions (xpost from math.se) [closed]

This is a cross post from here. I would like to know of some examples or references where algebraic ideas have been used in complexity theory or the like. Examples would be parallels of ...
1
vote
0answers
29 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
20 views

What is MongeElkan distance between words?

i used CosineSimilarity, EuclideanSimilarity, LevenshteinSimilarity and known about how it ...
8
votes
1answer
103 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
48 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
25 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
920 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
82 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 ...
4
votes
4answers
668 views

Is there a method for automatic runtime analysis of algorithms?

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms? I googled "Automatic algorithm analysis" which gave me this but it is too ...
2
votes
1answer
48 views

NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors. Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations ...
5
votes
0answers
36 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 ...
2
votes
1answer
49 views

Natural Language Parser that can handle syntactic and lexical errors

I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small ...
5
votes
1answer
57 views

What is the practical relevance of textbook mutual exclusion algorithms?

There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ...
0
votes
0answers
4 views

Hierarchical reinforcement learning exploration methods

One of the extensions to hierarchical reinforcement learning is change the degree of randomness that is applied while choosing an action. It is possible to increase the randomness to encourage ...
0
votes
0answers
10 views

Reference for Motivation of WSN Localization in 3D

I need references to motivate the reader about 3D Wireless Sensor Network Localization problem. I have found many references about 2D WSN localization, however, there is a lack of 3D WSN Localization ...
2
votes
1answer
72 views

Algorithms online problems

I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations. As far as I can see, the sites that I ...
2
votes
2answers
56 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
0
votes
0answers
60 views

Logic and Functional programming

I have a subject Introduction to logic and functional programming but the course is not provided in detail. This is the provided course. Introduction to declarative programming paradigms. The ...
3
votes
1answer
57 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
1
vote
0answers
44 views

References for wearable e-health systems for biosignal based health monitoring [closed]

Ubiquitous computing refers to "information technology and computer power, which in principle pervade all everyday objects" (see Friedewald and Raabe, 2010). A similar form is wearable computing, ...
2
votes
1answer
79 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...
1
vote
1answer
24 views

Semantic information collections on the web. (Semantic Wikipedia)

There are lots of technologies supporting semantic information markup even as wiki software. I am wondering if there is any kind of broad information collection project like Wikipedia which features ...
2
votes
1answer
55 views

What is the lower bound for finding the third largest in a set of $n$ elements?

The problem is easy to describe: What is the lower bound for finding the third largest in a set of $n$ elements? Particularly, do we have to know both the largest and the second largest for ...
1
vote
0answers
46 views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm or a single class Java/C implementation? I have access to original two papers, but they do not show the ...
1
vote
2answers
98 views

Reference request for coding Knight's Tour

Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?
5
votes
3answers
130 views

Complexity of natural language processing problems [closed]

Which natural language processing problems are NP-Complete or NP-Hard? I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any ...
0
votes
0answers
23 views

Patent-free algorithm for labeling a MRF/CRF

At the moment I'm implementing a video segmentation algorithm for moved foreground / background. In the literature often a graph-cut algorithm is used, which is patented by US6973212. Are there any ...
0
votes
0answers
14 views

Is there an application area that sensors are on planes and we know the local positions of the sensors, but not the global positions?

I am currently writing the motivation of my thesis. And the answer to this question is very crucial for me: I am working on wireless sensor networks. Say that, there are a number of planes, for ...
9
votes
3answers
99 views

Recipe book for SAT encodings?

SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts. Every time one wants to use them to solve a problem in a specific ...
1
vote
0answers
23 views

Equivalence of data-flow analysis, abstract interpretation and type inference?

@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of ...
1
vote
0answers
20 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each ...
3
votes
1answer
56 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq ...
2
votes
0answers
47 views

Recent Garbage collection survey paper

Many years ago I read a GC survey paper that was updated every few years with advances; I tried to find such a paper today to point a questioner on Stackoverflow at. However all I can find is very ...
4
votes
0answers
34 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$ ...
7
votes
0answers
53 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
3
votes
0answers
28 views

Term for index-like data structures

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently. That includes trivial things like sorting/hashing, less trivial ...
2
votes
0answers
27 views

Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

I have recently been working on an applied project where I have to solve optimization problems. I have found that it is much easier to solve an integer linear program (ILP) as opposed to a ...
3
votes
0answers
40 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 ...
1
vote
0answers
43 views

Teaching computer science in developing countries - any literature?

I've been teaching computer science in a developing country and I've seen how the everyday challenges are very different from what I was used to. The students are different. The teachers are ...
1
vote
1answer
25 views

Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy

I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise ...
1
vote
1answer
34 views

Feasibility of linear inequalities with binomial variables

I have a system of linear inequalities of the form $A^t x <= b$ where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
2
votes
2answers
55 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
0
votes
0answers
8 views

Hierarchical learning in a non-static environment

I've been reading about hierarchical reinforcement learning (HRL), in particular it's application to a simple delivery task as show here. While reading the paper, I noticed that the environment ...
8
votes
2answers
201 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ ...
5
votes
2answers
224 views

Direct NP-Complete proofs

I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are ...