All Questions
10,435
questions with no upvoted or accepted answers
37
votes
0
answers
667
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
30
votes
0
answers
787
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)$ ...
- 431
24
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 ...
- 349
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,117
22
votes
0
answers
696
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,289
20
votes
1
answer
2k
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.♦
- 156k
19
votes
0
answers
484
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
987
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
17
votes
0
answers
358
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 ...
- 758
16
votes
0
answers
302
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.4k
16
votes
2
answers
814
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
14
votes
0
answers
224
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
695
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.♦
- 156k
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,431
13
votes
1
answer
790
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 ...
user33772
13
votes
0
answers
218
views
Why do we have to forbid non-conforming lower and upper type bounds?
(it's a repost of my unanswered question from [email protected] 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
432
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
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 ...
- 984
12
votes
0
answers
276
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
910
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
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,812
12
votes
0
answers
816
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
123
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
151
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 \}$. ...
- 275k
11
votes
0
answers
244
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
210
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
204
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
164
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,644
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
373
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,934
11
votes
0
answers
402
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,657
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
181
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.7k
11
votes
1
answer
5k
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
92
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,730
10
votes
0
answers
115
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
200
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
787
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
444
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 ...
- 622
10
votes
0
answers
236
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
158
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 ...
- 570
10
votes
1
answer
451
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
234
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 ...
- 686
10
votes
0
answers
133
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
201
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
331
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 ...
- 515
9
votes
0
answers
766
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,048
9
votes
0
answers
155
views
Using naturality to prove $f: \forall\alpha. \alpha\times\alpha\to\alpha$ must be a projection
Suppose we have a System F term $f : \forall \alpha. \alpha\times\alpha\to\alpha$, interpreted in a parametric model which is a bicartesian closed category.
I was wondering if in such context it is ...
- 14.4k