All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

Probability of node being infected at time t=10 in SIR model

For the question above I am having a bit of a rough time trying to calculate the probabilities for nodes C, D, and E. My thoughts: For the node C I believe it would be equal to the probability that ...
  • 1
-1 votes
0 answers
37 views

Is every decidable language Turing-recognizable? Please read body for more details

So I'm currently going through Michael Sipser's computational theory book. In chapter 3 he says this: Call a language Turing-recognizable if some Turing machine recognizes it. By recognizable it ...
0 votes
0 answers
27 views

Why $Rank(C)< R(k,d)$ for Depth 3 Balckbox PIT Algorithm implies $C$ is zero

I was reading the Survey on Polynomial Identity Testing by Nitin Saxena. In the Depth 3 Blackbox PIT Algorithm he first finds $O(k^2d^2+2^k)$ many subspaces of the linear forms of the $\sum\prod\sum(...
6 votes
0 answers
99 views

Consistent Sampling a Random Walk

Assume there's a random walk $S_k = X_1 + \dots + X_k$ where $X_i \in \{1, -1\}$ are uniformly iid. I want Alice and Bob to share a function $S(k) = S_k$. A straightforward approach would be to let ...
0 votes
0 answers
40 views

Question About Time Complexity From a 2016 Test [closed]

I am looking at this question that came up in a test I took: We have 3 given functions: 𝑓(𝑛) = O(𝑛²) ℎ(𝑛) = Ω(√𝑛) 𝑔(𝑛) = O(log𝑛) Which of the following statements is false?: 𝑓(𝑛) / ℎ(𝑛) = ...
2 votes
1 answer
78 views

doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations. I follow the proof of the following two identities : $[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq ...
  • 121
0 votes
0 answers
84 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
1 vote
0 answers
41 views

Is there a calculus or formalism for measuring set relations between algorithm outputs?

I'm asking this question from a fairly naive position, so apologies in advance, etc. I'm aware of the Bird-Meertens formalism for equational reasoning about algorithms but what I'm really interested ...
2 votes
0 answers
68 views

What kind of solver should I use for this hypergraph problem?

I have to list the solutions to the following hypergraph problem: There is a set of nodes, linked by edges that are 2-to-1 and bidirectional. The possible directions are either direct: 2 sources and 1 ...
  • 8,223
3 votes
0 answers
34 views

Can you compute Shannon expansion of a Boolean formula more efficiently by using a QBF solver?

Maybe this is not enough research level, but I've been scratching my head on it for a while... I'm interested in the Shannon expansion of an existentially quantified Boolean formula of the form: $$ \...
  • 1,406
6 votes
0 answers
103 views

Consequences of $P^{NP[o(n)]} = P^{NP}$

I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$? I ...
0 votes
1 answer
148 views

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define $$ f_{\mathfrak S}(z) := \sum_{\...
  • 291
1 vote
0 answers
25 views

Non-uniform advice skews runtime

Let $\mathsf C$ be some class. Let $a : \mathbb N \to \mathbb N$ be some function describing the bit length of advice. Let $C/a := \{L | \exists L' \in \mathsf C \text{ and } \exists (w_n)_{n\in \...
4 votes
0 answers
64 views

Circuit computing Longest Increasing Sub-sequence (LIS)

Taking inspiration from sorting networks, I was wondering if another prominent algorithm can be implemented in the same fashion: finding the longest increasing sub-sequence (LIS), Input is given as ...
  • 679
10 votes
12 answers
4k views

Theoretical Computer Science vs other Sciences?

So I‘m in my third semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
6 votes
0 answers
59 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 ...
  • 61
4 votes
0 answers
55 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 ...
  • 209
1 vote
0 answers
26 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(...
1 vote
3 answers
201 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
9 votes
1 answer
367 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,224
7 votes
2 answers
870 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: ...
  • 172
-1 votes
0 answers
50 views

M/M/1 priority queueing system (?), an exercise

can someone help me please solving this? Consider a switch with two input links and one outgoing transmission link. Data packets arrive at the first input link according to a Poisson process with mean ...
-1 votes
0 answers
36 views

Do modular exponentiation and extended GCD have any $Logspace$ relation between them?

Modular exponentiation and Extended $GCD$ are notorious open problems in parallel computational complexity domain. Is there any $Logspace$ or lower relation or reduction between them at least under ...
  • 12.6k
3 votes
2 answers
141 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
53 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$,...
2 votes
0 answers
72 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 ...
6 votes
0 answers
145 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,015
0 votes
0 answers
24 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 ...
1 vote
0 answers
57 views

Are there polynomial time computable polynomials with circuits of size $s$ but no circuits of size $s-1$?

So I was wondering whether you could always have a multivariate polynomial $P$ over $\mathbb{Z}$ that ... can be represented by arithmetic circuits of size $s$ has polynomial degree and exponentially ...
1 vote
0 answers
244 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 ...
-1 votes
0 answers
40 views

N-Queens complexity categorization

As I am reading through papers regarding the N-Queens problem, I got caught up whether it is classified to be a NP-Hard problem or otherwise. This paper says that the problem is classified as an NP-...
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
101 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$ ...
0 votes
0 answers
120 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 ...
  • 1
-3 votes
0 answers
14 views

Need example of Iterative Lengthening Search

I have spent hours on internet to find an example of iterative lengthening search algorithm but found nothing. I need it ASAP. Can anyone help me? Please. It is its definition: Iterative lengthening ...
  • 1
4 votes
1 answer
158 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 ...
4 votes
2 answers
153 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
39 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 ...
  • 111
3 votes
0 answers
88 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
56 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 ...
  • 9
5 votes
0 answers
99 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 ...
  • 151
-1 votes
0 answers
17 views

Capacitated Vehicle Routing- Help in understanding a proof

The paper "A Capacitated Vehicle Routing Problem on a Tree" (https://link.springer.com/content/pdf/10.1007/3-540-49381-6_42.pdf) by Shinya Hamaguchi1 and Naoki Katoh stated in the ...
2 votes
0 answers
60 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 ...
0 votes
0 answers
36 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 ...
  • 111
0 votes
1 answer
100 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
63 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 ...
0 votes
0 answers
30 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 ...
  • 324
0 votes
0 answers
55 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 vote
1 answer
43 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
98 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 ...

15 30 50 per page
1
2 3 4 5
246