# All Questions

2,950 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
474 views

### Looking for a quotation by Edsger Dijkstra

In one of his papers Edgser Dijkstra makes a statement like: "What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
168 views

### Minimal rare subgraphs

I am looking for any related work to the following problem. Say you have a large directed graph $G$ and you want to find rare (or unique) subgraphs of minimal size that are not isomorphic to any other ...
610 views

### Known upper bounds on the communication complexity of Karchmer-Wigderson games

In 1988 Karchmer and Wigderson established a nice characterization of the circuit depth $d$ (DeMorgan circuits) of a Boolean function $f \colon \{0,1\}^n\rightarrow\{0,1\}$: $d$ is exactly the number ...
316 views

### Survey on infinite alphabet automata?

The paper "Symbolic Finite State Transducers, Algorithms and Applications" by Bjorner et al (to appear at POPL 2012) describes one type of finite-state, infinite-alphabet automata/transducers by using ...
335 views

### Directed Sparsest Cut on Planar Graphs?

The (uniform) directed sparsest cut problem asks for a cut $(S,\bar{S})$ in a directed graph $G=(V,E)$ which minimize the ratio $\frac{\delta_{out}(S) }{|S||\bar{S}|}$, where $\delta_{out}$ is the ...
219 views

### Combinator logic and unification

Summary: if we are trying to use combinator logic to solve first-order logic type problems, is the best method to feed in free variables and use the standard first-order unification algorithm? In ...
270 views

### Conditional density of primes

We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem. My question is about the density of primes when we choose random numbers from a ...
891 views

### Enumerating topological sorts of a vertex-labeled DAG

Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
317 views

158 views

### Generating a random graph with constraints on spectrum

Consider two sequences $u_1 \geq u_2 \geq ... \geq u_n$ and $l_1 \geq l_2 \geq ... \geq l_n$ with $u_i \geq l_i$ for every $i$. Let $\mathcal{G}(l_{1:n},u_{1:n})$ be all undirected unweighted simple ...
3k views

### Eliminate ambiguity from CFG

CFG here stands for context-free grammar. I understand that: Deciding whether a CFG $G$ is ambiguous is undecidable. Deciding whether a CFL $L$ is inherently ambiguous is undecidable. My question ...
263 views

183 views

### generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits

In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their ...
427 views

### Cheeger's inequality for directed graphs?

Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
239 views

### Inapproximability of multiterminal cut

In the multiterminal cut the input is a graph $G$ and a subset $T$ of its vertices. The task is to remove the minimum number of edges from $G$ such that there is no path connecting any distinct ...
1k views

### Complexity of finding the leading eigenvector of a graph Laplacian

Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$? Are there any families of Laplacians for which it takes ...
358 views

### Is Bayesian updating computationally unfeasible?

Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be ...
331 views

### Is there a P-complete problem on diophantine equations?

In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-...
514 views

### Matrix rigidity and uses of matrices with low rigidity

Roughly a matrix of rank $n$ is said to be rigid, if to bring its rank down to $\frac{n}{2}$, one has to change at least $n^{1+\epsilon}$ of its entries, for some $\epsilon > 0$. If an $n \times n$...
542 views

### What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?

I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? ...
142 views

### Provable BPP Hierarchy

No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition: A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
130 views

### Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?

Planar graphs are 4-colorable. Determining if a planar graph is 3-colorable is NP-Complete. A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable. ...
254 views

### Does MIP* = RE algebrize?

Does the MIP* = RE result algebrize? (It doesn’t relativize, as noted here.) If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?
150 views

### Alternative proofs of Savitch's theorem?

Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one? By the usual one I mean the proof based on recursively querying whether there is a midpoint. ...
149 views

### Is counting the total number of faces of a polytope $\#P$ hard?

Let $P$ be a polytope defined by $Ax = b, x \geq 0$. Question: What is the complexity of computing the total number of faces of $P$? I know counting vertices is $\# P$-complete, but this problem is ...
202 views

I have found the following question at openproblemgarden.org: The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the ...
166 views

### Descriptive Complexity characterzation of BPP

We know of descriptive complexity characterizations of classes such as P, and NP, which use First Order logic, and operators. Does BPP have a characterization under descriptive complexity, too(any ...
124 views

### Diameter of “almost” always connected Erdős-Renyi graphs

Let $G=(V,E)$ be a random Erdős-Renyi Graph, i.e., $G\in\mathcal{G}(n,p)$. It is well known that if $p=(\log n +c +o(1))/n$ with $c\in\Re$ then $$P(G \text{ is connected})=e^{-e^{-c}}\ .$$ However, ...
### Complexity of checking $a > br^m + cr^n$, with $r$ rational
I'm wondering if the following problem is decidable in P-time (or even NP): Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where \$r = {p ...