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

learn more… | top users | synonyms

1
vote
0answers
12 views

Are there other unsupervised techniques than clustering to partition data into classes

I have a dataset of $N$ elements; each are $n$-dimensional vectors. I want to partition them into different classes. Classification requires training data. Is clustering the only unsupervised ...
2
votes
0answers
19 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
34 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
32 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
19 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
17 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 ...
0
votes
0answers
30 views

delineations of the computer science field vs engineering/ math etc by experts [closed]

there are some strong-at-times opinions expressed about definition/ scope of CS as a field in chat including by mods. CS is a relatively young science and has shifted significantly over a few decades. ...
2
votes
2answers
23 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
7 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 ...
0
votes
0answers
8 views

Has hierarchical learning been embodied in a robot before?

I've been reading about hierarchical reinforcement learning (HRL) and it's applications. A well-written literature review on the subject can be found here. However, I was wondering if research has ...
7
votes
2answers
135 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
197 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 ...
-1
votes
0answers
17 views

Simple proof of the polynomial smoothed runtime of k-means?

The k-means algorithm has exponential worst-case runtime but its smoothed runtime can be shown to be polynomial. Is there a simple proof of this?
0
votes
0answers
23 views

A bound for the minimum vertex cover of scale-free graphs

For a complete graph, the size of minimum vertex cover is $n-1$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for ...
3
votes
0answers
44 views

What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
5
votes
1answer
43 views

Base conversion puzzle

Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows: Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its ...
4
votes
3answers
76 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
-1
votes
0answers
28 views

Asymptotic runtime of Apriori and Fp Growth

What is the asymptotic runtime of apriori and fp growth? I have been searching from on internet for a week for results but have been unable to find any proper reference.
4
votes
1answer
20 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
3
votes
0answers
54 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...
4
votes
2answers
110 views

what would be the drawbacks of lecturing two programming languages simultaneously?

One colleage came with the idea/comment that it would be useful to lecture two programming languages, eg. Java and Scheme, at the same time while lecturing an Introduction to Programming course aimed ...
2
votes
1answer
140 views

Practical Page-Replacement Algorithms

Could anyone suggest other page replacement algorithms that are applicable to the real world aside from FIFO, Second Chance (Clock), Enhanced Second Chance and Random?
3
votes
0answers
29 views

Monograph or survey paper on smoothed analysis of algorithms

The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008. Since then, has ...
-2
votes
1answer
21 views

from when do we have the field of computer vision? [closed]

when was the field of computer vision created and what are the disciplines that gave birth to it? I would appreciate it if you could give some web references that have the answer.
0
votes
0answers
24 views

Connections between reflection/introspection and metacognition

I would like to know if the notions of reflection and introspection in programming languages have prompted research in other fields other than computer science. I have found Cantwell's thesis, but I ...
5
votes
1answer
111 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
0answers
35 views

Bounded existential polymorphism

In Pierce's "Types and Programing Languages" he, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
1
vote
1answer
54 views

Video lectures on type systems

For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and ...
-3
votes
1answer
36 views

Min-max selection sort

Is there already modified version of selection sort that works like this pseudocode: ...
2
votes
2answers
87 views

Which textbook can I use after a high school CS course? [closed]

I just finished the AP Computer Science course in high school and since my school does not have any further classes, I was thinking about getting a textbook and continuing my study. APCS goes through ...
1
vote
1answer
52 views

Programming languages for genetic engineering [closed]

I'm interested in getting a Ph.D. and would love to work on a project such the GEC project at Microsoft Research, which studies the application of programming languages for synthetic biology and ...
0
votes
1answer
34 views

efficient algorithms for factoring polynomials [closed]

Does anyone know what are the most efficient algorithms for factoring polynomials in a field of characteristic zero, i.e, a field that may contain infinitely many elements. I'm mainly concerned within ...
1
vote
1answer
46 views

What are practical applications of AI Planning? [closed]

note: any tips toward making this more constructive will be highly appreciated. I've dealt with ai-related problems, from searching algorithms, to computer vision, to machine learning. However none ...
9
votes
1answer
112 views

Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an ...
2
votes
1answer
41 views

What are recent, high-quality surveys on NLP topics?

In particular POS tagging, dependency and constituent parsing. This is not really my field of study but I would really like to be able to make informed claims on what precisions current top systems ...
1
vote
1answer
37 views

A detail on variant of Mahaney's theorem about reductions of sparse languages vs P/NP

Wikipedia states on sparse languages that There is a Turing reduction (as opposed to the Karp reduction from Mahaney's theorem) from a NP-complete language to a sparse language iff NP $\subseteq$ ...
0
votes
2answers
72 views

Ant colony optimization for continuous functions

I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and ...
2
votes
0answers
52 views

Are there online available solved homeworks on complexity theory?

I have never seen this subject before but certain things I read got me curious. I found various online lecture notes on complexity theory and theoretical CS but almost no where do I see solved ...
1
vote
0answers
33 views

Shortest path with min-sum multiplication and Boltzmann distribution

My professor presented a method to find shortest paths using the min-sum multiplication and Boltzmann distribution. He multiplies the adjacency matrix many times and takes the $\beta$ of Boltzmann ...
0
votes
0answers
46 views

Where to start studying about HTM?

I am looking for references (pedagogic and beginner friendly!) to these two topics, hierarchical temporal memory algorithms applied to deep planning problems (multi-layer) neural networks trained ...
6
votes
4answers
386 views

Computer science for programmers

I'm a self-taught programmer and have been coding for 8 years. Due to this experience, I'm already very familiar with the principles of programming (such as if-statements, classes, polymorphism, ...
2
votes
2answers
89 views

What is the state of the art in efficient boolean function operations?

How do you most efficiently combine boolean functions with a large number of variables using AND, OR, and NOT? The most up-to-date work that I can find on this subject is about 20 years old ...
0
votes
0answers
18 views

Finding a minimum covering of a polygon with interesting shapes

After reading many papers about problems of minimum polygon covering, I found out that there are four different types of units that are considered for covering polygons, in increasing order of ...
5
votes
1answer
90 views

What is the complete version of the paper: “How to Generate and Exchange Secrets (extended abstract)” by Andrew Yao?

I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. ...
0
votes
1answer
72 views

Is the Berman-Hartmanis Conjecture Solved?

The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on ...
8
votes
1answer
87 views

Probability Distributions and Computational Complexity

This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem ...
4
votes
0answers
42 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 ...
3
votes
2answers
90 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
5
votes
1answer
176 views

What algorithms exist for solving natural number linear systems?

I'm looking at the following problem: Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number ...
5
votes
2answers
149 views

Which language families admit inductive definitions?

I am self-learning about formal languages. I learned that the family of the regular languages can be defined inductively, in terms of the operations they are closed under (namely the smallest ...