# All Questions

12,293 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
27 views

• 121
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
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 ...
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
34 views

• 291
1 vote
25 views

• 8,224
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
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 ...
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
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
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$,...
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 ...
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
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 ...
• 331
1 vote
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
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 ...
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-...
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
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$ ...
• 862
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
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
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 ...
• 1,859
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
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
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
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 ...
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
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 ...
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 ...
• 597
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
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. ...
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 ...
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
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
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