# Tag Info

5

I believe what you're looking for is the field of Experimental Algorithmics. There is a text by McGeoch, an ACM Journal, and a previous question on this site that provides a reading list for the field.

1

Although others have pointed out the answer. I thought I may make it self-contained and show why teaching dimension is the answer. Consider a concept class $C$ over input space $X$. A set of elements $S\subseteq X$ is called a teaching set for a concept $f$ if $f$ is the only concept in $C$ consistent with $S$. Let $\mathcal{T}(f)$ be the set of all ...

1

I recommend the following books: Khalid Sayood "Introduction to DATA COMPRESSION" Khalid Sayood "Lossless Compression Handbook" David Salomon "Handbook of Data compression" And a little more specific, but also good books in this field: Timothy Bell "Text compression" Donald Adjeroh, Timothy Bell, Amar Mukherjee "The Burrows-Wheeler Transform: Data ...

3

In the PRAM model without bit operations, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1]. Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial ...

3

A paper by Abboud et al. recently accepted to SODA 2016 shows that subtree isomorphism cannot be solved in $O(n^{2-\epsilon})$ time unless the strong exponential time hypothesis is false. Of course, we can verify an isomorphism in linear time. In other words, the SETH gives us a natural problem in $\sf{P}$ with an $\Omega(n^{1-\epsilon})$ gap between ...

2

In Slide 26, Martin Escardo provides an algorithm that might give you what you're looking for: Go the library. Pick a book on topology. Pick a theorem. Apply the dictionary. Get a theorem in computation. http://www.cs.bham.ac.uk/~mhe/.talks/popl2012/escardo-popl2012.pdf See also this paper

11

There have been a number of developments with regards to the use of monads in the theory of computation since Eugenio Moggi's work. I am not able to give a comprehensive account, but here are some points that I am familiar with, others can chime in with their answers. Specific examples of monads You do not have to study super-general theory all the time. ...

0

This paper gives some important recent work using monads.

4

The paper, Knowledge, Creativity and P versus NP by Avi Wigderson is an excellent exposition of the P vs NP problem's implications on the philosophical question of automating creativity.

3

some of what you refer to is covered under a general heading known as "digital physics" or digital philosophy which has a continuing thread of research in physics albeit not always mainstream. a notable example of a TCS paper/ survey with major philosophical angles/ analysis Why Philosophers Should Care About Computational Complexity / Aaronson another ...

11

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book. The hardness proof is due to Lovasz in this paper.

2

From Recursive Functions article on SEP: The use of recursion goes back to the 19th century. Dedekind [1888] used the notion to obtain functions needed in his formal analysis of the concept of natural number. In logic, recursion appears in Skolem [1923], where it is noted that many basic functions can be defined by simple applications of the method. The ...

2

Maybe slightly tangential to the original question, but the blog entry "How recursion got into programming: a comedy of errors" describes an interesting part of early computing history.

6

The "inverse" is almost the same as SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in $O(n^{2-\epsilon})$ time. To show this, it seems that you would need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$. This kind of reduction would be ...

1

relatively recent results by Backurs, Indyk accepted to STOC 2015 that computing edit distance in $O(n^{2-\epsilon})$ time → SETH false tie in neatly/ strong to the new emerging "fine grained complexity" research program/ paradigm. they are closely related to/ built on Williams result that SETH → Orthogonal Vectors conjecture. (even covered by the mainstream ...

6

The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. Why do we assume that RSA is secure? We don't have any particular justification for its classical hardness other than the fact that no one has found any fast ...

9

I think that many examples come from NP-complete problems that fall in P when we fix one or more parameters. For example, checking if a graph contains a clique of size $k$ is NP-complete if $k$ is part of the input, polynomial-time solvable if $k$ is fixed. For any fixed $k$, the verification takes linear time, but unless $P=NP$, the search problem ...

9

Deciding primality: the best known variant of AKS appears to decide primality in time $\tilde{O}(n^6)$, whereas the classical Pratt certificate of primality implies primality can be decided in nondeterministic time $\tilde{O}(n^3)$.

16

Deciding if a value exists in an array takes time $\Omega(n)$ (or $\Omega(\log n)$ if the array is sorted). Verifying that an array contains the given value at a given position is possible in time $O(1)$. Sorting (in the comparison model) takes time $\Omega(n \log n)$, but verifying that an array or list is sorted is possible in time $O(n)$.

23

it is known that given a graph G and a tree T, it can be verified in linear time that T is a minimum spanning tree of G. But we don't yet have a deterministic linear time algorithm to compute the MST. Of course the gap is tiny (1 vs $\alpha(n)$), but it's still there :))

18

For some problems there seems to be no difference. In particular, Vassilevska Williams & Williams show: for Boolean matrix multiplication, computing the matrix product and verifying the matrix product subcubic-equivalent, meaning that they either both have subcubic-time algorithms or neither of them do. The same is true for matrix product computation ...

19

This paper shows that there are verification algorithms for both YES and NO instances for 3 problems, including Max flow, 3SUM, and APSP, which are faster by a polynomial factor than the known bounds for computing the solution itself. There is a class of problems, namely the ones which improving the running time is SETH-hard, whose the running time for ...

Top 50 recent answers are included