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

learn more… | top users | synonyms

1
vote
1answer
43 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
18 views

Min-max selection sort

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

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

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
47 views

Programming languages for genetic engineering [on hold]

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
31 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
38 views

What are practical applications of AI Planning? [on hold]

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 ...
7
votes
1answer
95 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
22 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 ...
-2
votes
0answers
22 views

research on relations between density of languages and reductions

consider the "density" of a language $L$ roughly defined as the ratio of accepted words to total number of words eg something like $\rho(n)=f(n)/g(n)$ where $n$ is the word length. now consider ...
1
vote
1answer
36 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
1answer
48 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
47 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
31 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
318 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
75 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
16 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
0answers
56 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
76 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 ...
2
votes
0answers
24 views

Extend the causal memory implementation 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
172 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
144 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
900 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
36 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
28 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
46 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
58 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
33 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
64 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, ...
6
votes
1answer
210 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
42 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
53 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 ...
2
votes
0answers
38 views

Is there an available feature model and code of a dynamic software product line (DSPL)?

Dynamic Software Product Lines (DSPLS) are software product lines (SPLs) where features can be bound and unbound during program execution time. Is there a feature model and code available of an ...
5
votes
1answer
106 views

Where/when did Stephen Kleene first define the Kleene closure/star?

I'm working on a paper and would like to review the origins of Kleene's closure. I am unable to find any article of Kleene's that has the original definition of the Kleene closure. Is there a paper ...
2
votes
1answer
42 views

Bloom filter variant

I've been playing around with a simple probabilistic data structure which is very similar to a Bloom filter. Where a Bloom filter would use $k$ independent hash functions to choose $k$ of the $m$ bits ...
17
votes
4answers
911 views

Is there an anti-Bloom filter?

A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in ...
1
vote
1answer
62 views

Dual-pivot Quicksort reference implementation?

Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere? I would like to include that algorithm in a comparison among sorting algorithms for a ...
6
votes
1answer
51 views

Matrix equality up to row/column permutations problem name

Sorry for the trivial question; has the following decision problem an "official" (possibly short) name? Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same ...
0
votes
1answer
253 views

Is there a model of computation, that tries to be realistic? [closed]

For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things ...
1
vote
0answers
43 views

What are the models of distributed storage systems in the literature?

To understand the effectiveness and/or efficiency of a protocol implemented in distributed storage systems, it is often desirable to evaluate it in a quantitative way under a hypothetical model. ...
6
votes
2answers
144 views

If $\log xy=\log x+\log y$ then why multiplication is harder than addition?

Someone told me that the $\log$ function was introduced to make the calculation easier. If we have to calculate $xy$, we can calculate instead $\log x+\log y$ since $\log xy=\log x+\log y$. How this ...
0
votes
0answers
17 views

TF-IDF query engine in context of terms weight

I'm looking for public algorithm which gives the engine these abilities: Query by ranked terms Limit outcome by date/time range Basically, i'd like to concentrate articles (generally ...
2
votes
0answers
28 views

Lower-bounds of running-time for output sensitive Algorithms

Let me ask my general question using a specific example, namely range searching: Given a set of points in the plane and an axis parallel rectangle, report all points lying in the rectangle. If the ...
0
votes
0answers
49 views

Algorithm for storing polygon edges into grid

Is there any algorithm which takes edges (given by its two end points), and determines in which cell (or cells) of grid it is? Grid has fixed dimensions and number of cells. Grid is represented by ...
2
votes
0answers
52 views

Advantages of adaboost over gentleboost in applications, or vice versa?

I've been researching on AdaBoost and GentleBoost classifiers, but can't seem to find a clear answer to the question: What is Adaboost better at classifying in computer vision? What is GentleBoost ...