# All Questions

10,747 questions
Filter by
Sorted by
Tagged with
30 views

### Neighborly properties in a bipartite graph

Input: Let $G$ be a connected, bipartite graph with parts $A$ and $B$, each of size $n$. For $S\subseteq A$, let $N(S)\subseteq B$ be the set of neighbors of $S$ in $B$. Similarly, for $T\subseteq B$, ...
33 views

### Diffie Hellman theory

A friend sent me a question about Diffie Hellman and I can't seem to figure it out, maybe someone here can help. Let G be a finite cyclic group (for example, G = Z*p), with a generator g. Suppose that ...
32 views

### Uniquely 4-colorable Maximal Planar Graph Conjecture?

My question is on Uniquely 4-colorable Maximal Planar Graph Conjecture mentioned in On purely tree-colorable planar graphs (and other papers of same(?) team such as "Theory on Structure and ...
163 views

### 3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” by Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
432 views

### Optimization Problem on a Directed Graph

I have the following graph optimization problem. In a directed graph $G$, each node $i$ is endowed with a real value $v_i$ (input) that encodes the minimum "activation threshold" of that node. For ...
41 views

33 views

### Non-rigid isomorphic structures

In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
198 views

### Can modern SAT-Solvers utilise the symmetry of First Order Logic?

Apologies if the question is trivial or is wrongly stated, I am a Physicist! Assuming that we have a universally quantified first-order logic sentence, all variables are universally quantified, ...
123 views

### Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

Let $\mathcal A$ be an automaton, then I define the following $\omega$-language accepted by $\mathcal A$:  L'(\mathcal A) := \{ \eta \in X^{\omega} : v \sqsubset \eta \mbox{ implies } v \in L(\...
188 views

### Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

Consider a deterministic transition structure having states in set $X$ and transition function $\rightarrow$, and an initial state $x \in X$. This structure is intended to be part of an automaton ...
579 views

### Regular safety properties and bad prefixes of $\omega$-regular properties

I have two questions: By starting with a nondeterministic Büchi automaton (NBA) $\mathcal{A}^{\varphi} = (Q, \Sigma, \rightarrow, I, F )$ for an $\omega$-regular property $\varphi$, we can construct ...
202 views

### Complexity of DBA-recognizable Omega-Languages

Given an $\omega$-regular expression $r$, how difficult is it to decide if $L(r)$ is recognizable by some deterministic Büchi automaton? I know it is solvable in EXPTIME by converting the regular ...
709 views

### Continued Fraction Algorithm in Shor's Algorithm

I am just trying to make the final link of Shor's algorithm clear. Here $r$ is the order of $x$ modulo $N$. We have a number $\psi$, which for a rational number $\dfrac{s}{r}$ satisfies \begin{...
326 views

### Complexity relative to the graph of the Busy-Beaver function

This question is inspired by the comments made on this other question that I asked, and by an attempt to provide an explicit example of a complexity question beyond the Turing degree $\mathbf{0}$. (...
15 views

### Universal Generalisation Inference rule over array Proprties

I have a question about the soundness of the Universal Generalization Rule Over array Properties in proof i am working on To give some hints about the problem: suppose that $f(x)$ and $g(x)$ represent ...
130 views

### What is the complexity of this submatrix selection problem?

We have a $kn\times kn$ matrix $M$ made of $n^2$ many $k\times k$ blocks. We want to find an $n\times n$ submatrix such that each row and column is from distinct window of size $k$ such that the sum ...
30 views

### Reduce a decision problem to an optimization problem

In this paper, the author shows that finding an edge coloring that minimizes the total sum on a multi-tree is NP-hard. In theorem 3.1, the author does so by reducing from 3SAT. I find his proof quite ...
67 views

### Minimizing the gaps with incremental capacity

There are a single job, a machine and a set of $n$ slots. The machine has a capacity that increments by $\zeta(t)$ every slot $t=1,2,\ldots,n$. Initially (before the first slot), the machine has 0 ...
58 views

### Is there an official/academic name for the “current value” in a loop? [closed]

This is a question about semantics/vocabulary. I don't like saying "the current value you are looping over/on". I'm wondering if there is a better term.
203 views

### Counting words of length $n$ in an inherently ambiguous CFG?

There is a polynomial-time algorithm for computing the number of words of length $n$ in an unambiguous CFG $G = (V, \Sigma, R, S)$ (via a dynamic programming approach). However, for ambiguous CFGs, ...
23 views

### Any reason why Turing Machine would prevail on recursion theory? [migrated]

Nowadays, most introduction books, videos, and comments about theoretical computer science talk about Turing machines but don't discuss recursion theory anymore. These approaches are known to be ...
337 views

### Is it possible to infer on the thermodynamics of two problems if a reduction from $B$ to $A$ exists?

Peter Shor commented on this post: years of experience in theoretical computer science says that the thermodynamic behavior of two NP complete problems are in general not similar. What can we say ...
2k views

### How to write the introduction of a research paper?

Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.
973 views

### Isn't it “trivial” to represent/reduce any classical physics problem into a Spin-Glass which is NP-Complete?

In the late 80's there were several highly cited efforts to use Spin-Glass models to formulate other computational problems such as: Protein Folding and Neural Networks. Isn't it straight forward to ...
95 views

### Application of Yao's Minmax Principle for Adaptive Randomized Algorithms

Reference Request: I am interested in references where Yao's Minimax Principle is applied for adaptive randomized algorithms if any. More generally, I am interested in minimax lower bound results for ...