13
votes
Sensitivity-Block sensitivity conjecture - Implications
Here is what Scott Aaronson has to say on the subject:
What makes this interesting is that block-sensitivity is known to be polynomially related to a huge number of other interesting complexity ...
- 14.1k
13
votes
Applications of $p$-adic numbers in CS
De, Kurur, Saha and Saptharishi gave a modular version of Fürer's integer multiplication algorithm in their paper Fast integer multiplication using modular arithmetic, in which the p-adic numbers ...
- 14.1k
12
votes
Applications of topology to computer science
Nobody has yet mentioned directed algebraic topology, which was in fact developed to provide a suitable algebraic topological toolbox for the study of concurrency.
There are also several low ...
- 357
11
votes
What's the relation between OOP and category theory?
There are absolutely some relationships between the semantics and practice of OOP and category theory. This is somewhat unsurprising since both fields attempt to give a principled generic account of ...
- 13.2k
10
votes
Accepted
Are there survey papers in theoretical computer science?
Yes!
These survey series come to mind:
Foundations and Trends in TCS (many authors put a free version on their web page)
Theory of Computing Graduate Surveys
SIGACT News Complexity Column (and also ...
- 35.7k
10
votes
Research problems in communication complexity
I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity.
It's hard to say what areas a new communication complexity researcher ...
- 515
10
votes
Applications of $p$-adic numbers in CS
Hensel lifting is very closely related to the $p$-adics: it's basically getting a better and better approximation to a $p$-adic number, "better" in the sense of "closer in the $p$-adic valuation. ...
- 35.7k
8
votes
Uses of algebraic structures in theoretical computer science
Algebra (and algebraic geometry) has had a pretty big role to play in cryptography, with elliptic curve groups, (number-theoretic) lattices, and of course $\mathbb{Z}_p$ being the basis for nearly all ...
6
votes
Applications of algebraic geometry in Boolean complexity
In addition to the Geometric Complexity Theory Program already mentioned by Sasho Nikolov (see e.g. here, and - shameless self plug, but has tons of references on uses of AG in complexity - here), ...
- 35.7k
6
votes
Applications of $p$-adic numbers in CS
There are also some computational models:
Here is the first paper: Rusins Freivalds: Ultrametric automata and Turing machines. Turing-100 2012: 98-112
- 3,647
6
votes
Research problems in communication complexity
Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger).
Razborov's 2011 ...
- 18.7k
5
votes
What's the relation between OOP and category theory?
Bart Jacobs tackled this problem at one point. In his view, classes can be considered as coalgebras. Roughly, we have a polynomial endofunctor $F : \mathbf{Sets} \to \mathbf{Sets}$ which gives the ...
- 193
5
votes
Survey on Erdős-Pósa?
I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written:
Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. ...
- 5,424
5
votes
Sensitivity-Block sensitivity conjecture - Implications
As I understand it, the original motivation was to study CREW PRAM (consecutive read exclusive write parallel RAM) model. In this model, several processors compute a function with shared memory access,...
- 377
4
votes
Applications of $p$-adic numbers in CS
here is a nice general survey with a brief overview of diverse (recent) CS applications for p-adic theory, p3
What are p-Adic Numbers? What are They Used for? / Rozikov
Here are areas where p-adic ...
- 10.8k
3
votes
What hierarchies and/or hierarchy theorems do you know?
From this question on cs.stackexchange, I became aware of the genus hierarchy of regular languages. Essentially, you can characterize regular languages based on the minimum genus surface in which the ...
3
votes
What hierarchies and/or hierarchy theorems do you know?
Elaborating on one of the bullet points mentioned by the OP (GoldreichKNR09): there are several hierarchy theorems in property testing and proofs of proximity, relating to the query complexity, the ...
2
votes
Computational complexity in quantitative finance
From SSRN, two papers related to the complexity of portfolio optimization:
Walter Murray, Howard Howan Stephen Shek, A Local Relaxation Method for Cardinality Constrained Portfolio Optimization ...
2
votes
Important papers and open problems in Boolean functions
Bryant's "Graph-Based Algorithms for Boolean Function Manipulation" introduced Reduced-Order Binary Decision Diagrams (ROBDDs) for representing and manipulating Boolean functions. I believe these see ...
- 967
1
vote
Computational complexity in quantitative finance
Predicting the stock market is hard! Can TCS make this sentiment more formal?
If stocks are modeled as random variables like geometric Brownian motions then prediction becomes a concern of ...
- 4,400
1
vote
Uses of algebraic structures in theoretical computer science
In functional programming, the most general and elegant abstractions for problems are often algebraic (or category-theoretic) in nature: monoids, semirings, functors, monads, F-algebras, F-coalgebras, ...
- 1,125
1
vote
Uses of algebraic structures in theoretical computer science
Recently, we explore (see our paper on springerlink: A formal series-based unification of the frequent itemset mining approaches) a unification attempt to pattern mining (a popular instance of data ...
1
vote
What hierarchies and/or hierarchy theorems do you know?
Consider the Unambiguous Polynomial Hierarchy, reference here, original reference here for the unambiguous polynomial hierarchy(paywalled). While studying the Boolean hierarchy BH, and classes such ...
1
vote
What hierarchies and/or hierarchy theorems do you know?
The Polynomial Hierarchy in communication complexity as defined by Babai, Frankl, and Simon (see the original paper here and without the paywall here). The significance of this hierarchy is hard to ...
1
vote
Is there any good and free Introduction to topological graph theory
Archdeacon's survey Topological Graph Theory was almost mentioned already:
http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf
- 4,400
1
vote
Where and how did computers help prove a theorem?
A paper of mine with Gupta and Kumar titled On a bidirected relaxation for the MULTIWAY CUT problem was also based on running experiments. In fact we were trying to prove the converse of what we ended ...
1
vote
Where and how did computers help prove a theorem?
My recent paper with Karthik Chandrasekharan titled Hypergraph $k$-cut in deterministic polynomial time was based on extensive computational experiments. We explored different conjectures and ...
1
vote
Where and how did computers help prove a theorem?
Some recent results in state complexity were found with the help of systematic brute-force search for worst-case examples. This is doable because there are not too many deterministic finite automata ...
1
vote
Where and how did computers help prove a theorem?
In 2018, Aubrey de Grey found a 1581-vertex, non-4-colourable unit-distance graph. This gives a lower bound of five for the famous Hadwiger-Nelson problem. He used a computer to verify that the graph ...
Only top scored, non community-wiki answers of a minimum length are eligible