# All Questions

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

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
88 views

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
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
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
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
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(...
1 vote
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
371 views

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