All Questions
12,298
questions
1
vote
0
answers
19
views
Computational complexity of some optimization problem?
I wonder if there are some methods I can borrow from computational complexity theory to analyze the optimization problem such as a convex optimization problem. An example of this is to find the ...
- 111
1
vote
1
answer
58
views
Communication complexity of equality on graphs
I came upon a nice observation in communication complexity, and I was wondering if it was already known.
Consider the following variant of the equality problem: There is a fixed graph $G$ that is ...
- 5,290
0
votes
1
answer
43
views
Finding an $\epsilon$-concentrated collection with size in terms of spectral $1$-norm
$\newcommand{\R}{\mathbb{R}}$
This question is about Problem 3.16 in Ryan O'Donnell's Analysis of Boolean Functions book. The problem is stated as follows:
Let $f : \{-1,1\}^n\to\R$ and let $\epsilon&...
- 51
1
vote
0
answers
36
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
0
votes
0
answers
31
views
Weighted vertex cover in chordal graphs
I'm interested in computing the weighted vertex cover in chordal graphs. I believe this is possible in polynomial time.
Does anyone have any pointers to any algorithms that can achieve this (...
0
votes
0
answers
21
views
Complexity of XOR-Knapsack
Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
- 2,039
0
votes
0
answers
23
views
Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT
3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction).
But, as I ...
- 304
1
vote
1
answer
44
views
If boolean function $f$ is computable by a k-CNF and an l-DNF then it can be computed by a decision tree of depth at most kl
I have seen it stated that if boolean function $f$ is computable by a $k$-CNF and an $l$-DNF then it can be computed by a decision tree of depth at most $kl$. However, I am not able to see why this is ...
0
votes
0
answers
40
views
Learning Parities via Gradient Descent
[Disclaimer: Crossposted in cs --> link]
In their recent work [DM20] Daniely and Malach prove that a two layer sufficiently wide NN can learn parities via gradient descent (GD). Since [Kearn94] it ...
2
votes
1
answer
38
views
Balls in monochromatic bins
Suppose we have a collection of $m$ balls in $k$ different colors. Let $b_i$ be the number of balls with color $i$, so $\sum_{i=1}^k b_i = m$. Assume we have $n$ bins with capacities $c_1, \dots, c_n$,...
- 23
-1
votes
0
answers
39
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
-2
votes
0
answers
55
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
33
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
114
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
2
votes
1
answer
88
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
102
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
44
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
71
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
36
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
115
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
159
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
28
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
69
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
63
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
57
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
2
votes
0
answers
28
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
214
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
371
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
3
answers
899
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
37
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
144
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
54
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
74
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
148
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
58
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
249
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
41
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
104
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
15
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
160
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
156
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
89
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
18
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