# Questions tagged [big-list]

Questions whose answers are a big list of items (books, theorems, software, ...)

173 questions
Filter by
Sorted by
Tagged with
185 views

### What online talks should everyone watch? [duplicate]

In the past 4-5 years or so, partly owing to COVID, more and more talks have been uploaded to YouTube. In the same spirit as this question by Ryan Williams almost 14 years ago: What papers should ...
• 369
295 views

### Obscure characterizations of the regular languages

I've been collecting equivalent characterizations of the regular languages. Does anyone know of any I haven't yet found? Wikipedia has a bunch: https://en.wikipedia.org/wiki/Regular_language#...
• 479
3k views

### What are examples of recent relatively simple 'toolbox algorithms'?

Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc. There are also several relatively standard data structures, such ...
1k views

### Problems in NP with non-trivial certificate

For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I ...
80 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 ...
• 479
39 views

### Statements equivalent to strongly polynomial time linear programming

Say a problem is SPT iff it admits an SPT algorithm. What statements of interest are known to be equivalent to "LP is SPT"? Examples: "linear feasibility solving is SPT" (due to ...
• 662
177 views

### The graph of problem reductions

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
1 vote
76 views

### Some examples of tools to demonstrate problem is in $NC$ [closed]

Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
• 12.9k
3k views

### Examples of collapsing hierarchies

Are there interesting examples of "collapsing hierarchies" in computer science? The formal definition of a hierarchy here would be a class of languages/problems/objects which is ...
• 521
187 views

### What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different. What evidences are there that $PP$ is in $BQP$? What evidences are there that $PP$ is not ...
• 12.9k
692 views

### "Refined" list of open problems in TCS

In the conference on learning theory (COLT), a list of open problems is published every year, for example, the list of 2019. The open problems are being submitted and peer reviewed, which makes this ...
• 151
135 views

### Graph problems in P with unknown lower bounds

I am looking for references to interesting graph problems, which are known to be in P, but their precise big-O lower bounds are elusive. I would split this into 2 classes: problems, where we know of ...
• 920
1k views

### What podcast should everybody listen to?

This list was inspired by the lists: What are the popular science books that inspire TCS? What Books Should Everyone Read? What papers should everyone read? What videos should everybody watch? I don'...
263 views

### What are the consequences of a faster algorithm for $CIRCUIT$-$SAT$?

What is the best algorithm known for $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates? What is the consequence if there is an $\alpha\in(0,1)$ such that $CIRCUIT$-$SAT$ in $n$ variables and $m$ gates ...
• 539
419 views

### Site with collection of exercises in TCS?

Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online ...
• 14k
392 views

### A canonical complete problem for EXP and NEXP in terms of formulae

3SAT is a complete problem for NP. TQBF is a complete problem for PSPACE. Is there direct way to define canonical complete problems for EXP and NEXP in terms of boolean formulae? I have only seen ...
• 12.9k
6k views

### Most important new papers in computational complexity

We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers ...
127 views

• 12.9k
1k views

### Research problems in communication complexity

There have been many open challenges questions in this forum. For instance, Research and open challenges in Programming Language Theory What are current open problems in compiler theory? ...
• 12.9k
1k views

### Problems not known to be PSPACE-complete

What are problems with the following properties: 1) they are restriction of (possibly well known) problems that are PSPACE-complete; 2) the restricted versions are in PSPACE, but it is an open ...
3k views

### Problems with big open complexity gaps

This question is about problems for which there is a big open complexity gap between known lower bound and upper bound, but not because of open problems on complexity classes themselves. To be more ...
• 8,883
879 views

### How would a theory of computation course that culminated in lambda-calculus as "the" model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
• 5,325
325 views

### Introductions to steganography from an information-theoretic standpoint

Can I get some introductory references for steganography from an information-theoretic standpoint? I recently listened to a talk on it, and the speaker said that he knew of no good introductions to ...
• 143