Questions tagged [open-problem]

Problems known to be open in the literature and any problem that, after being posed, is decided to be open by the community.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
28
votes
0answers
644 views

The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
22
votes
0answers
887 views

$\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years. You may recall that Hoffman and ...
19
votes
0answers
576 views

Identifying Reducible/Irreducible polynomials over $Z[x]$

It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$. Say one only seeks to identify whether a given polynomial over $\...
16
votes
0answers
428 views

Is graph coloring complete for poly-APX?

Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
14
votes
0answers
266 views

Any example of an unsatisfiable integer program with non constant Rank Lower bounds for LS+ cuts but with short LS+ refutations?

Assume we want to refute an unsatisfiable CNF. We can interpret it as an integer program, thus a refutation can be done by applying Lovasz-Schrijver semidefinite cuts ($LS_{+}$ cuts) to its linear ...
13
votes
0answers
706 views

Online algorithms: open problems

Recently the long-standing k-server problem has been solved by Nikhil Bansal, Niv Buchbinder, Aleksander Mądry and Seffi Naor (to appear in FOCS 2011). I'm interested in knowing other open problems in ...
11
votes
0answers
255 views

What are the most recent developments in small-depth quantum circuits?

Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge: The power of small-depth quantum circuits. Is $BQP = ...
10
votes
0answers
235 views

Complexity of the min edge-colored cut problem

Given an undirected graph $G=(V,E)$ with a color on each edge, the problem is to find a 2-partition $(V_1,V_2)$ of $V$ s.t. the number of colors used by the edges $uv, u \in V_1, v \in V_2$ is ...
6
votes
0answers
565 views

Does PEG contain CFG?

Despite their considerable expressive power, all PEGs can be parsed in linear time using a tabular or memoizing parser (8). These properties strongly suggest that CFGs and PEGs define incomparable ...
5
votes
0answers
329 views

Complexity of balanced graph partition problem

Wagner and Wagner, in "Between min cut and graph bisection" (MFCS 1993), studied a variant of minimum bisection problem where we seek a cut with minimum size such that each partition has at least $\...
4
votes
0answers
101 views

Open Problems About Nowhere-Dense Classes of Graphs

I'm writing a survey about nowhere-dense graphs. I would like to list some of the main open problems in the field. In particular I would like to list problems of the following form. The problem has ...
3
votes
0answers
276 views

Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other ...
2
votes
0answers
60 views

Complexity of comparing extended integer power towers

Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
1
vote
0answers
51 views

Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

I am wondering if this is a topic that has had research done... If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring ...
1
vote
0answers
126 views

Noisy channel coding theorem in Quantum information

Why Shannon's noisy channel coding theorem can't be used for Quantum communication applications? Schumacher proved the first Noiseless theorem and there are quantum error correction mechanisms out ...