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

learn more… | top users | synonyms

4
votes
0answers
47 views

Examples for $\Omega(n^3)$ bounds on TMs

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is ...
5
votes
1answer
38 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
73 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
21 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
19 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
50 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 ...
2
votes
1answer
46 views

Scalable quantum computation vs Uncertainty Principle

What does it means for a Quantum Computer to be scalable? I see a zero sum game between Quantum physics measurement being unpredictable and Quantum computing being scalable (and classically ...
4
votes
2answers
107 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
137 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
20 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
23 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
109 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
51 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
24 views

Min-max selection sort

Is there already modified version of selection sort that works like this pseudocode: ...
2
votes
2answers
86 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
49 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
32 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
42 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 ...
8
votes
1answer
108 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
40 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
69 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
48 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
32 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
45 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 ...
5
votes
5answers
359 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
86 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
89 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
83 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
40 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
173 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
146 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 ...
6
votes
2answers
903 views

What is the name of this prime number algorithm?

Does the following recursive algorithm have a name? If so, what is it? ...
2
votes
0answers
41 views

Introductory book on Logic and Computation

Can you give me some suggestions about a good introductory (but comprehensive) bookabout Logic and Computation? Some fuzzy topics that I have in mind are: Presburger artihm., PA, ZF, ZFC, HOL Set ...
1
vote
1answer
29 views

comparisons vs arithmetic complexity

I'm trying to find out which operation is fast, evaluating a comparison vs doing an arithmetic option on a single word (e.g subtract, add). Can anyone point me in the right direction with some blogs, ...
1
vote
0answers
29 views

Notable decidable operations on context-sensitive languages [closed]

It is not always so easy to determine which basic questions on languages are (un)decidable. Also due to Rice's theorem, many nontrivial questions on languages are undecidable. What are notable or ...
5
votes
0answers
52 views

What are the treatises on how to build mechanical computers?

I've just watched this replica of the Antikythera mechanism. I've heard also about Babagge's analytical machine and the Curta calculator. I got curious: What did they use to build computers made of ...
3
votes
0answers
63 views

What are appropriate isomorphisms between formal languages?

A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are ...
2
votes
1answer
36 views

Find $k$ subsets containing a particular element quickly

Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers. To that effect, ...
7
votes
0answers
61 views

Is there an O(n log n) algorithm for 4D line simplification?

The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are ...
1
vote
1answer
71 views

Best algorithm for correlation between time series?

I have some biological data (ECG), which are quite chaotic in nature, and and some other data; that are not chaotic but related in some way, like fatigue. I want to find out how the time series, ...
7
votes
1answer
212 views

Is the reversal of a minimal DFA also minimal?

The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with ...
5
votes
1answer
44 views

Relationship between graph expansion and conductance

I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is: Could someone point me to a reference that discusses both of these ...
9
votes
1answer
1k views

Which NP-Complete problem has the fastest known algorithm?

In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2*2^n)$?
3
votes
1answer
58 views

Complexity of factoring products of distinct prime numbers

Problem: Input is an integer number $x$ that we know factors as $p_{i_1}\cdot p_{i_2}\ldots p_{i_n}$, where the $p_{i_j}$'s are distinct prime numbers. Output is the above factorization of $x$. Do ...