All Questions

9,936 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
37 votes
0 answers
614 views

Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph $G$, and two vertices $s$ and $t$, find an $s$-$t$ path $P$ ...
• 371
37 votes
1 answer
2k views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
• 3,023
29 votes
0 answers
723 views

Largest set of cocircular points

Given $n$ points with integer coordinates in the plane, determine the maximum number of points that lie on the same circle (on its circumference, not its interior). This can be done in $O(n^3)$ ...
• 411
23 votes
0 answers
1k views

Can a calculus have incremental copying and closed scopes?

A few days ago, I proposed the Abstract Calculus, a minimal untyped language that is very similar to the Lambda Calculus, except for the main difference that substitutions are ...
• 4,037
23 votes
1 answer
1k views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
• 339
20 votes
0 answers
656 views

• 221
11 votes
0 answers
116 views

Min-eigenvalue bound for a random d-regular graph

I need help proving the following fact: Let $G$ be a random $d$-regular graph with adjacency matrix $A$. The smallest eigenvalue $\lambda_n$ of $A$ should satisfy $|\lambda_n| = o_d(d)$. (In ...
• 156
11 votes
0 answers
215 views

Covering a complete graph with n copies of an arbitrary graph: NP-complete?

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them ...
11 votes
0 answers
198 views

Can you multiply complex 2x2 matrices in fewer than 21 real multiplies?

It is well known that 2x2 matrices can be multiplied using just 7 (instead of the obvious 8) multiplications in the ground field (Strassen-Winograd, etc.). It is also well known that complex numbers ...
• 191
11 votes
0 answers
2k views

Barendregt's Variable Convention: what does it mean?

Barendregt's Variable Convention: If $M_1,...,M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free ...
• 1,072
11 votes
0 answers
189 views

When can you "invert" an equation in the lambda calculus

Suppose that $M$ is a full model of the simply typed lambda calculus. Suppose each base type is infinite. Now suppose that $f$ and $g$ are two functions in $M$ (not necessarily in the same domain) ...
• 230
11 votes
0 answers
157 views

Denotational semantics of object-oriented languages

I am interested in denotational semantics of object oriented languages. Namely, what are the common/typical denotations of objects used in the literature? Is this an interesting topic these days? The ...
• 1,614
11 votes
0 answers
1k views

Alternative to Bloom filter for extreme parameters

A Bloom filter is a space-efficient probabilistic data structure to perform membership-tests on a set (see Wikipedia's page for a definition; I use the same notations below). I am interested in a ...
• 391
11 votes
0 answers
365 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, \operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G \...
• 1,924
11 votes
0 answers
392 views

Proof of PCP theorem

I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem". ...
• 3,607
11 votes
0 answers
2k views

Does Automatic Differentiation handle conditional branches, if yes how?

I'm trying to understand how Automatic Differentiation (AD) works. For simple algebraic operation, I get the chain rule thing. But, when the code contains conditional statement like ...
11 votes
0 answers
2k views

I have rank-deficient matrix $M \in \mathbb{R}^{n\times m}$ with $\text{rank}(M) = k$ and I want to find a rank factorization $M = PQ$ with $P \in \mathbb{R}^{n \times k}$ and $Q \in \mathbb{R}^{k \... • 4,782 11 votes 1 answer 4k views Finding the longest repeating subsequence Given a string$s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string$w$which is a subsequence (doesn't have to be a contiguous) of$s$... • 494 10 votes 0 answers 79 views Maximum matching with social distancing Let$G = (X\cup Y, E)$be a bipartite graph. Suppose$X$contains people,$Y$contains seats in a theatre, and each edge$(x,y)$has a weight representing how much person$x$is willing to pay for ... • 5,798 10 votes 0 answers 140 views Regularity profiles A standard exercise in formal language theory uses Lagrange's four-square theorem to construct a language$L$such that$L$isn't regular but$L^2$is regular. (Let$A = \{ a^{n^2} : n \geq 0 \}$. ... • 273k 10 votes 0 answers 114 views Can we say McCarthy and Hoare had the same objective in the 60s regarding a mathematical theory of computation? I don't think there's any way to ask a very precise question here, so this might be considered opinion based. Nevertheless, it seems the question is clear enough because I'm asking whether these two ... • 237 10 votes 0 answers 193 views Constructing a connected graph with given degree sequence I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi ... • 211 10 votes 0 answers 716 views Advantages of algorithm W over algorithm J for type inference in Hindley-Milner type system According to A modern eye on ML type inference Furthermore, for some unknown reason, W appears to have become more popular than J, even though the latter is viewed—with reason!—by Milner as ... • 3,127 10 votes 0 answers 419 views Is Agda sound as a proof system? I was browsing Agda's stdlib source code, since I was trying to get into it seriously and therefore wanted to know more. I was amazed at that Agda is way more developed than I thought and it's ... • 583 10 votes 0 answers 234 views Minimum edge deletion partitioning of a planar graph I'm interested in the time complexity of the following problem: Given an undirected planar graph$G=(V,E)$and a weight function$w:E \rightarrow \mathbb{Z}$(so weights can be negative, too), color ... • 153 10 votes 0 answers 156 views Complexity class for probabilistic approximation algorithms with bounded error What's the name of a complexity class of optimization problems that have "bounded error probabilistic approximation algorithms"? Bounded error probabilistic version of APX (as BPP is bounded error ... • 560 10 votes 0 answers 175 views (Slightly) faster simulation of quantum Fourier transform Suppose I want to write a classical software simulator of a quantum circuit with$N$qubits. When it comes time to simulate the quantum Fourier transform I can evaluate all$2^N$states to determine ... • 17.5k 10 votes 1 answer 432 views Shift-resolve parsing - questions I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ... • 233 10 votes 0 answers 1k views Universal Turing Machine simulation with bounded time overhead Is it possible to design a Universal Turing Machine in which the simulation time of a given Turing Machine$M$is bounded by a factor of$\mathcal{O}(\log|\Gamma|+\log|Q|)$of the original running-... • 367 10 votes 0 answers 222 views "Essential" problem for MA I am trying to understand different interactive proof systems, in particular AM and MA. Is there a typical problem for the complexity class MA as Graph-NonIsomorphism problem is for AM? Is there ... • 666 10 votes 0 answers 130 views Applying the graph mining algorithm Leap Search in an unlabeled setting I am reading Mining Significant Graph Patterns by Leap Search (Yan et al., 2008), and I am unclear on how their technique translates to the unlabeled setting, since$p$and$q$(the frequency ... • 320 9 votes 0 answers 190 views Complexity of frog game on graphs is exponential, or can we do better? Frog game initializes by placing one frog on every vertex of a simple connected graph$G$with$n$vertices. A move consists of moving all$x\gt 0$frogs from one vertex to another non-empty vertex to ... • 105 9 votes 0 answers 323 views Are there consequences for P ≠ NP that are unintuitive? It's often regarded that the most intuitive answer to the question of$P$vs$NP$is that$P ≠ NP$. This is often illustrated with some consequences that would follow if$P = NP$were true. Things ... • 505 9 votes 0 answers 749 views How can the shortest traveling salesman tour be found in$O(2^n poly(n))$time and less than exponential space? I'm stuck on problem 9.4 from The Nature of Computation which reads: Dynamic Salesman. A naive search algorithm for TSP takes$O(n!)\$ time to check all tours. Use dynamic programming to reduce this ...
• 1,038

15 30 50 per page