All Questions
12,401
questions
6
votes
0
answers
84
views
Cycle packing with degree condition
Given a directed graph where each vertex has the same in-degree as out-degree, I would like to find the maximum number of edge-disjoint cycles. Is this NP-hard?
Without the degree condition, the ...
- 123
4
votes
0
answers
62
views
Equivalent Characterizations of Semilinear Sets
Coming from an automata theory background, the semilinear sets seem like an ideal candidate for having lots of equivalent characterizations.
I am already familiar with a few well known ones:
Sets ...
- 259
2
votes
0
answers
30
views
Tape reduction, tape compression and time compression
In our lecture we have the following relationships:
I have problems to understand these abstract classes.
First of all, our Turingmachines are defined as $1$ input tape and $k$ working tapes.
DSPACE(...
- 21
1
vote
3
answers
228
views
Turing Machines and Logic
It is well known that Monadic Second Order Logic (over words) and finite automata can express the same set of languages.
Is there a logic over words (perhaps a nth order logic) such that it and turing ...
- 123
10
votes
1
answer
399
views
Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?
Consider the following decision problem over a fixed alphabet $\Sigma$:
Input: strings $s_1, \ldots, s_n$ of $\Sigma^*$ and a target string $t \in \Sigma^*$
Output: does there exist a permutation $\...
- 8,234
7
votes
3
answers
952
views
Yet another constructive (Coq) proof that `nat -> nat -> nat` is not bijective. How to explain it to myself?
Here is a Coq proof I've came up with:
...
- 202
3
votes
2
answers
151
views
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $n$ be a large positive integer. Give a nonempty collection $\mathcal S$ of subsets of $[n] := \{1,2,\ldots,n\}$, define an inner-product on $\mathbb R^n$ by
\begin{eqnarray}
\langle x,y\rangle_{\...
- 291
0
votes
1
answer
59
views
Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover
As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$,...
- 135
2
votes
0
answers
76
views
Extending fagin’s theorem for #P (for arbitary structure)
While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures.
This is a corollary from fagin’s theorem. I have read fagin’s ...
- 129
6
votes
0
answers
156
views
Are exponential lower bounds known against $MOD_6 \circ MOD_3$ circuits computing $OR$?
Background
What is currently known for depth-2 $CC^0$ circuits with restricted gate types:
In [1] it is shown that $(MOD_p)^k \circ MOD_m$ circuits (that is, $k$ layers of $MOD_p$ gates at the output)...
- 1,034
0
votes
0
answers
26
views
Impact HHL caveat relaxation on quantum advantage
We know that there are four caveats for the exponential speedup proven for the HHL algorithm. Could anyone answer how that exponential speedup evolves as we relax the caveats?
For example, the ...
- 331
1
vote
0
answers
262
views
Did I discover a new data structure?
For context, I am working on an application in an environment where storage is prohibitively expensive (Ethereum smart contract) and I have some odd requirements:
I need to store a potentially ...
- 11
2
votes
0
answers
17
views
Bound on line with minimum zone complexity in a line arrangement
In an arrangement of $n$ (pseudo)lines, the well known Zone Theorem gives a $O(n)$ bound on the complexity of the zone of any given line (for the purpose of this question, the complexity of the zone ...
- 351
3
votes
1
answer
113
views
Complexity of sampling a clique uniformly at random
Let $G$ be an undirected graph, and let $C_1, ..., C_M$ denote all possible cliques in $G$.
What is known on the complexity of sampling a clique uniformly at random. That is, returning clique $C_i$ ...
- 897
0
votes
0
answers
133
views
What's the connection between branchwidth and treewidth
I understand that treewidth and branchwidth are essentially equivalent for a fixed graph, given that $branchwidth(G) = Θ(treewidth(G))$.
However, my question pertains to a specific case involving ...
- 21
4
votes
1
answer
167
views
A question about decision tree complexity
Let $f$ be a Boolean function. Is it possible that for some $x$ it holds that $DT(f|_{x=0}) = DT(f)$, but $DT(f|_{x=1}) < DT(f)$?
Here $DT(f)$ is decision tree complexity, i.e. the minimum depth of ...
- 1,881
4
votes
2
answers
180
views
NP-hardness: (planar) directed feedback vertex set problem with bounded degree
My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
- 397
1
vote
0
answers
42
views
What is the meaning of loss in online convex optimization?
I am studying online convex optimization, and it is stated that when we make a decision, we observe loss corresponding to our decision. In some problems like multi-armed bandit problems, we know the ...
- 61
3
votes
0
answers
92
views
$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$
I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...
- 131
0
votes
0
answers
61
views
Is there some intuitive point to understand Co-NP/poly?
I know what it means:
The coNP/poly problems are problems that decide a problem in co-nondeterministic poly-time using a $poly(n)$-size advice, where $n$ is the input size.
By the definition, we have ...
- 19
5
votes
0
answers
105
views
How is inapproximability by polynomial size circuits sufficient for the Nisan-Wigderson generator?
I couldn't understand how exactly Yao's XOR lemma was used to prove the following claim made in the proof of Theorem 2 of the original paper describing the Nisan-Wigderson generator, so I decided to ...
- 201
2
votes
0
answers
64
views
Confusion with the definition of Online Set Cover
I am confused on a technicality on how Online Set Cover is defined.
One way to define it is: We are given a collection of sets $\mathcal{S}$ upfront, and in each time-step an element arrives to be ...
- 597
0
votes
0
answers
41
views
Is there any bound on the convergence rate of actions in bandit literature?
In classical bandit problems where there are $K$ arms and we should decide which arm to pull at each period, the main issue is to design an algorithm that minimizes the regret and we find a bound on ...
- 61
0
votes
1
answer
119
views
Sources that prove solving 2-SAT with DP takes linear time
Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. ...
0
votes
0
answers
70
views
Where does combinatorial optimization beat machine learning algorithms?
For some variant of the Vehicle Routing Problem my algorithm that is based on combinatorial optimization performs a lot better than the algorithms based on machine learning of my competitors. So I ask ...
- 77
0
votes
0
answers
35
views
Which temporal logic is the one described in Manna & Pnueli's "The Temporal Logic of Reactive and Concurrent Systems: Specification"?
The Wikipedia article on temporal logic lists many varieties of temporal logic, such as LTL (linear temporal logic), CTL (computation tree logic), CTL*, and others. Which of these is the logic ...
- 334
0
votes
0
answers
57
views
Ensuring the connectivity of an undirected graph through linear programming
I am trying to solve a linear programming problem that deals with finding an optimal subgraph as a function of several parameters. The case is I am trying to model a constraint that ensures that the ...
- 1
1
vote
1
answer
48
views
$k-$median problem and filtering technique Lin and Vitter
I read a paper from Tardos et al. about $k-$medians in metric space problem:
Given $N$ as set of points in metric space with distance function $c_{ij}$ for each $i,j\in N$, demand $d_i$ for each point ...
- 113
2
votes
1
answer
106
views
NP-complete problems on posets?
I'm in the midst of some doctoral research and trying to figure out a particularly tricky reduction. I think my best shot is to reduce from an NP-complete problem on posets, if one exists.
I did some ...
- 23
3
votes
1
answer
49
views
Equivalence of finitary and infinitary semantics of concurrent programs
The following claim is stated on p. 155 of Manna and Pnueli's The Temporal Logic of Reactive and Concurrent Systems: Specification.
Let $P_1$ and $P_2$ be two finitely branching transition systems ...
- 334
0
votes
0
answers
32
views
Engset's loss system with 1 server, how to calculate state probabilities and average number of customers in the system?
I have this problem:
"By considering the Engset’s loss system, if there is only one server instead of m servers, derive the probability of having k customers in the system and hence the average ...
- 101
3
votes
0
answers
97
views
Complexity of checking if a given prime number can be computed using at most $s$ addition/multiplication operations?
Given are a prime number $p$ and a parameter $s\in\mathbb{N}$.
What is the computational complexity of the problem of determining whether $p$ is computable by a series of at most $s$ steps, each being ...
user67795
1
vote
0
answers
51
views
Is it possible to define beta reduction for PHOAS?
I'm using Parametric Higher-Order Abstract Syntax (PHOAS) as a representation for untyped lambda calculus in OCaml:
...
- 63
2
votes
0
answers
88
views
Why is the competitive ratio defined as $\mathbb{E}(ALG)/\mathbb{E}(OPT)$ vs $\mathbb{E}(ALG/OPT)$?
It seems like the consensus is to define an $\alpha$-competitive algorithm if $\mathbb{E}_R(ALG) \geq \alpha \mathbb{E}_R(OPT)$ where $\mathbb{E}_R$ is the expected value taken across the problem ...
- 897
2
votes
0
answers
43
views
Submodular function minimization over integer lattice
Let $[k]=\{0,1,\ldots,k-1\}$.
A function $f:[k]^n\to \mathbb{R}$ is submodular if $f(x)+f(y)\geq f(\max(x,y))+f(\min(x,y))$ for all $x,y\in [k]^n$. Here $\max$ and $\min$ are applied coordinate-wise.
...
- 4,367
4
votes
1
answer
159
views
Shortest path property and monadic second order logic
I know that induced paths and Hamiltonian cycles can be expressed with monadic second-order logic ($MS_2$).
Is it possible to express the shortest path in $MS_2$?
- 45
4
votes
2
answers
290
views
Lambda-calculus: Beta-equivalent terms have the same type
In the simply-typed lambda calculus, how do you prove that: If two terms are beta-equivalent, then they have the same type?
My guess is that I should use the subject reduction, and maybe the ...
- 371
3
votes
1
answer
79
views
END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node
The END OF THE LINE problem is stated as
Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
- 135
1
vote
0
answers
51
views
Approximation algorithm for non-bipartite Euclidean matching
What is the current best (in terms of running time) (1+\epsilon)-approximation algorithm (both randomized and deterministic) for non-bipartite Euclidean (in higher dimension) matching? There are ...
- 11
2
votes
2
answers
788
views
Johnson-Lindenstrauss and the largest eigenvalue of a matrix
Johnson-Lindenstrauss (JL) lemma shows that for any vector $u$ in $\mathbb{R}^d$, the vector $\frac{1}{\sqrt{k}}Ru$ satisfies $(1-\epsilon)\|u\|\leq \frac{1}{k}\|Ru\|^2\leq (1+\epsilon)\|u\|$ with ...
- 243
1
vote
0
answers
109
views
Closely related (?) arrows in categories
Let $f: x\to y$ and $f':x' \to y'$ be arrows in a category ${\bf C}$, where $x\cong x'$ and $y\cong y'$. Assume that for all isomorphisms $v: x \to x'$ and $u: y\to y'$, the corresponding diagram ...
- 183
5
votes
2
answers
167
views
Lower bound for sorting without using a decision tree model
Can we prove the lower bound for the sorting problem just by Turing machine model?
It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can ...
- 51
0
votes
0
answers
64
views
Why does the prefix sum operation require its binary operator to be associative?
Prefix Sums and Their Applications states that
The all-prefix-sums operation takes a binary associative operator ⊕, and
an ordered set of n elements...
Why is associativity a required property of ...
3
votes
0
answers
40
views
Quantum circuits vs quantum circuits w/ only local interactions?
If we restrict a quantum circuit to only have interactions between "nearby" qubits (for some connection topology that defines "nearby", as is the case in several actual quantum ...
- 36.4k
2
votes
1
answer
103
views
Embedding degree-3 planar graphs as topological minors in wall graphs in polynomial time
For a proof, I need the fact that we can efficiently embed an input planar graph into a representative of a specific family of high-treewidth graphs. Specifically, I need an embedding as a topological ...
- 8,234
0
votes
1
answer
74
views
An inequality about median of points in higher dimensions
Let $S$ be a set of points in $\mathbf{R^d}$ and let $m$ be the median of this set of points, i.e. $\sum_{x \in S} || x - y||$ is minimized when we have $y=m$. Now let $z$ be an arbitrary point in $\...
- 1
9
votes
2
answers
231
views
Defining regular language classes with disjoint union
Regular languages are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for ...
- 8,234
4
votes
1
answer
98
views
NC0 randomnes vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
- 41
0
votes
0
answers
110
views
On the use of Turing machines for computational complexity
Almost always in the study of computational complexity, the Turing machine is used as a model. On the other hand, the untyped lambda calculus is in a sense "simpler" than any Turing machine: ...
3
votes
1
answer
105
views
"Market" intuition for the dual of the max-weight matching LP
I recently learned about the Hungarian algorithm for maximum-weight matching in bipartite graphs and the "market" interpretation of the primal and dual LPs. (See also these notes.)
The setup:...
- 235