Tag Info

483

Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be ...

347

I have personally enjoyed several Aha! moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole. Does Non-determinism Lead to Efficiency? There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. ...

100

$\lambda$-calculus has two key roles. It is a simple mathematical foundation of sequential, functional, higher-order computational behaviour. It is a representation of proofs in constructive logic. This is also known as the Curry-Howard correspondence. Jointly, the dual view of $\lambda$-calculus as proof and as (sequential, functional, higher-order) ...

62

If you really want to know what led Neil Robertson and me to tree-width, it wasn't algorithms at all. We were trying to solve Wagner's conjecture that in any infinite set of graphs, one of them is a minor of another, and we were right at the beginning. We knew it was true if we restricted to graphs with no k-vertex path; let me explain why. We knew all such ...

58

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of ...

44

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the ...

40

PageRank is one of the best-known such algorithms. Developed by Google co-founder Larry Page and co-authors, it formed the basis of Google's original search engine and is widely credited with helping them to achieve better search results than their competitors at the time. We imagine a "random surfer" starting at some webpage, and repeatedly clicking a ...

34

There are many good theoretical reasons to study N/DFAs. Two that immediately come to mind are: Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and natural limitation (taking away ...

34

I would mention the widely-used software CPLEX (or similar) implementation of the Simplex method/algorithm for solving linear programming problems. It is the (?) most used algorithm in economy and operations research. "If one would take statistics about which mathematical problem is using up most of the computer time in the world, then (not counting ...

33

A flip answer is that this isn't the first thing about complexity theory that I'd try to explain to a layperson! To even appreciate the idea of nonuniformity, and how it differs from nondeterminism, you need to be further down in the weeds with the definitions of complexity classes than many people are willing to get. Having said that, one perspective that ...

32

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or even forgotten. Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the Entscheidungsproblem. This is ...

31

To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines. Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything is decidable. Language equality, inclusion, emptiness and universality are all ...

30

As I understand it, the National Resident Matching Program was for a long time just a straight application of the Gale-Shapley algorithm for the stable marriage problem. It has since been slightly updated to handle some extra details like spousal assignments (aka the "two-body problem"), etc...

30

There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for it comes from Coppersmith's paper "Rapid multiplication of rectangular matrices", but the explanation for why it leads to $N^2 \operatorname{polylog}\left(N\... 28 I think$\lambda$-calculus has contributed in many ways to this field, and still contributes to it. Three examples follow, and this is not exhaustive. Since I am not a specialist in$\lambda$-calculus, I certainly miss some important points. First, I think having different models of computation that turn out to represent the exact same set of functions was ... 28 Here is a "smoothness" argument that I heard recently in defense of the claim that non-uniform models of computation should be more powerful than we suspect. On one hand, we know from the time hierarchy theorem that there are functions computable in time$O(2^{2n})$that are not computable in time$O(2^{n})$, for example. On the other hand, by Lupanov's ... 28 Grothendieck's inequality, from his days in functional analysis, was initially proved to relate fundamental norms on tensor product spaces. Grothendieck called the inequality "the fundamental theorem of the metric theory of tensor product spaces", and published it in a now famous paper in 1958, in French, in a limited circulation Brazilian journal. The paper ... 27 State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient ... 26 He wanted to create a formal system for the foundations of logic and mathematics that was simpler than Russell's type theory and Zermelo's set theory. The basic idea was to add a constant$\Xi$to the untyped lambda calculus (or combinatory logic) and interpret$XZ$as expressing "$Z$satisfies the predicate$X$" and$\Xi XY$as expressing "$X\subseteq Y$". ... 25 It's not a single problem, but the entire field of analytic combinatorics (see the book by Flajolet and Sedgewick) explores how to analyze the combinatorial complexity of counting structures (or even algorithm running times) by writing down an appropriate generating function and analyzing the structure of the complex solutions. 24 If you're also including PhD-level stuff, many (most?) graduate CS programs include some course in coding theory. If you have a course in coding theory, you will definitely cover the Reed-Solomon code which is integral to how compact discs work and Huffman encoding which is used in JPEG, MP3, and ZIP file formats. Depending on the orientation of the course, ... 24 Very briefly: the simply-typed$\lambda$-calculus does not have dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from propositional to first-order logic. The key contribution of Martin-Löf's is a novel analysis of equality. There are two main ways of giving Curry-Howard style ... 22 GNU grep is a command line tool for searching one or more input files for lines containing a match to a specified pattern. It is well-known that grep is very fast! Here's a quote from its author Mike Haertel (taken from here): GNU grep uses the well-known Boyer-Moore algorithm, which looks first for the final letter of the target string, and uses a lookup ... 22 Apart from the foundational role of the$\lambda$-calculus, which was mentioned in all other answers, I would like to add something on What exactly did the lambda calculus do to advance the theory of CS? I believe that concurrency theory is one field of CS which has been tremendously influenced by the compositional view mentioned by Martin Berger. Of ... 21 It's a little vague, but I like the question. I wrote a paper about it a LONG time ago. Maybe this will help the Anonymous questioner: Brute Force Search and Oracle-Based Computation Here's a summary. Informally, if you do not keep any scratch work from previous trials, and just try all possible solutions in lexicographical order until a desired ... 21 Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly automatic groups (groups in which the elements can be represented by strings in a regular ... 21 I can see three related ways to understand the question: 1) Can we we regard$NP \ne P$as a fundamental principle of computational complexity theory, even before we can prove it? 2) Does the$NP \ne P$principle extends beyond its narrow mathematical meaning? 3) Does the$NP \ne P\$ principle can be regarded as a physical law. I think that there are ...

20

Your question itself is not naive but the type of answer you ask for is. It is rare for any line of work or intellectual enquiry to have an elevator pitch explanation. Not all would agree with your characterizations of mathematics and physics because they ignore the depth and nuances of those fields. Theoretical computer scientists are concerned with ...

19

Some graph classes allow polynomial-time algorithms for problems that are NP-hard for the class of all graphs. For instance, for perfect graphs, one can find a largest independent set in polynomial time (thanks to vzn in a comment for jogging my memory). Via a product construction, this also allows a unified explanation for several apparently quite ...

19

Lattice-basis reduction (LLL algorithm). This the basis for efficient integer polynomial factorization and some efficient cryptanalytic algorithms like breaking of linear-congruential generators and low-degree RSA. In some sense you can view the Euclidean algorithm as a special case.

Only top voted, non community-wiki answers of a minimum length are eligible