# All Questions

12,298 questions
Filter by
Sorted by
Tagged with
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
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
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
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
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 ...
1 vote
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
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 ...
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
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
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 ...
1 vote
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
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
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
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
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
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
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 ...
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
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
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
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 ...
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 ...
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
88 views

• 862
1 vote
57 views

1 vote
77 views

• 41