Post List

All posts; Tags Include "Computational Theory"

(Modify Search »)

  • December 18, 2016
  • 06:45 AM
  • 850 views

Fusion and sex in protocells & the start of evolution

by Artem Kaznatcheev in Evolutionary Games Group

In 1864, five years after reading Darwin’s On the Origin of Species, Pyotr Kropotkin — the anarchist prince of mutual aid — was leading a geographic survey expedition aboard a dog-sleigh — a distinctly Siberian variant of the HMS Beagle. In the harsh Manchurian climate, Kropotkin did not see competition ‘red in tooth and claw’, […]... Read more »

Sinai, S, Olejarz, J, Neagu, IA, & Nowak, MA. (2016) Primordial Sex Facilitates the Emergence of Evolution. arXiv. arXiv: 1612.00825v1

  • April 8, 2016
  • 11:29 AM
  • 1,087 views

The Real Cost of Sequencing

by Daniel Koboldt in Massgenomics

The real cost of sequencing is as hard to pin down as a sumo wrestler. Working in a large-scale sequencing laboratory offers an interesting perspective on the duality of the so-called “cost per genome.” On one hand, we see certain equipment manufacturers and many people in the media tossing around claims that sequencing a genome […]... Read more »

Muir P, Li S, Lou S, Wang D, Spakowicz DJ, Salichos L, Zhang J, Weinstock GM, Isaacs F, Rozowsky J.... (2016) The real cost of sequencing: scaling computation to keep pace with data generation. Genome biology, 17(1), 53. PMID: 27009100  

  • May 8, 2015
  • 10:30 AM
  • 1,172 views

do memristor chips remember electric sheep?

by Greg Fish in weird things

Humans beware. Our would-be cybernetic overlords made a leap towards hyper-intelligence in the last few months as artificial neural networks can now be trained on specialized chips which use memristors, an electrical component that can remember the flow of electricity through it to help manage the amount of current required in a circuit. Using these specialized chips, robots, supercomputers, and sensors could solve complex real world problems faster, easier, and with far less energy. [...] ...... Read more »

  • February 17, 2015
  • 08:05 AM
  • 1,681 views

I'll Beam Right Over

by Mark E. Lasbury in The 'Scope

Star Trek’s 50th anniversary is next year. Wouldn’t transporting a person to the ISS be a great way to celebrate? Well, there are a couple of problems to overcome, but we’re on our way. We have recently learned how to transport information and light from one place to another, without it ever existing anywhere in between! And this will help us make quantum computers that will be able to transport all the information contained in every atom of your body.... Read more »

Ma, X., Herbst, T., Scheidl, T., Wang, D., Kropatschek, S., Naylor, W., Wittmann, B., Mech, A., Kofler, J., Anisimova, E.... (2012) Quantum teleportation over 143 kilometres using active feed-forward. Nature, 489(7415), 269-273. DOI: 10.1038/nature11472  

Yokoyama, S., Ukai, R., Armstrong, S., Sornphiphatphong, C., Kaji, T., Suzuki, S., Yoshikawa, J., Yonezawa, H., Menicucci, N., & Furusawa, A. (2013) Ultra-large-scale continuous-variable cluster states multiplexed in the time domain. Nature Photonics, 7(12), 982-986. DOI: 10.1038/nphoton.2013.287  

  • January 7, 2015
  • 12:45 AM
  • 1,048 views

Cataloging a year of blogging: cancer and biology

by Artem Kaznatcheev in Evolutionary Games Group

Welcome to 111101111. Another year has come to an end, and it is time to embrace tradition and reflect on the past twelve months. In fact, I will try to do one better and start a new tradition: cataloging a year of blogging. Last year, I split up the 83 content heavy posts of 2013 […]... Read more »

Kaznatcheev, A., Scott, J.G., & Basanta, D. (2014) Edge effects in game theoretic dynamics of spatially structured tumours. arXiv. arXiv: 1307.6914v2

  • December 7, 2014
  • 04:23 AM
  • 1,316 views

Building the Best Computer

by Viputheshwar Sitaraman in Draw Science

The American spy/intelligence agency, IARPA, is working to address the shortcomings of existing supercomputers through its program, C3. [Infographic]... Read more »

Holmes, D., Ripple, A., & Manheimer, M. (2013) Energy-Efficient Superconducting Computing—Power Budgets and Requirements. IEEE Transactions on Applied Superconductivity, 23(3), 1701610-1701610. DOI: 10.1109/TASC.2013.2244634  

  • December 3, 2014
  • 09:00 AM
  • 1,375 views

How Slime Molds Our World

by Mark Lasbury in As Many Exceptions As Rules

Fungus-like protists have amazing tales to tell. One phylum has been shown to ranch bacteria and hire cowhands to guard them. One phylum has slime mold that can find its way through a maze and is used to model mathematics for video games. Finally, one phylum is responsible for the glut of Irish priests and policeman in late 1800’s America.... Read more »

Goss, E., Tabima, J., Cooke, D., Restrepo, S., Fry, W., Forbes, G., Fieland, V., Cardenas, M., & Grunwald, N. (2014) The Irish potato famine pathogen Phytophthora infestans originated in central Mexico rather than the Andes. Proceedings of the National Academy of Sciences, 111(24), 8791-8796. DOI: 10.1073/pnas.1401884111  

Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D., Fricker, M., Yumiki, K., Kobayashi, R., & Nakagaki, T. (2010) Rules for Biologically Inspired Adaptive Network Design. Science, 327(5964), 439-442. DOI: 10.1126/science.1177894  

Toshiyuki Nakagaki, Hiroyasu Yamada . (2000) Intelligence: Maze-solving by an amoeboid organism. Nature, 407(470). info:/

Brock, D., Douglas, T., Queller, D., & Strassmann, J. (2011) Primitive agriculture in a social amoeba. Nature, 469(7330), 393-396. DOI: 10.1038/nature09668  

  • September 12, 2014
  • 12:00 AM
  • 1,305 views

Transcendental idealism and Post’s variant of the Church-Turing thesis

by Artem Kaznatcheev in Evolutionary Games Group

One of the exciting things in reading philosophy, its history in particular, is experiencing the tension between different schools of thought. This excitement turns to beauty if a clear synthesis emerges to reconcile the conflicting ideas. In the middle to late 18th century, as the Age of Enlightenment was giving way to the Romantic era, […]... Read more »

Post, E.L. (1936) Finite combinatory processes -- formulation 1. Journal of Symbolic Logic, 1(3), 103-105. info:/

  • September 2, 2014
  • 12:15 AM
  • 1,393 views

Falsifiability and Gandy’s variant of the Church-Turing thesis

by Artem Kaznatcheev in Evolutionary Games Group

In 1936, two years after Karl Popper published the first German version of The Logic of Scientific Discovery and introduced falsifiability; Alonzo Church, Alan Turing, and Emil Post each published independent papers on the Entscheidungsproblem and introducing the lambda calculus, Turing machines, and Post-Turing machines as mathematical models of computation. The years after saw many […]... Read more »

Gandy, R. (1980) Church's thesis and principles for mechanisms. Studies in Logic and the Foundations of Mathematics, 123-148. DOI: 10.1016/S0049-237X(08)71257-6  

  • March 26, 2014
  • 12:45 AM
  • 1,565 views

Algorithmic Darwinism

by Artem Kaznatcheev in Evolutionary Games Group

The workshop on computational theories of evolution started off on Monday, March 17th with Leslie Valiant — one of the organizers — introducing his model of evolvability (Valiant, 2009). This original name was meant to capture what type of complexity can be achieved through evolution. Unfortunately — especially at this workshop — evolvability already had […]... Read more »

Feldman, V. (2008) Evolvability from learning algorithms. Proceedings of the 40th annual ACM symposium on Theory of Computing, 619-628. DOI: 10.1145/1374376.1374465  

  • March 16, 2014
  • 10:00 PM
  • 1,131 views

Computational theories of evolution

by Artem Kaznatcheev in Evolutionary Games Group

If you look at your typical computer science department’s faculty list, you will notice the theorists are a minority. Sometimes they are further subdivided by being culled off into mathematics departments. As such, any institute that unites and strengthens theorists is a good development. That was my first reason for excitement two years ago when […]... Read more »

Angelino, E., & Kanade, V. (2014) Attribute-efficient evolvability of linear functions. Proceedings of the 5th conference on Innovations in Theoretical Computer Science, 287-300. DOI: 10.1145/2554797.2554824  

  • February 15, 2014
  • 12:45 AM
  • 1,686 views

Evolution is a special kind of (machine) learning

by Artem Kaznatcheev in Evolutionary Games Group

Theoretical computer science has a long history of peering through the algorithmic lens at the brain, mind, and learning. In fact, I would argue that the field was born from the epistemological questions of what can our minds learn of mathematical truth through formal proofs. The perspective became more scientific with McCullock & Pitts’ (1943) […]... Read more »

Valiant, L.G. (2009) Evolvability. Journal of the ACM, 56(1), 3. DOI: 10.1145/1462153.1462156  

  • December 17, 2013
  • 12:15 AM
  • 1,552 views

Lower bounds by negative adversary method

by Artem Kaznatcheev in Evolutionary Games Group

Are some questions harder than others? Last week I quantified hardness of answering a question with a quantum computer as the quantum query complexity. I promised that this model would allow us to develop techniques for proving lower bounds. In fact, in this model there are two popular tools: the polynomial method, and the (negative) […]... Read more »

Peter Hoyer, Troy Lee, & Robert Spalek. (2007) Negative weights make adversaries stronger. STOC. arXiv: quant-ph/0611054v2

  • December 10, 2013
  • 12:45 AM
  • 1,518 views

Quantum query complexity

by Artem Kaznatcheev in Evolutionary Games Group

You probably noticed a few things about TheEGG: a recent decrease in blog post frequency and an overall focus on the algorithmic lens — especially its view of biology. You might also be surprised by the lack of discussion of quantum information processing: the most successful on-going application of the algorithmic lens. I actually first […]... Read more »

Simon, D.R. (1997) On the power of quantum computation. SIAM Journal on Computing, 1474. DOI: 10.1137/S0097539796298637  

  • October 14, 2013
  • 12:45 AM
  • 1,533 views

Mathematics in finance and hiding lies in complexity

by Artem Kaznatcheev in Evolutionary Games Group

Mathematics has a deep and rich history, extending well beyond the 16th century start of the scientific revolution. Much like literature, mathematics has a timeless quality; although its trends wax and wane, no part of it becomes out-dated or wrong. What Diophantus of Alexandria wrote on solving algebraic equations in the 3rd century was still […]... Read more »

  • October 10, 2013
  • 05:30 AM
  • 1,231 views

Computational complexity of evolutionary stable strategies

by Artem Kaznatcheev in Evolutionary Games Group

Yesterday, I shared a video of John Maynard Smith introducing evolutionary game theory (EGT) to the London Mathematical Society. I suggested that at its foundation, EGT was just like classical game theory, and based on equilibrium analysis — the evolutionary stable strategy (Maynard Smith & Price, 1973). Given a utility function that gives the expected […]... Read more »

Conitzer, V. (2013) The exact computational complexity of evolutionarily stable strategies. The 9th Conference on Web and Internet Economics (WINE). info:/

  • October 1, 2013
  • 11:00 PM
  • 961 views

Limits on efficient minimization and the helpfulness of teachers.

by Artem Kaznatcheev in Evolutionary Games Group

Two weeks ago, I lectured on how we can minimize and learn deterministic finite state automata. Although it might not be obvious, these lectures are actually pretty closely related since minimization and learning often go hand-in-hand. During both lectures I hinted that the results won’t hold for non-deterministic finite state automata (NFA), and challenged the […]... Read more »

Angluin, D., & Kharitonov, M. (1995) When Won't Membership Queries Help?. Journal of Computer and System Sciences, 50(2), 336-355. DOI: 10.1006/jcss.1995.1026  

  • October 1, 2013
  • 12:30 AM
  • 1,403 views

Bounded rationality: systematic mistakes and conflicting agents of mind

by Artem Kaznatcheev in Evolutionary Games Group

Before her mother convinced her to be a doctor, my mother was a ballerina. As a result, whenever I tried to blame some external factor for my failures, I was met with my mother’s favorite aphorism: a bad dancer’s shoes are always too tight. “Ahh, another idiosyncratic story about the human side of research,” you […]... Read more »

  • September 24, 2013
  • 10:30 PM
  • 1,326 views

How teachers help us learn deterministic finite automata

by Artem Kaznatcheev in Evolutionary Games Group

Many graduate students, and even professors, have a strong aversion to teaching. This tends to produce awful, one-sided classes that students attend just to transcribe the instructor’s lecture notes. The trend is so bad that in some cases instructors take pride in their bad teaching, and at some institutions — or so I hear around […]... Read more »

  • September 9, 2013
  • 04:15 AM
  • 1,426 views

What can theoretical computer science offer biology?

by Artem Kaznatcheev in Evolutionary Games Group

If there is anything definitive that can be said about biology then it is that biology is messy and complicated. The stereotypical image of a biology major is in the library memorizing volumes of loosely (at best) related facts only to have them overturned in the next semester. Concepts are related only vaguely, to the […]... Read more »

join us!

Do you write about peer-reviewed research in your blog? Use ResearchBlogging.org to make it easy for your readers — and others from around the world — to find your serious posts about academic research.

If you don't have a blog, you can still use our site to learn about fascinating developments in cutting-edge research from around the world.

Register Now

Research Blogging is powered by SRI Technology.

To learn more, visit http://selfregulationinstitute.org/.