All Questions
12,298
questions
3
votes
1
answer
107
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 ...
- 73
1
vote
0
answers
49
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,224
1
vote
1
answer
132
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
219
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
43
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
53
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
176
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
109
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
67
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
196
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,697
1
vote
0
answers
63
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
151
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.3k
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,015
10
votes
0
answers
172
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
217
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
23
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
75
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
77
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
235
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
88
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
63
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 ...
- 203
0
votes
0
answers
28
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{...
- 862
1
vote
0
answers
57
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 \...
- 73
0
votes
0
answers
58
views
How do I calculate the information content of a mass spectrum?
Ions in a mass spectrum are represented using two independent values for the mass-to-charge ratio [m/z] of the ion and it's relative abundance. Here's an example for caffeine from HMDB: https://hmdb....
- 101
2
votes
2
answers
107
views
Are there publicly available fast Laplacian solvers?
In a much celebrated result, we know that there is a $ O(m\log \frac{1}{\epsilon}) $ time algorithm for solving laplacian systems of the form $Lx=b$ where $L$ is a laplacian of a graph $G$ with $m$ ...
- 862
3
votes
1
answer
124
views
Terminal object in the category of embeddings
Let ${\bf CPO}$ be the category of $\omega$-complete partial orders and $\omega$-continuous functions. Let ${\bf CPO}^{E}$ be the category of embeddings of ${\bf CPO}$. Does ${\bf CPO}^{E}$ have a ...
- 183
1
vote
0
answers
98
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 10.8k
3
votes
1
answer
151
views
Connected dominating set in bipartite graphs
Let $G$ a bipartite graph with two disjoint set of vertices $\mathbf{A}$ and $\mathbf{B}$.
Denote $n_a:=|\mathbf{A}|$, $n_b:=|\mathbf{B}|$. Suppose the following conditions hold:
$\Theta(1)<n_b<...
- 77
1
vote
0
answers
77
views
Alternative notions of bisimulation
Suppose $(S, \Lambda, \rightarrow)$ is a labeled transition system. A bisimulation is a relation $R \subseteq S \times S$ s.t. $\forall \alpha \in \Lambda$ and $\forall p, q \in S$ with $R(p,q)$,
$\...
- 11
4
votes
0
answers
68
views
How to learn the intuition behind probabilistic arguments in Algebraic Complexity lower bounds
I was reading the lower bounds of arithmetic circuits. There in the proof of the theorem
Over field $\mathbb{F}_q$, determinant, permanent requires depth-3 circuits of size $2^{\Omega(n)} $ [...
- 203
2
votes
0
answers
103
views
Faster algorithms to estimate the subset sizes
Lemma: Consider two sets $B ⊆ U$, where $n = |U|$. Let $ξ, γ ∈ (0, 1)$ be parameters, such that
$γ < 1/ \log n$. Assume that one is given an access to a membership oracle that, given an element $x ∈...
- 41
2
votes
1
answer
84
views
Number of vertices that a connected dominating set can reach in densely connected graphs
Consider a undirected densely connected (every vertex has $>\Theta(1)$ incident edges) graph $G$. Denote its vertices set as $\mathbf{V}$, number of vertices as $n$.
A connected dominating set $\...
- 77
0
votes
0
answers
34
views
Making primary keys explicit in a Boolean relation
Suppose we have a Boolean formula $\phi(X,Y)$ over the sets of Boolean variables $X$ and $Y$, representing a binary relation. There are in general many tuples in this relation.
Is there a way to ...
- 1,406
0
votes
0
answers
48
views
Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$
I was reading Ramprasad Saptharishi's survey on Arithmetic Circuits.
There in section 2.1.1 fact 2.3 it has
Any arithmetic circuit of of depth $\Delta$ and size $s$, can be
simulated by an arithmetic ...
- 203
0
votes
1
answer
62
views
PAC learning over continuous functions
I'm wondering if it's possible to use PAC learning to learn a continuous function. For example, if we wanted to learn a probability distribution or a CDF, is it valid to train on some set of m ...
- 1
0
votes
0
answers
63
views
Universality problem over unary alphabet is NP-complete
The universality problem over a unary alphabet: Decide if a unary NFA rejects a string.
I believe that this is NP complete, but I am unsure of how to prove it. One possible idea I have is to split it ...
0
votes
0
answers
87
views
Solving Linear Equations over finite field $ Z_q $
Suppose we are given a linear equation $ Ax=b $, where $ A \in Z_q^{n \times m} $ and $ b \in Z_q^n $.
Note that $ q $ is a prime here, and $ Rank(A)= Rank(A;b)=n<m $.
I wonder whether the ...
- 1
2
votes
1
answer
173
views
Is Levin's Universal Search valid for the integer factorization problem while using the AKS test?
It seems that there are many versions of this question that have answers when I look it up. But it seems quite clear that LUS should find a factor within an asymptotically quadratic transformation of ...
- 123
1
vote
0
answers
26
views
Can input-output matrices optimize bidirectional search?
Given a bidirectional search on a weigthed digraph, could a modified input-output matrix guess what nodes are more likely to belong to the shortest path and the search be done through these nodes ...
1
vote
1
answer
68
views
Prefix free code unbalancing 0 and 1 bits
We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...
- 113
0
votes
0
answers
70
views
How does laziness help functional data structure?
Functional data structures, or immutable data structures, are often achieved by copying old data to new data upon operation. Naively, it looks much less efficient than their imperical counterpart. ...
- 127
1
vote
0
answers
61
views
What is a "strongly complementary pair" of primal/dual solutions to a linear program?
While trying to understand this paper by Hammer, Hansen and Simeone, I came across some terminology I was unfamiliar with: the notion of a "strongly complementary pair".
For a linear program ...
0
votes
1
answer
129
views
2xn grid graphs from ring graphs via local complementations
(Local complementation) A local complementation $\tau_v$ is a graph operation specified by a vertex $v$, taking a graph $G$ to $\tau_v(G)$ by replacing the induced subgraph on the neighborhood of $v$, ...
- 79
2
votes
0
answers
36
views
Algorithms for parametric matroid optimization
Let $M$ be a rank $r$ matroid with basis set $\mathcal{B}$ and an independence oracle. Given a linear function $w_e$ on each element $e$ of the matroid, we want to find the minimum weight basis for ...
- 4,327
2
votes
1
answer
67
views
Spanning Tree that Preserves the Number of Branch Vertices
Suppose a undirected connected graph $G$, denote the number of vertices in $G$ as $n$, number of branch vertices (i.e., vertices with degree $\geq 3$) as $n_{\geq 3}$. Suppose $n_{\geq 3}>\log(n)$.
...
- 77