Algorithms and Complexity

How fast is that? Is it even possible

To a large extent computer science is about inventing algorithms then exploring the properties of them, including proving mathematically that they work. However, just working is not enough. An important area of theoretical computer science does not just invent new algorithms but also explores how efficient they are. What are the bounds on what algorithms can even do at all.

While it may be theoretically interesting, it is not much use inventing an algorithm that will take longer then the age of the universe to give an answer, so understanding the maths of how efficient algorithms are – how complex they are really matters. And it leads to one of the most important but unsolved problems in all of Computer Science.

Learn below about some theoretically important algorithms, but also stories, but also about mathematical results about algorithms in general.

Playing Tantrix: P=NP?

You can find computer science everywhere – even in popular Solitaire games and puzzles. Most people have played games like Tetris, Battleships, Mastermind, Tantrix and Minesweeper at some point. In fact, all these games have a link to one of the deepest, fundamental problems remaining in Computer Science. They are all linked to a famous equation that is to do with the ultimate limitations of computers. (Read on)

Shafi Goldwasser and the Zero Knowledge Proof

A vortex of books

Shafi Goldwasser, one of the greatest living computer scientists, won the Turing Award in 2012 (equivalent to a Nobel Prize). Her work helped turn cryptography from a dark art into a science. If you’ve ever used a credit card through a web browser, for example, her work was helping you stay secure. Her greatest achievement, with Silvio Micali and Charles Rackoff, is the “Zero knowledge proof”…. (read on)

Barbara Liskov: Byzantine birthdays

The ACM Turing Award, which Barbara Liskov won, is the computing equivalent of a Nobel Prize. She was awarded it for more than 40 years’ work. Her early work on programming languages has been used in every significant new language that has been invented since. More recently she has moved on to problems about ‘distributed systems’: computer systems involving lots of separate computers that have to work together. That’s where the arguing comes in. (read on)

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This blog is funded by EPSRC on grant EP/W033615/1.