Unanswered Questions
490 questions with no upvoted or accepted answers
20
votes
0
answers
712
views
Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?
The following question arose as a side product of some work I have been part of recently.
An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a ...
CommunityBot
- 1
18
votes
0
answers
480
views
In an $m$ by $n$ Boolean matrix, can you find a square block whose four corners are ones in $O(m \cdot n)$ time?
Decision Problem
Input: An $m$ by $n$ Boolean matrix $M$.
Decision Question: Does there exist a square block within $M$ such that upper-left corner entry == upper-right corner entry == lower-left ...
- 5,177
17
votes
0
answers
1k
views
Longest geometrically increasing subsequence
Given a sorted array of $n$ positive integers, the problem is to find the longest subsequence so that the progression of differences between consecutive elements of the subsequence is geometrically ...
- 51.3k
17
votes
0
answers
1k
views
Tiling a rectangle with the fewest squares
Consider this problem: Find a tiling of an $m \times n$ rectangle by minimum number of integer-sided squares.
Is there any polynomial time (in $m$ and $n$) algorithm to do this? What is the best ...
CommunityBot
- 1
16
votes
0
answers
175
views
Is it possible to boost the error probability of a Consensus protocol over dynamic network?
Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
- 19.6k
15
votes
0
answers
464
views
Semiprime factorization, Groebner bases and a Nullstellensatz certificate
Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}...
CommunityBot
- 1
15
votes
0
answers
1k
views
Reference request: a more complete "faster factorization into coprimes"
Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a ...
CommunityBot
- 1
15
votes
1
answer
621
views
Exact Algorithm for edge labeling problem in DAG
I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.
Problem: We are given directed acyclic graph $G=(V,E)$. ...
- 23.4k
14
votes
0
answers
545
views
Is it possible to find the median with a linear size sorting network?
Is there a sorting network that makes only $O(n)$ comparisons and finds the median?
The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
- 14.4k
14
votes
0
answers
364
views
Finding all-pairs anti-distance
Thanks for a great forum. This is my first post here. I am working on a signal processing application and the core of one the main algorithms reduces to a graph theoretical problem.
Let $G=(V,E)$ ...
- 21.9k
14
votes
0
answers
495
views
DPLL and Lovász Local Lemma
Let $\varphi$ be a CNF formula. Suppose that each of $\varphi$'s clauses consist of exactly $t$ literals (and, moreover, all literals within one particular clause correspond to different variables). ...
- 21.9k
14
votes
0
answers
652
views
Approximation algorithm for Minimum Fill-In and/or minimum elimination ordering (for directed graphs)
Recently while working on a problem, I had to go through some of the literature on nested dissection. I happen to have one (maybe two?) questions related to the same.
First, I will define a few ...
- 21.9k
14
votes
1
answer
344
views
Space-approximation Trade-off
In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(...
- 11.2k
13
votes
0
answers
179
views
What is the curve of "search vs. insert"
Consider a collection of numbers (of arbitrary size), and an oracle that is able to accept two such numbers $a,b$ and answer queries of the form $a<b, a>b, a=b$ in constant time.
With this ...
- 379
13
votes
0
answers
198
views
Complexity to compute the eigenvalue signs of the adjacency matrix
Let $A$ be the $n\times n$ adjacency matrix of a (non-bipartite) graph. Assume that we are given the amplitudes of its eigenvalues, i.e., $|\lambda_1|=a_1,\ldots, |\lambda_n|=a_n$, and we would like ...
CommunityBot
- 1