All Questions
12,293
questions
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(...
- 203
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 ...
- 898
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 ...
- 111
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 ...
- 61
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, ...
- 117
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(...
- 11
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 ...
- 99
-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$,...
- 135
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 ...
- 129
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 ...
- 331
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 ...
- 153
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 ...
- 11
-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$ ...
- 862
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 ...
- 1,859
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 ...
- 1
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 ...
- 597
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 ...
- 77
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
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 ...
- 21