# Tagged Questions

2answers
163 views

### Is this problem on weighted bipartite graph solvable in polynomial time or it is NP-Complete

I encounter this problem recently and I want to know whether it is NP-Complete or solvable in polynomial time: Given a undirected weighted bipartite graph $G = (V, E)$ where $V$ can be partitioned ...
0answers
162 views

### Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
0answers
139 views

### Is finding a single vector in the null space as difficult as discovering the whole null space?

Let $A \in \mathbb R^{k\times n}$ be a matrix of rank $k$, where $k \ll n$. One can use Gaussian eliminations to discover $\operatorname{null}(A)$ at the cost of $O(nk^2)$. My question is: Is the ...
1answer
529 views

### Can the Legendre symbol be calculated in polynomial time?

Is there an algorithm which on input "$(a,p)$" (where $0\leq a<p$ are integers) takes time polynomial in $\log p$ and outputs "NOT PRIME" if $p$ is not prime and otherwise outputs the Legendre ...
1answer
35 views

2answers
164 views

### Determination of rationality and computing a rational parametrization

Suppose I have a hypersurface in $\mathbb{C}P^n$ given by some $f(z_1, \dots, z_{n+1}) = 0.$ Is there an algorithm which returns a rational parametrization if there is one, and "not rational" ...
1answer
2k views

### How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...
0answers
76 views

### Deciding / Approximating Parity of Small Depth Decision Trees

Let C be a circuit such that: C: $\{0,1\}^n$ to $\{0,1\}$ the top most gate is a parity gate all the inputs to the parity gate are small depth decision trees there is a total of $2^{ log^k n}$ ...
3answers
1k views

### How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}} Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise. Example: Input ...
3answers
275 views

### Generating a set of integer passwords that can be securely authenticated

First, apologies for the title. This is an odd question, and I couldn't come up with a simple title for it. My question is as follows. Given a positive integer $k$, determine a set of properties ...
1answer
547 views

### Lovász $\delta$ condition for LLL Algorithm

http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm What is the importance of the $\delta$ parameter for LLL bases called LovĂĄsz condition? ...
0answers
597 views

1answer
2k views

### Evidence for integer factorization is in $P$

Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
1answer
813 views

### Finding a vertex of least distance to all other vertices in a graph

Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the ...
2answers
208 views

### Formal verification in complexity theory

Reading books and papers on complexity theory, I am struck by the extreme degree to which proofs are stated in an intuitive, hand-wavy way. The alternative is to give a lot of details about the coding ...
3answers
675 views

### Definition of relativization of complexity class

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$? Usually, these classes and their relativizations seem to be defined in an ad-hoc ...
0answers
338 views

### Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of ...
0answers
274 views

### Amortized analysis of data structure via potential function

One common method for proving that a data structure supports an operation in $O(f(n))$ amortized time is to construct a potential function $\Phi: \mathcal S \rightarrow \mathbf R^{+}$, which ...
1answer
262 views

### Computing Simultaneous Hamming Neighborhood for a Set of Strings

Let $S = \lbrace s_1, s_2 \ldots s_n \rbrace$ be a set of strings each of length $k$ from an alphabet $\Sigma$, $h(s_i, s_j)$ denote the hamming distance between two strings. The simultaneous hamming ...
3answers
647 views

### SDP Feasibility

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...
2answers
1k views

### Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...
3answers
2k views

### Worst known algorithm in terms of Big-O (more precisely Big-theta)?

Hello, I have been trying to find the worst algorithm in terms of it's Big-O function. By worst I mean n! is worse than n^2, n^n is worse than n!, etc. Essentially the worst algorithm would be the ...
1answer
280 views

### Computation for composition of polynomials

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha)$ in $O(n)$ ...