All Questions

8
votes
0answers
100 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, ...
0
votes
0answers
151 views

On planar $4$ regular graphs

It is $NP$-hard to decide if a $4$-regular planar graph can be $3$-colored. Is an exact algorithm possible that under uniform distribution is in average polynomial time?
4
votes
2answers
746 views

Attempted proofs of P vs NP

What are the most recent (say in the last 3 years) attempts at disproving $P = NP$, and where can I find the papers?
1
vote
1answer
85 views

How many samples are needed to reconstruct a path?

Consider an input set of vertices $V$ and vertices $s,t\in V$. The goal is to learn some unknown shortest path from $s$ to $t$; the set of edges of the graph is hidden at first and there may be ...
3
votes
1answer
67 views

Agnostic query learning for DFAs

Angluin's membership+equivalence query algorithm allows to efficiently and exactly learn a target $n$-state DFA. But what if the target DFA is huge, or the target concept is not even a regular ...
2
votes
0answers
28 views

A Context-Sensitive Grammar which cannot be recognised by a Parsing Expression Grammar

It is (currently) an open question of whether every context-free grammar can be recognised by some parsing expression grammar. [1] However, has it been proven that there exists an example of a ...
-1
votes
0answers
61 views

Validity of relativization argument

In the book 'Computational complexity' by Arora-Barak, I was studying that any result of TM/ complexity classes that use only the following two properties of TM's are called relativizing results : $I....
1
vote
0answers
119 views

Can a hash preimage be used to amplify BPP probabilities?

Suppose we have an algorithm in $\mathrm{BPP}$ to decide membership in a language $L$. Normally we amplify the probability of accepting and rejecting members correctly by running our algorithm ...
1
vote
1answer
106 views

Is the unbounded fan-in model realistic?

Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates? As I understand, standard silicon ASICs ...
5
votes
0answers
48 views

Hardness result or reference for optimal Gaussian elimination process

I'm wondering if the following problem is NP-Complete or has any hardness result. References on related problem are also welcome. Input: integers $n\geq1,k\geq0$ and an invertible matrix $M\in\...
2
votes
0answers
39 views

Counting matchings on 3-regular bipartite graphs

What I call a graph here allows parallel edges. Is the following problem #P-hard: INPUT: a 3-regular bipartite graph $G$ OUTPUT: the number of matchings of $G$. It is known that counting matchings ...
-4
votes
0answers
54 views

An instance of Sudoku that can be solved in poly-time, but is it ASP-complete?

Another Solution Problem (ASP) of a problem ƒ is the following problem: for a given instance x of ƒ and a solution s to it, find a solution to x other than s. x = poly-time solvable puzzles s =...
-1
votes
1answer
84 views

Comprehensive list of functions used in Big-$O$ notation

We all know that exponential functions grow faster than polynomials. Let us consider the following function: $f(n)=n^{a_1}⋅(\log n)^{a_2}⋅(\log\log n)^{a_3}⋅(\log\log\log n)^{a_4}⋯ $ where the leading ...
18
votes
3answers
2k views

Why colon to denote that a value belongs to a type?

Pierce (2002) introduces the typing relation on page 92 by writing: The typing relation for arithmetic expressions, written "t : T", is defined by a set of inference rules assigning types to ...
-1
votes
0answers
17 views

How to deal with tradeoffs while making choices?

Sometimes while writing some code I make some decisions, the "problem" is that every choice has a negative consequence. Is coming with the perfect architecture possible? You'll tell me; perfect ...
1
vote
1answer
55 views

How to play the following game? (placing balls into bins)

Let $n,\ell\in\mathbb N$ for some $n\gg \ell\gg 1$. The goal is to pick two sequences of numbers, $x_1,\ldots,x_\ell$ and $y_1,\ldots,y_\ell$ such that $$\Sigma_{i=1}^\ell x_i = n\quad{}\mbox{and}\...
2
votes
2answers
190 views

Under what models do we know linear time sorting?

The best we know for general case sorting is $O(n\log n)$ (which is also $\theta(n\log n)$ is decision tree model) and the problem of $O(n)$ sorting is open for turing machine models. Under what ...
0
votes
0answers
31 views

2D-Interval partition problem

The classical interval partition Problem ascs for a minimal colouring of an interval graph: Let [a_i, b_i] be a collection of (closed) intervals (for i in {1,2,...,n} ). Find a partition of {1,2,...,n}...
2
votes
0answers
51 views

Hardness result or reference for a set partition problem

I'm wondering if the following problem is (or has been proven to be) NP-Complete. Input: integer $n\ge0$, set $S_1,S_2,\ldots,S_{2n}$, set $T_1,T_2,\ldots,T_n$. Accept iff: there exists $\{a_i,...
0
votes
0answers
42 views

Mapping of entire balls using Locality Sensitive Hashing (LSH)

LSH functions are useful for approximate nearest neighbor search. They are usually defined, for distance metric $d$ and $c>1$ as follows: A family of hash functions is $(r, cr, p_1, p_2)$-LSH ...
20
votes
1answer
391 views

Is prime-counting function #P-complete?

Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ...
2
votes
0answers
56 views

$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?

Complexity zoo in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas has the following: $FPT = XPuniform\implies EPTAS = PTAS$. Fundamentals of Parametrized complexity on page $534$ has ...
7
votes
1answer
137 views

Sampling monotone Boolean functions

I'm interested in sampling monotone increasing Boolean functions on $n$ input bits uniformly at random. I understand that this is equivalent to approximating the Dedekind numbers ($D_n = $ the number ...
0
votes
0answers
18 views

The set of weight functions for which the assignment problem has non-trivial solutions

The standard assignment problem is specified with a square matrix ${\bf W}$ of weights (values, costs): $$ V_{\cal P} = \sum_i w(i, b(i)) = \sum_{(i, j) \in {\cal P}} w_{ij}, $$ where $\cal P$ is a ...
2
votes
0answers
131 views

Is the following problem in $coNP$?

Given an $n\times n$ matrix $M$ with $\mathbb Z$ entries is 'does an $\frac n2\times\frac n2$ minor of $M$ vanish?' in $\bf{coNP}$? At least one $\frac n2\times\frac n2$ minor non-vanish implies rank ...
0
votes
0answers
43 views

What is the complexity of Parametric Mixed Integer Linear Programming?

We know $$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$ $$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$ is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference). What is ...
-1
votes
0answers
41 views

Need help for my research and thesis topic related to linear algebra

I'm M. Phil Mathematics student and now I'm going to start my thesis work. I'm hugely interested in computer programming but yet I know only about web programming languages like javascript and little ...
1
vote
0answers
34 views

TSP variant in which edge costs depend on the already visited vertices

Does a TSP variant exist in which edge costs depend on the vertices already visited? For instance, if you already visited vertices A, B, and then C, in that order, then now the cost to traverse CD = 5,...
0
votes
1answer
33 views

Graph path problem [duplicate]

I am trying to solve one graph traversing problem which might be classical to guys who are familiar with the topic. However, I am not. I have directed graph where nodes are cities and plane can fly ...
4
votes
0answers
41 views

NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

I would like to know whether there are any examples of natural problems within the MAX-$k$-CSP family for which (under standard/reasonable conjectures) we believe the following: There is a value $\...
-1
votes
0answers
26 views

Channel and difference between entropies

If i have the Entropy H(X) of the channels entrance and H(Y) for the output. What does the difference between these 2 entropies tell me?
-3
votes
0answers
19 views

clustering of a set of points

I have two clustering problems. In one problem, the objective is to minimize the maximum radius of a cluster among all the clusters. In another problem, our goal is to minimize the maximum distance ...
2
votes
1answer
182 views

How far has computer science moved past Knuth's TAoCP, if at all? [closed]

The seminal book The Art of Computer Programming got its start in 1968. I have been finding references to it in many literature reviews, apparently there are many problems for which a review by Knuth ...
8
votes
3answers
388 views

Why exactly are complexity theorists interested in closed timelike curves?

Context: There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which ...
5
votes
0answers
157 views

Is there a fast algorithm for inverting a sparse matrix?

I am doing research on a random-walk like problem. As a critical part of my solution, I need to invert a non-singular sparse matrix of size $n \times n$ and with $O(n)$ non-empty entries. I'm working ...
-1
votes
0answers
19 views

Calculating Jaccard coefficient for similar words

Doc1: John who reads a book loves Mary Doc2: who does John think Mary loves? Considering the query "love Mary" Will the Jaccard coefficient be: J(q, D1) = 2/7 J(q, D2) = 2/6 Because "...
7
votes
1answer
142 views

Holant problems and holographic reduction: simple graphs or multigraphs?

From what I can understand, Holographic reductions for Holant problems are used to show #P-hardness or polynomial time computability of certain counting problems on undirected graphs that have very ...
7
votes
1answer
120 views

Understanding the Beck-Chevalley Condition

I've been reading through Bart Jacobs' "Categorical Logic and Type Theory", and lemma 1.8.9 has me stumped. The lemma is stated as follows: Let $p : \mathbb E \to \mathbb B$ and $q : \mathbb D \to \...
1
vote
0answers
29 views

Techniques to improve the efficiency of Dynamic Time Warping Algorithm

I am analyzing a set of time series that are shifted along the x-axis (see image below for clarification). I intend to average the time series and for that I would like to overlap all the start points ...
2
votes
1answer
117 views

Lower bound on alternations needed in $BQP$ versus $PH$ result?

What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
0
votes
1answer
52 views

Finding a Hamiltonian cycle from perfect matching of a bipartite graph

A disjoint vertex cycle cover of G can be found by a perfect matching on the bipartite graph, H, constructed from the original graph, G, by forming two parts G (L) and its copy G(R) with original ...
4
votes
1answer
164 views

Which (almost) balanced Boolean function has smallest “total” influence

The well known Kahn–Kalai–Linial (KKL) Theorem says that for any Boolean function $f\colon \{-1,1\}^n \xrightarrow{} \{-1,1\}$ $$ \max_{i \in [n]} \{\mathbf{Inf}_i[f] \} \geq \mathop{\bf Var}[f] \cdot ...
6
votes
1answer
85 views

Axioms of Minimum Size Resolution Refutations

Let $\phi$ be an unsatisfiable CNF formula and let $\Pi$ be a resolution refutation of $\phi$ of minimum size. Let $\psi$ be the subformula of $\phi$ containing the clauses that actually appear as ...
4
votes
1answer
50 views

Minimizing a convex piece-wise linear function of short $(\max, +)$ circuit length

If $a_{ij}$ is an $m \times n$ matrix of real numbers, and $b_j$ are $n$ more real numbers, then $$\max_i \sum_j (a_{ij} x_j + b_j) \qquad (\ast)$$ is a convex piecewise linear function of $(x_1, \...
0
votes
0answers
99 views

Lower bound to agnostic learning with membership queries

Setting: Let $X$ be a finite set and $C = \{0, 1\}^X$ a finite family of classifiers on $X$. Fix an $f \in \{0, 1\}^X$ not in $C$, a (possibly randomized and adaptive) learner $A$ has access to a ...
9
votes
2answers
220 views

Applications of algebraic geometry in type theory/programming language theory

Lately, I have become interested in algebraic geometry and have started reading on it. I still know very little about this field, but I do want to know if it has any connection with my main field, ...
4
votes
2answers
188 views

A variant of #POSITIVE-2-DNF

Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations ...
4
votes
0answers
82 views

Complexity of DFA intersection in this specific case?

In general, the size of the DFA that recognizes the intersection of $n$ languages is exponential in $n$. However, in my case I am computing the intersection of a very restricted subset of possible ...
0
votes
0answers
74 views

Given $n\times n$ matrix $A$ with integer entries, find #$k$SAT formula that yields $\mathrm{perm}(A)>0$

For each #$k$SAT instance one can build a matrix $A$ such that $\mathrm{perm}(A) = F(\Sigma)$, where $\Sigma$ is the solution count of the $k$SAT formula and $F$ an easy to invert function. My ...
8
votes
1answer
251 views

Is there any quantum analog of the VP vs. VNP problem?

From Wikipedia: $\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$. $\...

15 30 50 per page