Skip to main content

Week 2: On Understanding Our Research Identities

Matt and Josh did a great job walking me through Josh's research. I wanted to share the notes I wrote about Josh's research while reading one of his published articles and compare them to what I understand after the conversation.

Here's the notes, written the morning before the Week 2 meeting:

Notes on Joshua Brody et al, “Property Testing Lower Bounds Via Communication Complexity”, Computational Complexity 21:2012

“Communication complexity” seems very key to Josh’s research as a whole. I wonder if there is a way for me to understand or grasp it as a concept via complex systems theory or other definitions of complexity that I’m a bit familiar with, or to otherwise understand what qualifies communication as complex in computation/information theory. Does seem as on p. 312 that various formalizations of complexity as a concrete definable (mathematical) characteristic or property are in play in Josh’s work.

“property testing”: from Wikipedia (
“In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to decide if some mathematical object (such as a graph or a boolean function) has a "global" property, or is "far" from having this property, using only a small number of "local" queries to the object.
For example, the following promise problem admits an algorithm whose query complexity is independent of the instance size (for an arbitrary constant ε > 0):
"Given a graph G on n vertices, decide if G is bipartite, or G cannot be made bipartite even after removing an arbitrary subset of at most edges of G."
Property testing algorithms are important in the theory of probabilistically checkable proofs.”

What do I think I understand about property testing algorithms? Using small ‘local’ queries to determine a mathematical object is in fact “big”? Understanding what the "big" object is? Making the "big" object usable or tractable by just 'pinging' a few slices or selections of it? Is that a good translation?

“Communication complexity framework has been extensively studied”. This is an interesting moment in anybody’s scholarship—the identification of the space that the scholars are operating within that makes their work useful/original/important in relationship to the spaces or concepts that are well understood or thoroughly studied. “This approach turns out to be quite fruitful, both for proving new bounds and for giving simpler proofs of known bounds in property testing”. I should ask if there are other rivalrous approaches, or who has used the approach that Josh and his co-authors sketch here.

In terms of collaboration, how did this one come together? Is this because Josh proved Theorem 1.4 in his 2011 work?
Would be interested just in talking about how theorems in this kind of research iterate? Are there moments of sudden or unexpected intellectual disjunction? Big intuitive leaps? Or is the next task or job clearly iterable out of the last one accomplished?


So compare to what I learned through conversation with Josh and Matt.

1. The prospect of the conversation was somewhat terrifying! Though thank god I at least understand accurately what a Boolean variable is. Perhaps more soberingly, I do not have an entirely clear grasp of what a function is, which is roughly like saying in a humanities context that I don't know what words and grammar and books are exactly.

2. But I am now way, way clearer on what Josh researches, how he researches it, what the relationship between his research is and other work in his field, on the process of his collaboration with other researchers, on the goals and ambitions of his research. One of the things I walk away from after Friday is thinking that for all that I believe that non-face-to-face information mappings of the work of our colleagues might produce a good kind of "continuous partial attention" to each other, there's really no substitute for the opportunity to ask questions in a dialogue, especially the kind of dialogue where it's ok to ask a mix of simple (even simple-minded) questions and more sophisticated ones.