julianrdcosta

Julian R D’Costa

julianheadshotcrop

Welcome to my website! Think of this as a library under construction – there’s a distant noise of hammering, the walls aren’t painted yet and the sentences sometimes trail off, but there’s a few quiet nooks you can sit in and enjoy the odd blogpost.

Probably the second-funniest way to describe what I’m up to these days is to say I work at an AGI lab – just one you’ve never heard of.

I used to be a DPhil student in computer science at Oxford University, where I worked on algorithmic verification with James Worrell and Joel Ouaknine. I grew up in Goa, India, and studied math at IISc Bangalore. If something on this site interests you, I’d love to chat – I’m julianrdcosta on gmail and twitter.

Work With Me

Although I dabble in many things, I’m particularly interested in working in:

I also have a LinkedIn and a CV.

If you are an unusually enlightened parent, child, or human, you may enjoy hiring me as an aristocratic tutor.

Research Papers

My DPhil research was about algorithmic questions that arise when you ask the halting problem for computational systems that are linear – in the sense that matrix multiplication is a linear map.

For example you could ask: Can we decide whether a given loop x = x_0; while (c^Tx = 0) {do x = Mx} terminates?

Going nonlinear quickly means that halting and pretty much any other question you can ask about the system is undecidable. As for linear systems, you can diagonalize matrices and write everything in terms of sums of powers of eigenvalues, so (if the matrices commute or there’s just one matrix involved) things should be easy, right? Wrong! Terry Tao calls it a “mathematical embarrassment” that we still don’t know how to understand linear systems. (But there’s been some recent progress)

Here’s my PhD thesis: Reachability and Escape Problems in Linear Dynamical Systems

New expository note: Transforming Matrices and Semialgebraic Sets into a Jordan basis: Explains how to transform a matrix into a Jordan basis, and how such a basis change affects the description size of the associated semialgebraic sets.

I’m currently thinking about discrete linear dynamical systems with perturbations. For example, see this blog post about the 2D Rotation Rounding Problem.

The Pseudo-Reachability Problem for Diagonalisable Linear Dynamical Systems

Bounding the Escape Time of a Linear Dynamical System over a Compact Semialgebraic Set.

On the Complexity of the Escape Problem for Linear Dynamical Systems over Compact Semialgebraic Sets

The Pseudo-Skolem Problem is Decidable

How Fast Can You Escape a Compact Polytope? (STACS 2020)

Erratum: Appendix 2: Proof of Lemma 5 of How Fast.. deals with converting a rational matrix A to its Jordan form J = QAQ^{-1} where Q^{-1} is the matrix of generalized eigenvectors. It contains the sentence “The entries q ij of Q can be computed in 3d^3 operations from the entries of Q^{−1}”. Unfortunately this is not valid, because the entries of Q^{-1} are  algebraic numbers, which may not be representable explicitly, so it is not clear what it would mean to use Gaussian elimination (which has cubic complexity) on them. It is, however, true that the entries of Q, J and Q^{-1} can be computed in polynomial time from A, but this involves careful maneuvering to avoid going through the splitting field of all the eigenvalues of A, and Q is not computed from Q^{-1}. The details are in Transforming Matrices and Semialgebraic Sets into a Jordan basis This means that the explicit constants in Theorem 3 are incorrect. I am hoping to publish a followup which improves Theorem 3 to a single exponential bound.

Interests

Right now I’m interested in AI, especially questions in theory and alignment, neuroscience, synthetic and molecular biology, longevity research, economics – how is wealth created?, education and parenting, and design.

Idiolect

Words and phrases that have made it into my personal vocabulary and I’d like to see get more popular

Today’s lucky ten thousand – a short handle for the idea that someone not knowing something isn’t an occasion for surprise or scorn, but an opportunity to watch someone discover something for the first time

Finite problems – The human mind tends to expand or contract all problems to roughly the size that will occupy an entire brain. As a relatively privileged person, I use the phrase finite problems to remind myself that most of the problems I face are not likely to leave me homeless or starving, but can – worst case scenario – be dodged by disappearing, changing my name, and returning as Julian Prime. This thought comforts me. It is unlikely to work for someone else, but I write it up because it might.

Nerdsnipe – It’s just really fun to use as a verb

Questions

Stuff I’d really like to know the answer to:

  • What are the base rates for Chronic Fatigue Syndrome, developing CFS-like symptoms after respiratory infection, and developing CFS-like symptoms after Covid?
  • Given the insane corruption and decadence of 16-century Popes, how did the Papacy survive for another 5 centuries with its reputation sufficiently intact to be considered a moral authority? Essentially, I want to know, what are the reasons behind the Roman Catholic Church’s longevity? I’m also very interested in good solutions to the succession problem.
  • What parts of the modern world /economy actually produce wealth (in the Paul Graham sense, also excluding positional goods) , which parts are bullshit (in the bullshit jobs sense) and are there any things which are neither?

Requests/Gifts

(if for some reason you feel inclined)

I would like to read the following books, which are pretty hard to get hold of:

  • The Marlow books by Antonia Forest (managed to procure print copy of Autumn Term)
  • All the Fishes Come Home to Roost, by Rachel Manija Brown (managed to find ebook)
  • Pogo by Walt Kelly (collections of the comic strips)  (found in New York)
  • Asimov Laughs Again