Questions tagged [big-list]

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

Filter by
Sorted by
Tagged with
4
votes
0answers
145 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
0answers
60 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 ...
19
votes
14answers
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 ...
-2
votes
1answer
163 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 ...
13
votes
3answers
397 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 ...
3
votes
0answers
123 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 ...
9
votes
4answers
711 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'...
5
votes
1answer
244 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 ...
5
votes
1answer
245 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 ...
8
votes
0answers
208 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 ...
36
votes
10answers
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
0answers
118 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 $...
21
votes
2answers
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 ...
5
votes
0answers
129 views

Dequantumizability known and unknown?

Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
7
votes
1answer
223 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 ...
4
votes
0answers
86 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$?
1
vote
0answers
84 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. ...
3
votes
0answers
65 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 ...
2
votes
1answer
614 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 ...
3
votes
2answers
233 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 ...
-1
votes
1answer
116 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 ...
8
votes
4answers
842 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 ...
7
votes
4answers
295 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 ...
17
votes
1answer
455 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 ...
8
votes
3answers
667 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....
-1
votes
1answer
195 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 ...
9
votes
2answers
646 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 ...
15
votes
3answers
1k 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 ...
3
votes
0answers
225 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 "...
11
votes
2answers
343 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-...
8
votes
2answers
279 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. ...
3
votes
1answer
387 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-...
11
votes
2answers
843 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 ...
12
votes
7answers
782 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 ...
14
votes
9answers
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 ...
25
votes
2answers
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 ...
2
votes
1answer
98 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 ...
12
votes
2answers
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 ...
5
votes
2answers
968 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
votes
4answers
951 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 ...
34
votes
8answers
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
votes
2answers
748 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 ...
4
votes
1answer
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 ...
2
votes
2answers
194 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,...
10
votes
1answer
570 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 ...
2
votes
1answer
281 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?
3
votes
1answer
492 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 (...
7
votes
4answers
586 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 ...
18
votes
2answers
924 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.
23
votes
5answers
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 ...