Vijay D
  • Member for 10 years, 10 months
  • Last seen more than 2 years ago
  • Berkeley, CA
Core algorithms deployed
Accepted answer
488 votes

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 ...

View answer
What is the enlightenment I'm supposed to attain after studying finite automata?
Accepted answer
352 votes

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 ...

View answer
How practical is Automata Theory?
33 votes

Can you hear that noise? It is the sound of a thousand brilliant theorems, applications and tools laughing in automata-theoretic heaven. Languages and automata are elegant and robust concepts that ...

View answer
Most memorable CS paper titles
30 votes

I used to like quirky titles when I started out in computer science but got bored eventually. Some authors manage to write titles that are clever, memorable and relevant but most attempts at funny ...

View answer
Applications of topology to computer science
30 votes

Topology is such a mature discipline with varied subfields including geometric, algebraic, metric, point-set and (the self deprecating) pointless topology. Computer science is also fairly broad and ...

View answer
Beautiful results in TCS
22 votes

The undecidability of the halting problem. Beautiful for many reasons. It is an impossibility result. The proof uses diagonalisation. The statement applies to a broad range of models of computation. ...

View answer
A topological space related to SAT: is it compact?
22 votes

What you are doing is deriving a topological representation of a Boolean algebra. The study of representations of Boolean algebras goes back at least to Lindenbaum and Tarski who proved (in 1925, I ...

View answer
What is theoretical computer science?
20 votes

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 ...

View answer
Why can machine learning not recognize prime numbers?
19 votes

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction. There are two fields ...

View answer
Do past time LTL and future time LTL have the same expressiveness?
Accepted answer
18 votes

The quick summary is that LTL with only past and no future modalities defines properties expressed over finite-words and these are the star-free subset of the regular languages. Standard LTL when ...

View answer
Starting SAT solver papers
18 votes

An excellent beginner overview is given by the following article from 2009. Boolean Satisfiability: From Theoretical Hardness to Practical Success, Sharad Malik, Lintao Zhang, Communications of the ...

View answer
What is the goal behind abstract interpretation in programming languages?
Accepted answer
17 votes

Abstract interpretation is a very general concept and depending on whom you ask, you will receive different explanations because versatile concepts admit multiple perspectives. The view in this answer ...

View answer
How can I use my computational theory and analysis powers for the greater good?
Accepted answer
16 votes

Please read William Thurston's answer to the question What's a mathematician to do? on mathoverflow. Just to convince you that it is a must-read, let me quote him. The product of mathematics is ...

View answer
Pointers for CS applications of logic
15 votes

I briefly reviewed some areas here, trying to focus on ideas that would appeal to someone with a background in advanced mathematical logic. Finite Model Theory The simplest restriction of classical ...

View answer
What algorithms exist for construction a DFA that recognizes the language described by a given regex?
Accepted answer
15 votes

There are different algorithms to convert regular expressions to finite automata. You can go directly from regular expressions to DFAs without building any other automaton first by implicitly doing ...

View answer
Is there a hidden link between the existence uncountable sets and the undecidability of the halting problem?
Accepted answer
14 votes

It's not a hidden link but one that has been made explicit using the language of category theory and also a very natural question to ask and study. There is a fair bit of material on the subject. CS ...

View answer
Enumerate all solutions of a SAT problem
Accepted answer
14 votes

You are looking for an ALL-SAT or all solutions SAT solver. This is a different problem from #SAT. You do not have to enumerate all solutions to count them. I do not know of a tool that solves your ...

View answer
Uses of algebraic structures in theoretical computer science
13 votes

Lattices and fixed points are at the foundations of program analysis and verification. Though advanced results from lattice theory are rarely used because we are concerned with algorithmic issues such ...

View answer
Casual tours around proofs
13 votes

(This started out as a comment and got way way way too long). You may enjoy William Thurston's article On Proof and Progress in Mathematics. Mathematics in some sense has a common language: a ...

View answer
Regular languages from category-theoretical point of view
12 votes

Actually, I think what you're looking for is Kleene algebra. See Dexter Kozen's classic article. He gives an axiomatization of Kleene-star. I assume this is the very first step you're interested in. ...

View answer
Automated theorem proving via unsupervised approaches
Accepted answer
12 votes

Clarification on terminology The theorem proving community does not use the terms supervised and unsupervised. They use the terms interactive theorem proving or automated theorem proving. If you give ...

View answer
Practical applications of parity games
Accepted answer
11 votes

Here is a rather different application from what you may have had in mind. Linear programming has many practical applications. There are many algorithms for linear programming and those based on ...

View answer
To what extent can an algorithm predict the time complexity an arbitrary input program?
11 votes

The question you pose and the specific counting trick you describe is a classic one in program analysis. There is the theoretical problem of complexity analysis, and it's practical manifestation in ...

View answer
Alan Turing's Contributions to Computer Science
11 votes

Turing's paper on Checking a large routine which was presented at a conference in Cambridge in 1949 antedates formal reasoning about programs as developed by Floyd and Hoare by nearly two decades. The ...

View answer
Beautiful results in TCS
11 votes

Shannon's source and channel coding theorems. A mathematical definition that distinguished between the transmitted, receiver and medium and which ignored the semantics of the message was a big step. ...

View answer
What's the correlation between treewidth and instance hardness for random 3-SAT?
Accepted answer
10 votes

Not really an answer but the closest references I am aware of. There are results available for branch-width. Also, there is at least one empirical study of treewidth of industrial instances. ...

View answer
Good reference about approximate methods for solving logic problems
10 votes

The motivation you state for dealing with undecidability applies to decidable but hard problems as well. If you have a problem that is NP-hard or PSPACE-hard, we will typically have to use some form ...

View answer
(N)DFA with same initial/accepting state(s)
10 votes

An important subclass of this family is a sub-class of 0-reversible languages. A language is 0-reversible if the reversal of the minimal DFA for the language is also deterministic. The reversing ...

View answer
Proofs found by computer
10 votes

This is more of a meta answer in that it is a list of lists. The papers of Doron Zeilberger. He is a mathematician and his computer is listed at the coauthor Shalosh B. Ekhad on all papers where the ...

View answer
Can Hoare logic be used when objects are created or deleted?
10 votes

There is a lot of work on Hoare Logic for object oriented programs, and for reasoning about memory allocation and deallocation. Some starting points: A Syntax-Directed Hoare Logic for Object-Oriented ...

View answer