Hot answers tagged

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 ...
cody's user avatar
  • 13.8k
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 ...
Joshua Grochow's user avatar
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 ...
Pratyush Mishra's user avatar
8 votes
Accepted

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. ...
Hermann Gruber's user avatar
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 ...
Kevin Clancy's user avatar
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

What hierarchies and/or hierarchy theorems do you know?

Lasserre Hierarchy: An Hierarchy of progressively stronger (i.e., tighter, in the sense of integrality gaps) SDP relaxations of fractional polytopes J. Lasserre. An explicit exact SDP relaxation for ...
2 votes

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, ...
xrq's user avatar
  • 1,175
2 votes

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 ...
Slimane Oulad-Naoui's user avatar
1 vote

Uses of algebraic structures in theoretical computer science

Most answers on this page are research-oriented. They answer the question: what algebraic structures will help us publish more theoretical papers on computer science. But most of those theoretical ...
winitzki's user avatar
  • 304
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 ...
Bjørn Kjos-Hanssen's user avatar
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
Bjørn Kjos-Hanssen's user avatar
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