All Questions

Filter by
Sorted by
Tagged with
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 ...
TZM's user avatar
  • 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 ...
TomKern's user avatar
  • 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(...
mathquester's user avatar
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 ...
whoisit's user avatar
  • 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 $\...
a3nm's user avatar
  • 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: ...
Zazaeil's user avatar
  • 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_{\...
dohmatob's user avatar
  • 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$,...
Matthew Ferland's user avatar
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 ...
Omid Yaghoubi's user avatar
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)...
Jake's user avatar
  • 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 ...
Omar Shehab's user avatar
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 ...
Brad Brown's user avatar
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 ...
Tassle's user avatar
  • 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$ ...
user3508551's user avatar
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 ...
Jxb's user avatar
  • 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 ...
Alexey Milovanov's user avatar
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 ...
Blanco's user avatar
  • 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 ...
Amin's user avatar
  • 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 ...
Glycerius's user avatar
  • 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 ...
Hanchun Yuan's user avatar
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 ...
Johnny's user avatar
  • 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 ...
Karagounis Z's user avatar
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 ...
Amin's user avatar
  • 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. ...
wtfamidoing's user avatar
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 ...
Botanicus's user avatar
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 ...
Evan Aad's user avatar
  • 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 ...
AdCerros's user avatar
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 ...
ErroR's user avatar
  • 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 ...
Ctenochaetus's user avatar
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 ...
Evan Aad's user avatar
  • 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 ...
Alex_DeLarge's user avatar
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 ...
user avatar
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: ...
Hirrolot's user avatar
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 ...
user3508551's user avatar
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. ...
Chao Xu's user avatar
  • 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$?
fva's user avatar
  • 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 ...
Bob's user avatar
  • 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 ...
wavosa's user avatar
  • 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 ...
Sandip's user avatar
  • 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 ...
anurag anshu's user avatar
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 ...
LaR's user avatar
  • 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 ...
Hao Huang's user avatar
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 ...
djlovesupr3me's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
a3nm's user avatar
  • 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 $\...
David's user avatar
  • 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 ...
a3nm's user avatar
  • 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 ...
user68538's user avatar
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: ...
Wasabi Kurosawa's user avatar
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:...
Noah Singer's user avatar

15 30 50 per page