# All Questions

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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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?
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), ...
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?
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 ...
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 ...
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 ...
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$. ...
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, ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$. ...
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 ...