All Questions

Filter by
Sorted by
Tagged with
4
votes
0answers
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$, ...
-3
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
2answers
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 ...
3
votes
2answers
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 ...
3
votes
0answers
41 views

Complexity of finding the mean of the subset with smallest variance

Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer. Let's consider the following problem $\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\...
6
votes
2answers
347 views

Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
5
votes
1answer
93 views

An efficient Beta-Equivalence algorithm?

Is there an efficient algorithm to determine if two terms are beta-equivalent? I'm specifically curious about simply-typed-lambda-calculus, so you can assume both terms are strongly normalizing. I ...
1
vote
1answer
57 views

Delaunay triangulation when some triangles have been pre-specified?

I have an implementation of the Bowyer-Watson algorithm for Delaunay triangulation which works well -- given a set of 2D points, it computes a set of triangles to fill the areas between the points. ...
87
votes
9answers
15k views

What would it mean to disprove Church-Turing thesis?

Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why? Turing, Rosser etc ...
-1
votes
0answers
22 views

Online to batch sample complexity. Conservative assumption on online algorithm needed?

To the best of my knowledge, typical approaches to convert an online algorithm with mistake bound into a batch algorithm with PAC bound make the following assumption. A1: The online algorithm is ...
1
vote
0answers
51 views

Constructing FOL formula for which counting is easy?

Given a function free First Order Logic language $\mathcal{L}$ are there ways to write formulas for which counting the number of models for a given cardinality of the domain is easy (preferably exists ...
-3
votes
0answers
33 views

What exactly is automata theory and formal language? [closed]

I'm a beginner in this course . I searched online and read introductory chapters of a few textbooks but it is still not clear to me what exactly automata theory and formal language is. Why do we study ...
32
votes
3answers
2k views

Is this variation of TQBF still PSPACE-complete?

Deciding if a quantified boolean formula such as $\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$ always evaluates to true is a classical PSPACE-complete ...
12
votes
2answers
780 views

What is the proof of this nonstandard version of Azuma's inequality?

In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality: Let $C_1, \dots, C_k$ be real-valued ...
5
votes
1answer
115 views

Good Survey paper for k-means/k-median/k-center/facility-location

I have stated 4 problems in the Question title. All these problems are closely related and are studied in various variations. For example: Space: Euclidean/metric/discrete/continuous/non-metric/2-...
-1
votes
1answer
89 views

What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different. What evidences are there that $PP$ is in $BQP$? What evidences are there that $PP$ is not ...
-1
votes
2answers
97 views

Understanding definition of #P

Valiant defined $\#P$ in terms of a counting TM, which is a NTM that outputs the number of solutions [1]. I am a bit stuck with the following two questions: Let's say I have a decision problem $X$, ...
9
votes
3answers
616 views

Number of connected components of a random nearest neighbor graph?

Let us sample some big number N points randomly uniformly on $[0,1]^d$. Consider 1-nearest neighbor graph based on such data cloud. (Let us look on it as UNdirected graph). Question What would the ...
8
votes
1answer
129 views

Recent progress on the next-to-shortest-path problem for directed graphs?

In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem: Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be vertices in ...
2
votes
0answers
63 views

Tail bounds for sum of weighted Poisson random variables

Let $X_1,X_2,\ldots,X_n$ be $n$ independent Poisson random variables with $\mu(X_i) = \lambda_i$. I am interested in upper tail bounds for the random variable $Z = \sum_{i} a_i X_i$ where $a_i \in [0,...
1
vote
0answers
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 ...
4
votes
1answer
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, ...
4
votes
1answer
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(\...
6
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
3
votes
2answers
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{...
12
votes
2answers
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}$. (...
-1
votes
0answers
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
0
votes
1answer
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 ...
-2
votes
1answer
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.
6
votes
1answer
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, ...
-1
votes
0answers
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 ...
5
votes
1answer
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 ...
19
votes
1answer
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.
8
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
71 views

Data processing inequality for interaction information

The interaction information is defined as $I(X;Y)-I(X;Y|Z)$. Let $Z-(X, Y) -(X', Y')$ be a Markov chain. Is there an inequality similar to the data processing inequality, relating $I(X';Y')-I(X';Y'|Z)...
7
votes
2answers
326 views

Most general setting for fine-grained exponential-time complexity classes?

Consider the class of functions computable in time $(b+o(1))^n = 2^{\log_2{(b)} \times n + o(n)}$ on a $2$-tape Turing machine. By the Hennie-Stearns theorem, the same functions are computable in ...
-1
votes
0answers
38 views

Applied Pi calculus: Evaluation context that distinguishes replication with different restrictions

For an exercise, I need to find an evaluation context $C[\_]$ s.t. the transition systems of $C[X]$ and $C[Y]$ are different (=they are not bisimulation equivalent), where $X$ and $Y$ are the ...
9
votes
6answers
14k views

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
6
votes
0answers
92 views

Enumerating homologies of disjoint paths

I am reading this recent paper by Schrijver, in particular, section 4.2: Enumerating homologies of disjoint paths. I did not understand how do they re-route the paths through a spanning tree and ...
2
votes
1answer
98 views

Who proved that a triangulation is 3-colourable implies its dual is bipartite

Let $G$ be a maximal planar graph (also called a triangulation); i.e, $G$ is a planar graph every face of which is a triangle. It is well known that the following three statements are equivalent: (i) $...
-2
votes
1answer
70 views

Beta reduction and vacuous lambda abstraction [closed]

Suppose we have the following typed lambda term (where $s$ does not occur in E (which is of type $s \to p$) and $s$ and $s'$ have the same type), and want to apply $\beta$-reduction: $(\lambda s. E)\, ...
0
votes
0answers
69 views

Why is it difficult for GCT to prove super quadratic lower bound?

We have a quadratic lower bound for the Permanent Determinant problem. Why is it difficult for GCT to improve it?
0
votes
0answers
36 views

Self Generating Grammars - Does it have to be infinite recursion?

For brevity, let's redefine a grammar to be just the three-tuple $(\Sigma_G, P_G, S_G)$. As usual, $\Sigma_G$ is the alphabet, $P_G$ are the production rules and $S_G$ is the start rule of $G$. For ...
-1
votes
1answer
94 views

Required sample size to hit certain subset of a ground set

Suppose $X$ is a set of $n$ points in $\mathbb{R}^d$ and $N_1,\cdots,N_k$ are k disjoint (unknown)subsets of $X$. There is a probability distribution $\phi$ on $X$ defined as $\phi(p) = \frac{\lvert\...

15 30 50 per page
1
2 3 4 5
215