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

learn more… | top users | synonyms

3
votes
0answers
58 views
+100

Vertex Disjoint Path Covers of Hypercube-Like Graphs

This is a followup question relating to an older question I posted, namely: Decomposing the n-cube into vertex-disjoint paths. Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, ...
-3
votes
0answers
18 views

Where can I find the formal definition of Natural Language Processing?

I am recently carrying out a project related with Machine learning and Natural Language Processing due to that fact I want to know the formal definition of Natural Language Processing since I was ...
-1
votes
0answers
19 views

Reference request for old paper

Is there a pdf version of the following paper? Lipton, Richard. "New directions in testing." Distributed Computing and Cryptography 2 (1991): 191-202.
3
votes
2answers
42 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
6
votes
0answers
120 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
5
votes
2answers
83 views

Recommendations for a good (rigorous) text to study Computational Complexity.

I look for a good text to learn basics of computational complexity. I've read some parts of the first two chapters of "Computational Complexity: A Modern Approach" by Boaz Barak and Sanjeev Arora, ...
3
votes
1answer
84 views

Reconstructing a screen of permuted pixels

Reconstructing a screen of permuted pixels Summary Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture? Let: ...
1
vote
0answers
38 views

Tricks, Tips and Nontrivial Insights with Higher-Order Functions

Many years ago I briefly skimmed a physical book (or perhaps a preprint?) on programming in Racket that included lots of really unique uses of map and ...
-1
votes
0answers
16 views

Is there a language / format for describing network topologies?

Is there a formal way for describing network topologies? Bonus points if they were made with computer clusters in mind. Some common format in which most supercomputers from top500 could be described. ...
4
votes
0answers
44 views

Intuitive self-contained proof of Farkas' Lemma

I've been studying the proof of Farkas' Lemma, and given my rather fuzzy memory of Linear Algebra, am having some trouble with it. One version of Farkas' lemma states: For any convex cone ...
0
votes
2answers
43 views

Induced subgraph problem in trees

Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for ...
1
vote
1answer
48 views

context sensitive language finite or infinite

let L be a CSL. (my understanding/ memory/ expectation is) the problem is L finite or infinite? is undecidable. where was this 1st proved/ published? are there any cases in the literature of ...
2
votes
0answers
23 views

Maximum Weight Planarization of Size $n$ [duplicate]

Problem: Maximum Weight Planarization Given a weighted non-planar graph with $n$ vertices, and $m = \mathcal O\left(n^2\right)$ edges. Find the subgraph with $n$ nodes (but possibly removing edges ...
1
vote
0answers
28 views

(Why) is there no complexity class for linear space (O(n))? [duplicate]

tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it? the Quantified Boolean Formula (QBF) problem is a P-space complete ...
2
votes
0answers
26 views

Optimal way to survey a road

There is a road (a planar curve) of length 1. A treasure is placed in a random spot on the road. The treasure location is a uniform random variable, so that the probability to find the treasure in an ...
1
vote
0answers
21 views

About the complexity of learning probabilistic graphical models

I guess that one way of measuring the complexity of learning a joint probability distribution is as its "sample complexity" (which is also sometimes known as its "distributional learning complexity"?) ...
4
votes
1answer
34 views

Finding the lowest-weight negative cycle in a weighted digraph

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible? I know that I can detect ...
3
votes
0answers
66 views

Generalization of XOR Linked Lists

Are there any results generalizing XOR Linked Lists to other types of data structures? For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can ...
2
votes
0answers
118 views

on `On the cruelty of really teaching computing science' [closed]

Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course: On the one hand, we teach what looks like the ...
1
vote
0answers
30 views

Clustering of matrices

I have a matrix of n lines and T columns, containing only 0's or 1's. I would like to make permutations of lines (and lines only) to make the largest submatrix of 1's possible (i.e. i want to find ...
5
votes
1answer
167 views

Results on the difficulty of specific random 3-SAT problems?

This is a companion question to Results on number of solutions to random 3-SAT? Let $A$ and $B$ be two problems drawn from random 3-SAT, both with the same number of variables and clauses. If $A$ ...
2
votes
1answer
17 views

Reference Request: Overlaps between complexity theory and dynamical systems?

Per Wikipedia: In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in a geometrical space. Examples include the mathematical models that ...
2
votes
0answers
37 views

Results on number of solutions to random 3-SAT?

I'm looking for some published results, either empirical or theoretical, on the number of solutions to random 3-SAT problems. Given $N$ variables and a clause-to-variable ratio $\alpha$, how does the ...
2
votes
0answers
25 views

What is the state-of-the-art in machine translation on Chinese/CJK? [closed]

Sorry for my unfamiliarity with the field. Hopefully this question is on-topic here. Currently the machine translation from western European languages to English is arguably quite robust, with Google ...
2
votes
3answers
90 views

Design patterns for simple text based scripting language?

In my current application I am trying to determine the best way to implement a simple scripting language. This language would allow a user to create a script that controls a machine with various ...
1
vote
1answer
74 views

Information about ε-greedy algorithms

I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms ...
18
votes
0answers
310 views

on “On the cruelty of really teaching computing science”

Dijkstra, in his essay On the cruelty of really teaching computing science, makes the following proposal for an introductory programming course: On the one hand, we teach what looks like the ...
2
votes
1answer
67 views

Robot lawyer algorithm [closed]

I have a background in physics and have taken some few classes online in Machine learning. But I really do not understand how this Robot lawyer can work: A 19-year-old made a free robot lawyer that ...
6
votes
2answers
229 views

Generating constraints to solve dependently-typed metavariables?

In dependent-types, Miller pattern unification is used to solve a decidable fragment of higher-order unification. This allows dependently-typed languages to contain metavariables or implicit ...
3
votes
2answers
56 views

Decomposing a closed walk in a directed graph into cycles

Let's say I have a closed walk $W$ in a directed graph $D$. Represent $W$ as a list of arcs $(a_1, a_2, \dots, a_k)$. Since it's a closed walk, there may be repeated edges, but the source vertex of ...
2
votes
3answers
75 views

Common data structure examples

I recently began working as a tutor with my college, helping younger students struggling in intro classes get their footing. Many of my students particularly struggle with basic data structures ...
3
votes
2answers
64 views

Compare regex in programming languages with regular expression from automata/formal language?

I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages. These two differ not just ...
6
votes
1answer
61 views

Voronoi cells for rectangles

I am looking for a reference on the following variant of a Voronoi diagram: Instead of seed points, there are seed rectangles which are axis-parallel and pairwise-disjoint. Instead of Euclidean ...
4
votes
1answer
24 views

MIS complexity in cubic triangle-free graphs

The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the ...
6
votes
1answer
605 views

Finding a way out of a polygon

There is a simply-connected polygon $C$. It contains $n$ pairwise-interior-disjoint simply-connected polygons, $D_1,\dots,D_n$: The goal is to select one of the polygons, say $D_i$, and attach to ...
4
votes
1answer
128 views

Where can I find information on Data Structures used in common software?

As part of a course I am teaching on Data Structures, I want students to research and present the use of Data Structures in popular software/services. However, basic googling shows me that this ...
7
votes
3answers
231 views

Relationship of algorithm complexity and automata class

I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), ...
2
votes
0answers
18 views

Where does the term “Amechanicity” for type-error generation come from

I've been looking at these slides about improving type error messages for programming languages. One of the things they describe, starting at Slide 8, is the concept of amechanicity. Anytime the ...
3
votes
1answer
111 views

Where can I find an original reference for this integer square root algorithm

As an exercise, I converted an old method I learned for calculating square roots on a rotary decimal hand calculator to binary. I'm sure this is not original; can anyone provide a reference? ...
5
votes
0answers
38 views

Can we simulate any dependent datatype with `Eq`?

Consider the canonical homogeneous equality type: Eq : (A : Set) -> A -> A -> Set, with constructor ...
1
vote
1answer
57 views

Can anybody suggest some algorithms for computing the edit distance other than ‎Wagner–Fischer algorithm? [closed]

I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But ...
3
votes
0answers
38 views

What kind of formal language is generated by Parsing Expression Grammars?

I've been unable to find what language is recognized by PEGs. The original paper[1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also demonstrates how ...
0
votes
1answer
19 views

In terms of the multiplicative constant, what comparison algorithm is fastest in average complexity? [closed]

It is well-known that there is an asymptotic lower bound of $nlogn$ for comparison sorting. However, I am wondering what is the fastest known algorithm for comparison sorting, in terms of the ...
1
vote
2answers
37 views

Random sampling of tuples

When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may ...
8
votes
0answers
72 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
1
vote
1answer
81 views

Maximize ratio of sums

I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$. I would like to select a ...
3
votes
2answers
40 views

Could PRNGs make use of more internal state?

In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing): Pseudo-random number generators (PRNGs) must have a period since they ...
2
votes
0answers
38 views

Constraint solving for scheduling code with complex unspillable register classes?

I'm currently working on a compiler backend for a custom architecture which has some unusual constraints. The architecture has several super-registers with aliasing between the sub-registers, and none ...
0
votes
0answers
28 views

Pointers to schema evolution and semi-automated instance migration

QUESTION EDITED Since this question wasn't clear, I'll rephrase. See question-history for original. I'm looking for academic papers that describe schema evolution on documents (1) in a generic way. ...
1
vote
1answer
61 views

What is the Haskell-style type signature called (i.e., who is it named after)?

A type signature in Haskell is written in the following format: functionName :: (arg1Type, arg2Type) -> returnType There's a (hyphenated, after a person or ...