# All Questions

10,094 questions
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, ...
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?
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?
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 ...
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 ...
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 ...
61 views

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 ...
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 =...
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 ...
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 ...
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 ...
55 views

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}\... 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 ... 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}... 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,... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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,... 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 ... 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 \... 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? 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 ... 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 ... 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 ... 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 ... 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 "... 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 ... 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 \... 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 ... 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))]} ... 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 ... 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 ...
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 ...