Hot answers tagged

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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
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 ...
user avatar
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), ...
user avatar
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
user avatar
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 ...
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 ...
user avatar
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. ...
user avatar
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,...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
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
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