Newest Questions

Let $L^i=DSPACE[O(\log^in)]$ at every $i\in\mathbb N$ and let $L^1=L$. $st$-connectivity on undirected graphs is $L$-complete (through $L$ reductions) by Reingold's $SL=L$. What is the natural ...

Let $q : \mathbb{N} \to \Sigma^*$ be in $\mathrm{poly}$ (that is, $|q(n)|$ is polynomially bounded; the definition is essentially the good ol' "advice" from $\mathrm{P/poly}$). Also, let $M \...

I'm experimenting with CNF generation using SAT encodings and encountered a very simple tautology that, surprisingly, seems to require exponential time to prove unsatisfiability in practice. The ...

I maintain a directed acyclic graph (DAG) of events in a distributed system of n processes, with these properties: With = n: there are n independent “chains” (one per process). Transitive reduction: ...

Let $A_n \subseteq \mathbb{N}, n \in \mathbb{N}$ be cofinite, but not necessarily computable as a function of $n$. Does there always exist a function $f$ such that $f$ has a polynomial-time Turing ...

Liu and Pass in their 2021 paper "On the Possibility of Basing Cryptography on $EXP \neq BPP$" claim the following : I have a hard time agreeing with Fact 2.1. Reason being it seems to me ...

Suppose we have an undirected graph represented by an adjacency list. In particular, we have full random access, in one step of computation we can access the j-th neighbor of vertex of i. ...

I am trying to prove the following claim: Suppose $G$ is a cograph on $n$ vertices with a hamiltonian path. Then $G$ contains at least $\Omega(n^2)$ edges. In fact, $\Omega(n^{1+\varepsilon})$ would ...

It is known that s–t reachability in directed graphs can be solved in parallel using transitive closure via Boolean matrix multiplication in $O(log^2 n)$ time with $n^\omega$ processors, where $\omega$...

I'm trying to implement a Multiple Object Tracking algorithm based on Quantum Annealing following the approach proposed in this paper by Y. Ihara: Enhancing Multiple Object Tracking Accuracy via ...

Does there exist W[1] hard problems, which are randomized FPT, or would that break the W hierarchy?

I am trying a heuristic approach for solving 3-SAT instances without backtracking. The method relies on an initial variable assignment based on literal signs, followed by a targeted correction phase ...

Given the zig zag product of a graph $G$ with some graph $H$, $G \cdot H$. I want that for any vertices $s,t$ in G, there exists a path between them in $G$ iff there exists some vertices $s', t'$ in $...

Let PIT be the Polynomial Identity Testing. Suppose someone claims that PIT is in P by a simple combinatorial argument. Is there a complexity theoretic result which says that PIT $\in$ P cannot be ...

Among Us Problem: There are $2n$ undercover agents in Don's lair. Fewer than $n$ of them are terrorists, and the rest are anti-terrorists. The identities are top-secret, and no external evidence can ...