# Tagged Questions

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

36 views

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{... 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 ... 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 ... 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. ... 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)? 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, ...
41 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$; ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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"...
127 views