Questions tagged [big-list]

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

Filter by
Sorted by
Tagged with
5 votes
3 answers
179 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#...
TomKern's user avatar
  • 379
21 votes
10 answers
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 ...
Per Alexandersson's user avatar
7 votes
2 answers
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 ...
Command Master's user avatar
4 votes
0 answers
76 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 ...
TomKern's user avatar
  • 379
2 votes
0 answers
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 ...
user76284's user avatar
  • 662
4 votes
0 answers
174 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 ...
Matthieu Latapy's user avatar
1 vote
0 answers
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 ...
Turbo's user avatar
  • 12.8k
21 votes
14 answers
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 ...
Ville Salo's user avatar
-2 votes
1 answer
186 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 ...
Turbo's user avatar
  • 12.8k
15 votes
3 answers
663 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 ...
Johana T.'s user avatar
  • 151
3 votes
0 answers
134 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 ...
Ilk's user avatar
  • 920
11 votes
4 answers
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'...
Raphael Augusto's user avatar
5 votes
1 answer
259 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 ...
VS.'s user avatar
  • 539
5 votes
1 answer
412 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 ...
domotorp's user avatar
  • 13.8k
8 votes
0 answers
384 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 ...
Turbo's user avatar
  • 12.8k
36 votes
10 answers
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 ...
3 votes
0 answers
127 views

Examples of ineffective PH collapse theorems?

What are some examples of theorems of the form "If $X$, then $PH$ collapses", but where the proof does not say which level $PH$ collapses to? The canonical example would be "If $PH = PSPACE$, then $...
Geoffrey Irving's user avatar
21 votes
2 answers
2k views

Languages that we cannot (dis)prove to be Context-Free

I'm looking for languages which are "probably not Context-Free" but we are not able to (dis)prove it using known standard techniques. Is there a recent survey on the subject or an open problem ...
Marzio De Biasi's user avatar
5 votes
0 answers
186 views

Dequantumizability known and unknown?

Dequantumizable problems have been taking some headlines these days (for example this blog post by Scott Aaronson and this article in Quantum Magazine). What are some problems that are currently ...
Turbo's user avatar
  • 12.8k
7 votes
1 answer
233 views

Where do people publish/submit their work on type theory?

Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published? Especially, I'm looking for more "pure mathematical" venues/journals which ...
xrq's user avatar
  • 1,175
5 votes
1 answer
153 views

Problems which will be in $NC$ if fixed dimension Linear Integer Programming in $NC$

We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
Turbo's user avatar
  • 12.8k
1 vote
0 answers
121 views

A categorized (?) list of functional pearls in JFP and ICFP

Is there a list of (categorized preferred) functional pearls ever published in ICFP and JFP? I could go to the ICFP proceedings and JFP issues and find all of them, but this would be time-consuming. ...
xrq's user avatar
  • 1,175
3 votes
0 answers
69 views

Problems and theories in CS that uses Fibonacci numbers

I want to know problems and theories where Fibonacci sequence is used and where we have some possibility to use Fibonacci numbers. I have found that- In counting number of steps for Euclidean ...
tarit goswami's user avatar
3 votes
1 answer
699 views

Possible to do Complexity theory with only counting and Pigeonhole

Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
Turbo's user avatar
  • 12.8k
3 votes
2 answers
446 views

Examples/Textbooks on amortized analysis of algorithms

I am trying to get the amortized analysis for a complicated algorithm. I am wondering whether there are textbooks or illustrative examples that could serve as inspiration of techniques in amortized ...
shuhalo's user avatar
  • 1,165
-1 votes
1 answer
131 views

Special cases of hard counting problems that are easy

We know that bipartite planar perfect matching count is easy, permanent mod $3^t$ is easy for orthogonal matrices, permanent mod $2$ is easy, bounded rank permanent is easy. Outside of permanent ...
Turbo's user avatar
  • 12.8k
8 votes
4 answers
1k views

Stephen Hawking's impact on computer science

In light of Stephen Hawking passing away today, I was wondering whether any of his results have direct impact on cs? The obvious candidate would be in quantum computing, or rather the construction ...
Shaull's user avatar
  • 5,571
7 votes
4 answers
317 views

What are semantic classes that have a syntactic equivalent?

This question is related to Benefits for syntactic and semantic classes. As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a ...
domotorp's user avatar
  • 13.8k
17 votes
1 answer
511 views

List of (unsolved) complexity problems arising from PL

What are some major, open computational complexity problems that arise from programming languages, especially program analysis and compilation? I am looking for problems on the lines of "the time ...
xrq's user avatar
  • 1,175
9 votes
3 answers
839 views

What CS theories are absolutely paramount for someone new to TCS to understand? [closed]

First - I'm happy to be a part of this community. Electronics and software engineering are both my passion and my profession, yet I feel as if I'm missing a solid basis in theoretical computer science....
iangolden's user avatar
  • 109
-1 votes
1 answer
200 views

Can message passing help in GI related problems?

Can message passing algorithms like those used in https://arxiv.org/pdf/1704.00395.pdf be useful in showing GI testing is in P? Note message passing is prominent in AI and has been tried in decoding ...
Turbo's user avatar
  • 12.8k
10 votes
2 answers
833 views

What are some interesting applications of homotopical algebra in theoretical computer science?

I am an homotopy theorist, interested in computer science. I would like to ask what are some interesting applications of homotopical algebra (model categories, infinity categories, simplicial ...
user40853's user avatar
  • 101
16 votes
5 answers
2k views

Examples of successful derandomization from BPP to P

What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)? The only example that comes ...
user avatar
3 votes
0 answers
236 views

New proofs from "The Book" [closed]

The book "Proofs from The Book", referencing Erdős' notion of God's book, which contains the most beautiful proofs, was published in 1998. Are there any new proofs that should be considered for "...
Shaull's user avatar
  • 5,571
12 votes
2 answers
381 views

Major open problems on polynomial kernel (non) existence

We are not able to settle the (non-)existence of a polynomial kernel for a parameterized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non-...
Marzio De Biasi's user avatar
8 votes
2 answers
300 views

Uncertainties in GCT program

In https://en.wikipedia.org/wiki/Geometric_complexity_theory it is mentioned that ".. Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. ...
Turbo's user avatar
  • 12.8k
3 votes
1 answer
417 views

Log Rank Conjecture Collaborative Approach [closed]

Recently a post was made in Mathoverflow seeking possible avenues for collaborative projects. I made a proposal for Log Rank conjecture in https://mathoverflow.net/questions/219638/proposals-for-...
10 votes
2 answers
924 views

Problems with no known quantum advantage

I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer. To start things off, I think computation of ...
Simd's user avatar
  • 3,902
14 votes
7 answers
1k views

Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

What are some (not well-known) assertions that if true, the PH must collapse? Replies containing a short high-level assertion with reference(s) are appreciated. I tried to reverse-search without much ...
user34344's user avatar
  • 141
14 votes
9 answers
1k views

Counterintuitive results for undergraduates

I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get ...
Anonymous's user avatar
  • 4,031
26 votes
2 answers
1k views

Complexity zoo for unary languages

Of course, some complexity results may collapse for unary languages but I wonder if there is somewhere a survey summarizing the known results in this case: a kind of complexity zoo for unary ...
J.-E. Pin's user avatar
  • 4,781
2 votes
1 answer
102 views

List of papers on Runtime and Statistical Tradeoffs on Machine Learning

I was interested in the connection between (statistical) learning guarantees (or any statistical properties) and their relation to run time. For example, I was wondering, in what cases does having ...
Charlie Parker's user avatar
12 votes
2 answers
1k views

List of number theoretic or algebraic problems in various complexity classes

I am looking for a list about the known or unknown complexity of various number theoretic /algebraic problems. For example, GCD in $NC^1$ is open, factoring in $P$ is open, computing sheaf ...
Turbo's user avatar
  • 12.8k
5 votes
2 answers
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? ...
Turbo's user avatar
  • 12.8k
12 votes
4 answers
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 ...
Marzio De Biasi's user avatar
37 votes
8 answers
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 ...
Denis's user avatar
  • 8,678
8 votes
2 answers
870 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 ...
PhD's user avatar
  • 5,275
4 votes
1 answer
324 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 ...
ok_'s user avatar
  • 143
2 votes
2 answers
267 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness assumptions,...
Vinicius dos Santos's user avatar
10 votes
1 answer
640 views

What are the major research issues in distributed transactions?

Background: Transaction processing has been a traditional research topic in database theory. Nowadays distributed transactions are popularized by the large-scale distributed storage systems which ...
hengxin's user avatar
  • 2,329