0
votes
0answers
11 views

On derandomizing polynomial identity testing

In polynomial identity testing we seek a deterministic algorithm to infer equality of two polynomials $g,h\in\Bbb Z[x_1,\dots,x_n]$. Derandomizing known efficient randomized algorithms and producing ...
0
votes
0answers
12 views

Finding the maximum flow network and some contradiction claims?

I studying about NP, P and NP-Complete on Computational Course, and get stuck in one definition: we have an example to determine following is in NP or not: ...
0
votes
0answers
11 views

Approximating the clique size of the graph

Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0<\epsilon<1)$, is there any sublinear query algorithm known/possible to decide if the graph has a clique of size ...
-2
votes
0answers
29 views

Computational Complexity of 'Generic'/'Relaxed' Horn SAT [on hold]

Horn (Dual Horn) SAT are described as the SAT with at most one positive (negative) literal. And its in P. What about the complexity of relaxed case of 2-Horn SAT i.e. Each equation has at most 2 ...
-2
votes
0answers
30 views

Is every acyclic subset of edges of a connected graph G=(V,E) part of some spanning tree?

I was thinking of the problem in terms of the matroid polytope and spanning tree polytope. Given a graph $G=(V,E)$, we consider the graphic matroid on this graph. The spanning tree polytope and the ...
1
vote
0answers
14 views

Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition. http://www.sciencedirect.com/science/article/pii/030439759190180A Scott's algorithm on building ...
-1
votes
0answers
31 views

Applicative functors in categorical terms

This is a question related to Explaining Applicative functor in categorical terms - monoidal functors. Why are appl. functors endo? For example, when iterating the Maybe constructor, each category ...
2
votes
0answers
102 views

research papers for undergraduate students

The papers presented at conferences like SODA, FOCS are hard to understand for undergraduates. Also a lot of background knowledge is assumed for understanding such papers. Are there any ...
0
votes
2answers
112 views

Is the Presburger arithmetic decision problem known to be outside of BQP or BPP?

Presburger arithmetic is well-known to be decidable but intractable, requiring doubly exponential time even with nondeterminism (Fischer and Rabin, 1974). I am wondering if it is also known whether ...
-2
votes
0answers
37 views

What format of documentation do computer science majors use? [on hold]

What format of documentation do computer science majors use? Also do you guys make separate versions of documentations for different audiences?
12
votes
0answers
154 views

Is Hankelability NP-hard?

I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet. I am trying to write code to detect if a matrix is a permutation of a ...
-3
votes
0answers
23 views

Method/Algorithm for converting CFL to PDA

What's the general method for converting a CFL to a PDA without first converting the CFL to a CFG? For example how would I convert the CFL {a^nb^m | n ≤ m ≤ 2n} to the corresponding PDA?
-2
votes
0answers
24 views

SSD and DSD on a RBAC [on hold]

Assuming a Static Separation of Duty in a Role Based Access Model: if ( { r1, r2, r3, r4 }, 3) ∈ SSD, are the following UA (user Assignment) valid? UA1 = {(u1, r1), (u2, r1), (u3, r1), (u1, r2), ...
-1
votes
0answers
22 views

finite hypothesis classes which are not PAC learnable

Finite hypothesis class with bounded loss function are PAC learnable. Are there examples for finite hypothesis classes which aren't PAC learnable, if we omit the bounded loss assumption?
6
votes
0answers
63 views

Is $LL(k)$ for large $k$ considered harmful? If so, why?

I took a course touching on lexer and parser theory this semester (a sizeable chunk was devoted to regexes and other FSA, but context-free grammars were covered as well). Over the course of the ...
0
votes
0answers
11 views

3D Bin Packing with one bin with infinite/unknown size

Hi I'm looking for a variation of the Orthogonal 3D-BinPacking algorithm with only one bin of unknown size. I have a set $S$ of $n$ cuboids items $i_j$ with $j=1...n$. The dimensions of the items are ...
2
votes
0answers
42 views

Dynamical systems analysis of deep learning

I am interested in finding out references that apply dynamical systems analysis to develop the "theory" of deep learning, specifically (say) feedforward deep neural nets. The only paper I seem to have ...
5
votes
1answer
76 views

Simple path on dag with backward edges

What is the complexity of the following problem ($\in$ P? NP-hard?): Input: a directed acyclic graph $D=(V,E)$, a set of backward edges $E'\subset V\times V$, and two distinct nodes $s$ and $t$. ...
-3
votes
0answers
15 views

How to make a Weak TimeStamp algorithm? [on hold]

Could someone better explain the weak_ts() timestamp function that appears in the following image? The closest algorithm i found describing a timestamp algorithm is this: But it's not Wait-Free, ...
0
votes
0answers
30 views

Preventing cycling in the simplex method

In Matoušek and Gärtner's excellent book, Understanding and Using Linear Programming, they discuss various pivot rules and in particular ones designed specifically to avoid cycling. Unfortunately, ...
2
votes
0answers
47 views

Is minimizing sum of distances hard?

The Problem Given a set of $n$ points $S = \{v_1, v_2, \cdots, v_n\} \subset \Re^d$, find a unit vector $s \in \Re^d$ such that $s$ minimizes $$ \sum_{i=1}^{n}\sqrt{\|v_i\|^2 - \langle v_i, s ...
-2
votes
0answers
12 views

How many different Huffman encoding for a given number of symbols

In Huffman coding, if we have two symbols to be encoded, we will get the result either 01 or 10. If we have three symbols, we ...
-1
votes
0answers
26 views

PAC learning model definition

The probably approximately correct (PAC) learning model is defined as: A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such ...
-1
votes
0answers
10 views

Estimating the local point density (or sampling frequency) in a point cloud

Let's say we have an unorganized point cloud P1 with N coordinates {x,y,z}. We apply non-rigid transformation to P1 (translation + rotation + warping), to obtain point cloud P2. Given a pair of ...
1
vote
1answer
38 views

Far point queries in high dimensions

Given a set of points $X\subset R^d$ and a number $r\in R$, create a data structure for queries of the form: "given a point $q\in R^d$ return a point $x\in X$ with $\text{dist}(q,x)\ge r$". This is ...
-4
votes
0answers
20 views

How can I convert the following recursive top down DP code into bottom up iterative? [on hold]

I have code that calculates binomial distribution, and I have been stuck trying to figure out how to convert it into an iterative equivalent. ...
4
votes
0answers
40 views

Second Smallest $s$-$t$-Cut in a Network

Is anything known about the second smallest $s$-$t$-cut in a flow network? Or, more general, about this problem: Input: A network $N$ and a number $k$. Output: An $s$-$t$-cut whose capacity ...
7
votes
2answers
74 views

Separating lists of words

There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate" them, ...
-1
votes
1answer
19 views

M/G/$\infty$ queue with mixture of deterministic service times

Hey guys I am studying queueing theory and I am trying to understand this problem. Consider an $M/GI/ \infty $ queue with the following service time distribution: the service time is $1/\mu_i$ with ...
7
votes
0answers
179 views

Is the complexity of this covering problem known?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
6
votes
0answers
86 views

Problems in BQP but conjectured to be outside P

Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain ...
4
votes
1answer
102 views

Simple candidates for pseudorandom permutations?

Even though it is not known whether one-way functions exist, there are several candidate functions used in practice for cryptographic applications that are efficiently computable but are conjectured ...
3
votes
1answer
178 views

#P- vs PP-Completeness

Suppose $A$ is any #P-complete problem. Now, $A$ is modified to obtain a decision problem $A'$ not by asking whether there is a solution but whether at least half of the potential solutions are ...
5
votes
1answer
162 views

Easy decision hard counting Parametrized

It is known that counting perfect matchings in a bipartite graph is #P-complete. On the other hand, finding a perfect matching belongs in P. Is there a problem, that exhibits the same behavior in ...
-4
votes
0answers
41 views

linear programming relaxation for set cover [on hold]

according to this stanford lecture and wikipedia the approximation ration is log(n) but what is the base of the logarithm? I assume it is 2. so does that mean that it is worse than the greedy ...
-2
votes
0answers
35 views

what are some real world applications for set cover? [on hold]

does the set cover proplem has intesting real world direct applications. according to Wikipedia it is related to many other interesting problems. but I was wondering if it has direct applications.
-2
votes
0answers
31 views

“Accelerated” Ray Tracing [closed]

I want to create "accelerated" ray tracing. I want recommendations about great courses or books about data structures and algorithms which can provide me enough knowledge so that I can implement my ...
-2
votes
0answers
26 views

Terminology for a graph with ports on its nodes [closed]

A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain ...
4
votes
0answers
82 views

Rigid families of $\{0,1\}$ matrices

We know that there are many families of matrices over $\Bbb F_q$, $\Bbb R$ etc are rigid. See http://mahdi.cheraghchi.info/talks/rigidity_talk.pdf Do we know there are many families of rigid REAL ...
-1
votes
0answers
39 views

Polynomial time RSA decryption if m mod N > N/2 is decidable [closed]

Suppose I have the three tuple (m^e mod N, N, e) where m is the message and N is the product ...
4
votes
1answer
105 views

Special properties of bipartite expanders

It is well known that expanders, and often the special case of bipartite expanders, have found many uses in derandomization, coding, etc. However, I am curious if there are any special properties of ...
2
votes
1answer
109 views

Preferable way to express $O(n2^n)$

Is it preferable to write $O(n2^n)$ or $O((2 + \epsilon)^n)$? If neither, what is the best way? Since I see a lot of papers with $O(1.42^n)$ instead of $O(2^{\frac{n}{2}})$ and similar ...
-3
votes
0answers
20 views

If I know f(P) do I know f(P') if P' is the inverse of P? [closed]

Given that there is a function F for finding the shortest path between two points (from a set of paths P). Is the following a cogent procedure for finding the longest path. Whereas shortest is the ...
0
votes
0answers
52 views

Is there a reduction from a 0-1 knapsack problem to the unbounded problem?

As we know, an unbounded knapsack problem could be described as: $\max \sum_{i=1}^nc_1x_i$ s.t. $\sum_{i=1}^na_ix_i\le b$ $x_i\ge0,x_i\in\mathbb Z,i=1,\cdots,n$ And for an 0-1 knapsack problem, we ...
5
votes
1answer
85 views

When does automaton stay unchanged after string homomorphism?

Suppose we have a string homomorphism $\varphi: \Sigma \rightarrow \Sigma^*$. Consider the languages in $\varphi(\Sigma^*)$ whose letters are elements of $\varphi(\Sigma)$, so here I do not want to ...
-1
votes
0answers
53 views

A Turing Machine with noncomputable halting problem is universal [closed]

Claim: If $M$ is a Turing machine such that $\{w\mid M\mbox{ halts on }w\}$ is not computable, then $M$ is universal. Although I'd like to conjecture that this is true, I expect that we don't ...
0
votes
1answer
115 views

What is the intuition behind “hardness of approximation”? [closed]

I am reading a paper about graph matching problem. Which is, to some extent, an optimization version of the graph isomorphism problem. To my surprise, some closely related NP-hard problems are quite ...
0
votes
1answer
283 views

On straight line factorial calculation [on hold]

If there is no straight line program that uses at most $\log^c n$ constants for a fixed $c$ to compute $n!$ in at most $\log^d n$ steps for a fixed $d$, then $\mathsf{P}_\Bbb C\neq\mathsf{NP}_\Bbb C$. ...
-2
votes
0answers
87 views

A 2-state Turing machine complete catalog?

I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a multiplicity of criteria. Including ...
2
votes
0answers
54 views

Johnson Lindenstrauss for Random variables?

Does the Johnson-Lindenstrauss Lemma apply to any finite-dimensional Hilbert Space? In particular, I am interested in the space of random variables $X = (X_1,...,X_N)$ over $N$ uncertain states. If ...

15 30 50 per page