All Questions
9,923
questions with no upvoted or accepted answers
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
722
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
Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \...
- 2,269
19
votes
0
answers
457
views
Is finding a weight-balanced tree NP-hard?
In the following, we consider binary trees where only the leaves have weights.
Let $T$ be a binary tree and $W(T)$ be the sum of the weights of its leaves.
Let $T.l$ and $T.r$ be the left child and ...
- 316
19
votes
1
answer
956
views
Why hasn't functional programming researched dynamic trees?
Dynamic trees play an important role in solving problems such as network flows, dynamic graphs, combinatorial problems ("Dynamic Trees in Practice" by Tarjan and Werneck) and recently merging ...
JC Saenz
19
votes
1
answer
1k
views
Could min cut be easier than network flow?
Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
D.W.♦
- 150k
16
votes
2
answers
744
views
Steps that guarantee exiting a maze
Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting ...
- 261
15
votes
0
answers
329
views
Is the two-color leapfrog problem in P?
My question is whether a specific decision problem is in P or not. It's straightforwardly in NP. The decision problem is a specific case of the general $k$-color leapfrog problem.
I can already show ...
- 738
15
votes
0
answers
286
views
Using logic to prove non-regularity of a language
A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
- 12.3k
14
votes
0
answers
194
views
What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?
In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
- 241
14
votes
0
answers
675
views
Test whether two languages are equal, when give in algebraic form
This sub-problem is motivated by Algorithm to test whether a language is regular.
Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
D.W.♦
- 150k
13
votes
2
answers
1k
views
Flow graph that requires pushing back flow in Ford Fulkerson
Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson?
Let's assume we use the standard procedure of ...
- 4,381
13
votes
1
answer
748
views
The difference between dynamic logic and temporal logic
To find the difference, I'd just encountered with assertions below about temporal logic in Wikipedia:
another variant of modal logic sharing many common features with
dynamic logic, differs from ...
- 391
13
votes
0
answers
213
views
Why do we have to forbid non-conforming lower and upper type bounds?
(it's a repost of my unanswered question from scala-user@googlegroups.com about Scala)
In the Scala Language Specification, §4.4 Type Parameters, there is a requirement:
The most general form of a ...
13
votes
0
answers
423
views
Choosing a subset of binary variables to maximize the sum of the highest $K$
Consider the following problem:
Input:
integers $n > m > k$;
$n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$;
$n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$).
Let $X_1,\dots,X_n$ be $n$ ...
- 231
12
votes
0
answers
269
views
Is extensionality for coinductive datatypes consistent with Coq's logic?
Given a coinductive datatype, one can usually (always?) define a bisimulation as the largest equivalence relation over it. I would like to add an axiom stating that if two members of the type are ...
- 241
12
votes
0
answers
861
views
Optimal meeting point in directed graph
Let $G(V, E)$ be a edge-weighted directed connected graph and $v_1, \dots, v_n \in V$ be some vertices. Let $d(a, b)$ denote the length of the shortest path from $a$ to $b$, for $a,b \in V$.
I need ...
- 221
12
votes
1
answer
2k
views
Compiler that compiles to a Turing machine?
I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for ...
user7317
12
votes
0
answers
801
views
Fast algorithm for max-convolution with concave functions?
I'm interested in a discrete max-convolution problem, which is to compute
$$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$
for all values $c=0, \ldots, C$, where $x=(...
- 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
391
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
...
user10018
11
votes
0
answers
2k
views
Alternatives to SVD for rank factorization
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
139
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
713
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