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

learn more… | top users | synonyms

1
vote
0answers
36 views

Is this financial problem studied?

We are given a directed weighted graph $\mathcal{G} = (V, A)$, with $A \subseteq V^2$. The weight function is $w_{\mathcal{G}} \colon \mathcal{G}.A \to \mathcal{P}(\mathfrak{R}_{>} \times \mathfrak{...
2
votes
0answers
39 views

ORAM: Is it generic?

Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independent of ...
5
votes
2answers
65 views

Online sorting without modifications

There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random). Whenever a number arrives, we must put it ...
2
votes
1answer
181 views

Converting a non-planar graph to planar

Suppose that we have a non-planar graph $G$ which is undirected and connected. Our aim is to remove a set of edges and/or a set of vertices and convert make $G$ planar while keeping the connectedness. ...
7
votes
2answers
169 views

Type-system combining type-states and typed effects?

Has anyone succeeded in implementing or designing a type-system that combines both type-state (linear types) and effect types (e.g. Koka)?
2
votes
2answers
265 views

Is this probability distribution data structure already discovered?

Problem formulation I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, ...
0
votes
1answer
41 views

About the MNIST data-set

Is this known as a fact or from some analysis that the MNIST data-set is almost as if its sampled from some low (~10?) dimensional manifold? Is there a locally linear embedding to a low-dimensional ...
3
votes
1answer
40 views

Single-source shortest path algorithm for graphs representing stacked behavior

I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG). That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent ...
7
votes
1answer
190 views

Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
1
vote
1answer
20 views

Good resources for understanding semidefinite relaxation for combinatorial problems

I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as ...
0
votes
0answers
12 views

Advice on using DRAMSimm2 or other DRAM simulation tools

As part of my PhD research I am currently building a simulation of a 256 core NoC and really want to model its interaction with the memory system. My supervisor has suggested using the University of ...
1
vote
0answers
18 views

When was manual dynamic memory managment introduced?

Original Fortran only had static memory. Algol introduced stack allocation. Lisp had Garbage Collection. But when where manual dynamic memory management such as in C introduced. In C memory can be ...
2
votes
0answers
27 views

Computational complexity of logistic map

My question is pretty simple and to the point. Is there a known way to efficiently compute logistic maps to within a specified precision? In other words, the input is a value $x$ and integers $d,n$; ...
3
votes
0answers
30 views

How to show that an MINLP with L0 regularization is NP-hard?

I am currently working on a project that involves a mixed-integer non-linear optimization problem, and wondering if I can state that this problem NP-hard in a research paper. I'm not looking for a ...
3
votes
0answers
59 views

Find internal surfaces in an oriented mesh

I have a solid with internal holes. My solid is mostly a union between walls/floors/ceilings. Each of them is a mesh with polygons oriented counter-clockwise. Then with those polygons I do a union ...
0
votes
0answers
18 views

Parallel Machine Scheduling test data

I am writing optimization program for unrelated parallel machine scheduling problem on CUDA. Now, the only thing I am missing are some test cases. Does anyone know where I can find such data? I have ...
3
votes
0answers
32 views

Is this a known question in matrix sketching?

Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m << D $ dimensional columns ...
3
votes
0answers
62 views

Name for a class of problems solvable in $n^{O(\log \log n)}$

Isomorphism testing of projective planes can be done in $n^{O(\log \log n)}$. This class is contained in quasi-polynomial time. I would like to know more about this class and natural problems in it. ...
4
votes
0answers
16 views

Busy Beaver machines on semi-infinite tape

The Busy Beaver problem is to find the largest number of non-blank characters that are printed by a terminating Turing machine of no more than a given size on the blank input. The usual Busy Beaver ...
1
vote
1answer
30 views

Find Correlations in Vectors of symbols

Given a set of vectors, lets say that each coordinate is populated from an alphabet (meaning set of symbols, numbers, etc) (particular or shared alphabets are indistinct). Is there any standard ...
3
votes
2answers
50 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
2answers
110 views

How similar are two DFAs? -not just binary equivalence-

Are there any measures to compute similarity (or distance) between two DFAs? If yes, which are the main references? I need a measure of similarity, not only a (binary) equivalence test. "Similarity"...
6
votes
0answers
127 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
102 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
113 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
41 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 ...
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
49 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
62 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
29 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
27 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
22 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
60 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
77 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
121 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
31 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
38 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 ...
3
votes
0answers
43 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
106 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
76 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 ...
21
votes
0answers
388 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
70 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
232 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 arguments....
3
votes
2answers
62 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
81 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
67 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 ...