2022 Developer Survey is open! Take survey.

Questions tagged [big-list]

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

Filter by
Sorted by
Tagged with
4 votes
0 answers
168 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 ...
user avatar
1 vote
0 answers
63 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 ...
user avatar
  • 12.5k
19 votes
14 answers
2k 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 ...
user avatar
-2 votes
1 answer
171 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 ...
user avatar
  • 12.5k
13 votes
3 answers
469 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 ...
user avatar
  • 131
3 votes
0 answers
126 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 ...
user avatar
  • 713
10 votes
4 answers
901 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'...
user avatar
5 votes
1 answer
256 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 ...
user avatar
  • 529
5 votes
1 answer
306 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 ...
user avatar
  • 13.5k
8 votes
0 answers
253 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 ...
user avatar
  • 12.5k
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
120 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 $...
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 ...
user avatar
5 votes
0 answers
172 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 ...
user avatar
  • 12.5k
7 votes
1 answer
227 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 ...
user avatar
  • 1,125
4 votes
0 answers
87 views

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$?
user avatar
  • 12.5k
1 vote
0 answers
96 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. ...
user avatar
  • 1,125
3 votes
0 answers
68 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 ...
user avatar
3 votes
1 answer
659 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 ...
user avatar
  • 12.5k
3 votes
2 answers
311 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 ...
user avatar
  • 1,145
-1 votes
1 answer
117 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 ...
user avatar
  • 12.5k
8 votes
4 answers
911 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 ...
user avatar
  • 5,246
7 votes
4 answers
300 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 ...
user avatar
  • 13.5k
17 votes
1 answer
476 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 ...
user avatar
  • 1,125
9 votes
3 answers
736 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....
user avatar
  • 109
-1 votes
1 answer
199 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 ...
user avatar
  • 12.5k
10 votes
2 answers
724 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 ...
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
230 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 "...
user avatar
  • 5,246
11 votes
2 answers
370 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-...
user avatar
8 votes
2 answers
284 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. ...
user avatar
  • 12.5k
3 votes
1 answer
403 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
889 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 ...
user avatar
  • 3,910
13 votes
7 answers
911 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 ...
user avatar
  • 131
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 ...
user avatar
  • 3,993
25 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 ...
user avatar
  • 4,721
2 votes
1 answer
100 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 ...
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 ...
user avatar
  • 12.5k
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? ...
user avatar
  • 12.5k
12 votes
4 answers
980 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 ...
user avatar
36 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 ...
user avatar
  • 7,643
8 votes
2 answers
817 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 ...
user avatar
  • 5,157
4 votes
1 answer
322 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 ...
user avatar
  • 143
2 votes
2 answers
233 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,...
user avatar
10 votes
1 answer
618 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 ...
user avatar
  • 2,319
2 votes
1 answer
283 views

State of the art algorithms for community detection in graphs

Is anyone aware of the must read papers to get knowledge of the most recent algorithms and method for community detection in graphs, especially those that represent social networks?
user avatar
3 votes
1 answer
525 views

Important papers and open problems in Boolean functions

I am interested in Boolean function polynomial/rational exact/approximate/one sided approximate representation, relation to circuit/communication complexity, tools utilized to study Boolean functions (...
user avatar
  • 12.5k
7 votes
4 answers
656 views

Explaining computer science algorithms/concepts/ideas using metaphors

Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
user avatar
  • 2,319
18 votes
2 answers
937 views

Long-Standing Conjectures later trivially proved by an implication

I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.
user avatar
  • 545
23 votes
5 answers
4k views

EXPSPACE-complete problems

I am currently trying to find EXPSPACE-complete problems (mainly to find inspiration for a reduction), and I am surprised by the small number of results coming up. So far, I found these, and I have ...
user avatar
  • 7,643