All Questions
12,409
questions
2
votes
0
answers
55
views
computational complexity of sparse matrix powers
Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
- 209
3
votes
1
answer
86
views
Does ${\bf CPO}$ have $\omega$-colimits?
Does the category ${\bf CPO}$ have $\omega$-colimits? By ${\bf CPO}$ I mean the category that has as objects the $\omega$-complete pointed partial orders and as arrows $\omega$-continuous functions.
- 183
5
votes
0
answers
89
views
Reductions and projections in circuit complexity
I'm struggling to find a good reference that defines the difference between projection and monotone projection in the context of Boolean functions and circuit complexity.
My understanding is that a ...
- 607
7
votes
1
answer
266
views
Is $PSPACE$ believed to be different than $PP$?
From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$.
Is it currently believed that $PP\neq PSPACE$?
What would be the ...
- 215
0
votes
0
answers
65
views
Maintaining a $K_{3,3}$-minor-free graph
Suppose we are given that an undirected, connected graph $G$ is $K_{3,3}$-minor-free.
Let $a,b\in V(G)$ be non-adjacent vertices.
Under what conditions is the graph that results by adding the edge $(a,...
- 95
0
votes
0
answers
62
views
Unclear explanation of basic parallel DAG computation
Consider computation represented as a DAG, without if-then-else conditions, where nodes represent tasks and edges represent data dependencies. For example, A->B->C means that there are 3 tasks ...
- 1
0
votes
1
answer
56
views
Spectral sparsification of graphs with negative edge weights
I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.
It is ...
- 1
6
votes
1
answer
285
views
Concrete family of propositional formulas
Let $k,n \in \mathbb{N}$, where $k$ can be thought of as being fixed constant. For each $1 \leq \ell \leq k$ and $1 \leq i \leq n$ we have a proposition symbol $p_{(\ell,i)}$ (so in total we have $nk$-...
- 869
0
votes
1
answer
79
views
Regarding UNSAT bechmark of SATLIB found as SAT instance
I found the Satisfiable assignment to one of the UNSAT [SATLIB benchmark][1] instance, specifically uuf50-01.cnf as below answer:
[1, 2, 3, 4, -5, -6, -7, -8, 9, 10, -11, 12, 13, 14, -15, -16, 17, 18, ...
- 11
0
votes
0
answers
32
views
Computational complexity of CVaR calculation
I am currently looking for literature discussing the computational complexity of CVaR calculation. At this point the only work I have found is the following.
Mavronicolas, Marios, and Burkhard Monien. ...
- 331
0
votes
0
answers
91
views
Non-uniformity assumptions in circuit complexity
I recently came accross the following standard inclusion of complexity classes:
$$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
- 607
3
votes
0
answers
99
views
Context-free languages and free/bound variables
Fix a first-order language $L_0$, and let
$$L=\{f(\varphi)\mid \varphi \text{ is a well-formed formula of $L_0$}\},$$
where $f(\varphi)$ is $\varphi$ with all occurrences of free variables underlined.
...
- 4,445
7
votes
1
answer
247
views
How do separations in of query complexities imply complexity class separations relative to oracles?
Simon's problem is the following: Given oracle access to a Boolean function $f: \{0,1\}^n\rightarrow \{0,1\}^n$, and promised that precisely one of the following two cases is true, decide which of ...
- 250
0
votes
0
answers
52
views
Non-uniform consequences of uniform derandomization
Adleman showed that $\mathsf{BPP/poly} \subseteq \mathsf{P/poly}$.
Does $\mathsf{P} = \mathsf{BPP}$ have any implications for
$\mathsf{BPP}/a(n) \subseteq \mathsf{P}/a(n)$
$\mathsf{BPTIME}(t(n))/a(n) ...
0
votes
0
answers
52
views
Maximum-weight matroid intersection with real weights
Given a matroid with weighted elements, a basis with maximum total weight can be found in polynomial time using the greedy algorithm. This is true even when the weights are real numbers, if we assume ...
- 1,924
1
vote
0
answers
68
views
One way analogues of Logspace
When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$.
Likewise we say a function is logspace one-way if the function is ...
- 12.6k
0
votes
0
answers
11
views
Queueing theory. How to figure out if steady state or grows without bound?
I have a real-life problem from work that we haven't been able to figure out. None of us have advanced CS background.
Rate R of message arrival to the system from a client is 7/10s.
25 workers do ...
- 101
3
votes
0
answers
68
views
Bounding the size of a power of a proper interval graph
Is there a citable proof of the following result (or perhaps a generalization of it)?
Lemma 1. Let $G=(V, E)$ be a proper interval graph. Let $G^k=(V, E^k)$ be the $k$th power of $G$. Then $|E^k| = ...
- 9,555
1
vote
0
answers
97
views
How to download .bib of all papers ever published in main venues in TCS (journals, conferences, repositories, etc.)
Is there now a system out there that does this? Or even venue by venue -- for example, is there a way to download all references for all papers published any time in JACM? I tried DBLP but I couldn'...
- 7,589
0
votes
1
answer
87
views
Can an unrestricted grammar have a rule with only terminals on the left-hand side?
In the definition of unrestricted (type 0) grammars we only really have the rule that the lhs cannot be the empty string.
Then, is it allowed to have a production rule with an lhs consisting only of ...
2
votes
0
answers
98
views
Problems in $P^{PP}$
I just discovered that a problem that I was studying could belong to $P^{PP}$, I would like to prove that this problem is $P^{PP}$-complete (if that is even a thing). The issue is that I'm unable to ...
- 21
0
votes
0
answers
85
views
Existence of a family of size 2^Ω(n) of subsets of {1,...,n} each of cardinality n/4 where two subsets have at most n/8 elements in common
Let $\mathcal{G}$ be a family of $t=2^{\Omega(n)}$ subsets of $N=\{1,2,...,n\}$, each of cardinality $n / 4$ so that any two distinct members of $\mathcal{G}$ have at most $n / 8$ elements in common.
...
- 101
3
votes
1
answer
119
views
Hardness of Maximum Independent Set in 3-Colorable Graphs
Let $G = (V,E)$ be an undirected graph such that there is a proper coloring of the vertices of $G$ in three colors.
Question: In such graphs, are there known results for the hardness of finding a ...
- 103
1
vote
0
answers
51
views
Better approximation of the subset in the membership oracle
A standard tool for estimating the size of a subset via membership oracle queries is given below.
Lemma 2.8: . Consider two (finite) sets $B ⊆ U$, where $n = |U|$. Let $ε ∈ (0, 1)$ and $γ ∈ (0, 1/2)$ ...
- 41
11
votes
1
answer
1k
views
Is the 3-coloring problem NP-hard on graphs of maximal degree 3?
Consider the 3-coloring problem: given an undirected graph $G = (V, E)$, decide if there is a 3-coloring of $G$, i.e., a function $f$ from $G$ to $\{1, 2, 3\}$ such that there is no edge $\{u, v\}$ in ...
- 8,234
1
vote
1
answer
152
views
Graph partitioning to minimize sum of intra-partition edge weights
I've seen a lot of graph partitioning algorithms w/ the objective of minimizing the weight of inter-partition edges, (e.g. k-way partitioning) but haven't quite found anything on minimizing the total ...
- 11
2
votes
2
answers
221
views
Resources for hoodie design related to theoretical CS [closed]
I have to design a hoodie for my computer science batch, and I want it to be related to Theoretical computer science. I don't want to slap on some text with HTML-like angle brackets, but actually want ...
- 121
1
vote
0
answers
47
views
Enumerating all parse trees from a parse forest
Say a generalized parsing algorithm whether a GLL parser or Early parser generates a parse forest. Would it be possible to enumerate all of the parse trees from the forest? If possible, in a lazy ...
- 11
2
votes
1
answer
56
views
Sampling strategies for Quicksort
I'm studying a variation of Quicksort in which the algorithm samples a subarray of size $f(n)< n$ ($n$ is the size of the input array) and then chooses the pivot from this subarray. The pivot is ...
- 21
3
votes
1
answer
178
views
Solving linear programs with special structure
We have an application and at some point we need to solve a linear programming problem that looks like this:
$$
\min\ w_{1,2} + w_{3,4} + w_{5,6}\\
x_i - x_j \leq c_{ij},\ \forall\ (i,j) \in C\\
x_1 - ...
- 73
2
votes
0
answers
111
views
Computing real numbers with Turing Machines
Consider the following decision problem:
Given a two integers $n$ and $k$, decide whether $k=\lfloor n\pi\rfloor$
Question: Is this problem known to be in $P$?
Although this may look like a stupid ...
- 475
0
votes
0
answers
68
views
On the Reductions of Functional complexity Classes
In Chapter 10 of Computational Complexity by Christos Papadimitriou, it is noted that reduction between problems of functional complexity classes are defined as follows:
Function problem A reduces to ...
- 21
1
vote
2
answers
204
views
How much information does it take to specify, not each member of a group, but any one member?
It takes exactly $\log_2 n := \lg n$ bits of information to specify a number from $\{1,2,\ldots,n\}.$ Likewise, it takes $\lg{n\choose s}$ bits of information to specify a subset of $s$ out of the $n$ ...
- 1,717
1
vote
0
answers
65
views
communication complexity lower bound for identifying coordinate in which two strings differ
This is a question from Rao and Yehudayoff's "Communication Complexity and Applications" textbook that I've been thinking about for a while. Suppose Alice has a string $x\in\{0,1\}^n$ that ...
- 51
5
votes
1
answer
182
views
The precise definition of Normalization By Evaluation?
The Wikipedia article suggests that NbE is a technique for obtaining "the normal form of terms" by translating the object language into abstractions of the meta (host) language:
The ...
- 63
1
vote
0
answers
121
views
Computational complexity of higher order cumulants
From Wikipedia:
In probability theory and statistics, the cumulants κn of a probability distribution are a set of quantities that provide an alternative to the moments of the distribution. Any two ...
- 331
5
votes
0
answers
160
views
Complexity of a problem related to Friedman's TREE(k) function?
Background
Given two rooted, vertex-colored trees $T_1, T_2$, $T_1$ is color-preserving inf-embeddle in $T_2$, which we'll denote $T_1 \leq T_2$, if there is an injective $f \colon V(T_1) \to V(T_2)$ ...
- 36.4k
3
votes
0
answers
91
views
Succinct problems over uniform computational models
For a language $\Pi$, the traditional definition of "Succinct-$\Pi$" is the set of encodings of circuits whose truth tables are members of $\Pi$.
This definition is essentially restricted (...
- 1,034
10
votes
0
answers
179
views
True origin story of linear logic?
When I was a master's student in Paris I was exposed to the following standard narrative: "J.-Y. Girard invented coherence spaces, then he noticed the decomposition $A \to B~=~!A \multimap B$ and ...
3
votes
2
answers
220
views
What is this graph problem, and how hard is it?
My problem is quite simple to state, so it surely must have a name:
Given a graph $G=(V,E)$ with edge weights $w(e) \in \mathbb{Z}$, find a $V' \subseteq V$ that maximizes $\sum_{e \in E' } w(e)$, ...
- 31
0
votes
0
answers
24
views
An upper bound on sample complexity for state identification given ensemble distinction problem
I am trying to derive Fact 5. in paper 1:
Let $\mathscr{E}=\{\sigma_1,.., \sigma_m\}$ be an ensemble of quantum states in $\mathbb{C}^n$. If there is a POVM $\mathscr{M}$ for the state distinction ...
1
vote
1
answer
78
views
A bound that follows from submodularity
I am studying Lemma 1 of this paper: The Adaptive Complexity of Maximizing a Submodular Function. The proof appears on page 11.
I got stuck on this inequality:
where $f$ is a monotone submodular set ...
- 113
0
votes
0
answers
19
views
Hopfield Neural Network energy and neuron states
Can neurons in Hopfield Network have non-binary values ( continuous values instead of -1 and +1)? If they can , is energy expression for hopfield NN stays the same? What is the main condition for ...
- 1
2
votes
0
answers
78
views
Random Self-Reducibility of the Discrete Logarithm
Section 10.1.2 of Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach defines random self-reducibility and proves hardness of the discrete logarithm by reducing a worst case ...
- 21
5
votes
2
answers
242
views
Complexity of convertibility in simply typed λ-calculus with sums
For the simply typed λ-calculus with only the function type →, the complexity of deciding βη-equivalence is well-understood: it's TOWER-complete (as mentioned here). I expect the same should be true ...
1
vote
0
answers
89
views
How to solve the following continuous optimization problem?
Consider a function $f: X\times Y\times N$, where $X, Y \subseteq \mathbb{R}^m$ are convex sets, and $N = \{1,2,\dots,n\}$. We additionally know that
$f(\cdot,y,S)$ is convex for fixed $y,S$
$f(x,\...
- 25
0
votes
1
answer
68
views
In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$
I am reading Depth Reduction of Arithmetic Formula form the survey of Ramprasad Saptharishi. Now in the proof of depth reduction due to Brent, 74 that
Let $f$ be an n-variate degree d polynomial ...
- 268
0
votes
0
answers
29
views
Distribution-free learning vs distribution-dependent learning
I asked this question on Mathoverflow and realized that it should have been better to ask here.
My main confusion is, how to distinguish distribution-free learning and distribution-dependent learning ...
- 1
0
votes
0
answers
44
views
Ellipsoid method with the deepest cut
Consider the minimization of a convex $f(x)$ subject to $Ax\leq b$ for $x\in \mathbb{Q}^n$. The ellipsoid method takes as input a ball $B(0, R)$ containing $x^\ast$, and a separation oracle $\mathcal{...
- 897
1
vote
0
answers
60
views
Unbounded Knapsack Instance with a Single Optimum that takes each Item Once?
Consider the Unbounded Knapsack Problem (UKP): We are given a set of $n$ items $I = \{1,\ldots,n\}$ of integral weights $w_1, \ldots, w_n \in \mathbb{N}$, integral profits $p_1, \ldots, p_n \in \...
- 103