DIMACS
DIMACS REU 2019

General Information

me
Student: Shoshana Simons
Office: CoRE 444
School: Brown University
E-mail: shoshanasimons at brown dot edu
Project: Lower Bounds

Project Description

We are thinking about how we can translate questions about the resources a computational device needs to solve a problem into questions about the resources two people need to communicate about something, and vice versa. The study of the resources a computational device needs to solve a problem, when that computational device must be something called a circuit, is called circuit complexity. And the study of the resources two people need to communicate about something is called communication complexity. So a fancy way to say what we're doing is finding connections between circuit complexity and communication complexity. The project's called "Lower Bounds" because one of the major motivations for finding these connections is that having them would hopefully make determining lower bounds on the amount of resources a circuit needs to solve a problem more tractable.


Weekly Log

Week 1:

I met with my mentor, Robert, for the first time, and he introduced me to the history behind the problem he wants us to tackle. He gave me some papers to read, along with a textbook, that go deeper into the history, and I spent most of my week teetering between reading them and asking Robert questions about them. I'm someone who thinks the context of a problem is really important to understanding it and finding it interesting, so I appreciated Robert's willingness to focus on the build-up to our problem, not just the problem.

Reading these things gave me a lot to think about, not just about the history but also about the research process. The first thing I want to say is that I am really glad I had the textbook. If anyone who's starting out research happens to be reading this, I recommend asking your mentor for resources where you are a member of the target audience (like a textbook). Although there was definitely difficulty associated with both the papers and the textbook. I think one of the major sources of the difficulty is the fact that I don't know where to focus: I could spend days thinking about just one of the sentences in these things. When an author says something, I feel this urge to try connect it to other things that have been said, and other things I know, and that leads me down a rabbit hole of trying to connect dots for a while. So I think one of the things I want to work on this summer is figuring out the balance between reading and thinking that allows me to be most productive.

I feel grateful that I'm able to talk about these challenges, not just "the ideas", with my mentor. Starting out research is difficult, and I don't think it's just because the ideas themselves are inherently difficult. I think that the newness of this whole thing has been what's most difficult for me. My brain's had to take in a lot of new information in the past few days, and there's certainly a tradeoff between quantity and clarity when you're constrained by time. So the stuff I've learned hasn't really crystallized yet, and that means I'm not able to think and talk about things in the way I'm used to being able to think and talk about things. And THAT is difficult for me. Maybe I should learn to be more okay with the stuff in my brain being a little fuzzy for a time. A part of me feels like being okay with that is what I'm supposed to do, but another part of me feels like being okay with that is ingenuine to who I am. I'll think about this more and get back to you next week. I do think that the stuff is crystallizing more every day, and that feels good.

Week 2:

I am happy to report that stuff has crystallized a lot! From talking with Robert, I think I'm beginning to understand that research is a cycle of two phases: what I'll call the "the consumption phase" and "the creation phase." You're in the consumption phase when you're taking in other people's ideas and trying (usually, really friggin hard) to get them to crystallize. Once a sufficient amount of the ideas you've taken in have crystallized, you're ready to enter the creation phase. In the creation phase, you play around with what has crystallized to create new ideas and revel in the clarity you feel. When you get stuck, or find that you don't have enough inspiration to create, you go back to the consumption phase. That's the cycle.

One could say doing, well, really anything follows this two-phase cycle, but I think the consumption phase in research is a lot harder than it has been for me in the past. In classes at school for example, the consumption phase is well-defined: you know what you have to learn and when you are ready to enter the creation phase. It's right when the textbook chapter ends and you feel ready to try the problems out. But there's no such textbook in research. You have to create it yourself. In other words, you have to decide which ideas you should focus on getting to crystallize, and which ideas are less important to getting to your creation phase. But there's a large sea of information out there, and pruning through it can feel overwhelming, confusing, and frustrating.

But the difficulty that the consumption phase brings me in research seems to pay off in the creation phase. I feel like I have more creative power than I do after say, reading a textbook for a class, because for one, I've internalized so much more information, but I think what makes me feel most empowered is that I've taken a path through the history of ideas that no one ever has before. I got to experience the creation phase for the first time this week, and I got my first "result." I am now working on writing up my result, and I am enjoying that a lot. And although I am a little bit dreading going back to the consumption phase, the hope that it will eventually pay off generously in creativity will keep me going. I guess you could sum up the lesson I learned this week as "you gotta consume to create."

Week 3:

Writing up my result took a little longer than I anticipated; I actually didn't finish until the end of this week. I think a big reason it took me as long as it did to finish is because I wanted my result to feel well-motivated to someone like, say, me, but at the start of the summer. So I didn't just splat my result on the page: I built up to it, and that took time.

I'm happy with how my write-up turned out, although I will say that even with my slow build up, I don't think that it's something I could've flew through in an hour or two at the beginning of the summer. The ideas in my paper heavily build on one another, and it takes time to absorb the prerequisite ideas for some big idea if you want to understand that big idea through and through. You gotta let those prerequisite ideas incubuate for the big idea to hatch. We don't try to teach students all of, say, calculus in a day for a reason, and I think it'd be good for all of us in the research world to remember that we don't as we're writing papers and desgining talks. I mean after all, what's the big difference between the audience members of a paper or talk and the students in a class?

Week 4:

It's getting hard to describe what I'm doing without getting into the details of my research, so I'm going to give a very, very rough sketch of what I've been doing (caution: read my project description before proceeding!). The result I developed over the past few weeks was a new characterization, or way of thinking about, a certain kind of circuit. I'm now going to try to find another characterization of this kind of circuit because: 1. the more ways we have to think about something, the better, and 2. a lot of connections have been discovered between this kind of circuit and some cool ideas out there, and it'd be nice for the characterization I come up with to tap into some of those cool ideas.

This week, I'm reading about just one of these connections, and I'm thinking about how I can exploit it to get a new characterization. If that was much too vague to make any sort of sense, just know that I'm reading a lot right now and spending a lot of my time in the consumption phase. Although I will say that the consumption and production phases seem to be much shorter nowadays: I'll consume a little and then try stuff out pretty quickly. And then pretty quickly, what I'm trying out will fail or I'll get stuck and will go back to consuming.

Week 5:

At the end of last week, I walked Robert through a few directions I thought we could move in to get closer to a new characterization, and we decided to pursue one of these directions this week. I've made some progress in this direction this week, and in the process, I've learned about even more connections that exist between this kind of circuit and cool ideas out there.

I think one of the best points of this week for me was finding a paper that gave me what I needed to state precisely a property of circuits that I'd only been able to characterize intuitively before. I like thinking about the fact that this stuff that stirred up so much confusion in me only a few weeks ago is the same very stuff that's giving me more mental clarity than ever now. Math's funny like that. I feel like my research this summer has been a little like navigating through a hurricane. I know the eye's gotta be somewhere; I just have to find it.

I've also found this week that I'm able to read papers much quicker than I could at the beginning. I'm able to anticipate what the writers are going to say more quickly and feel more comfortable deciding what I need and don't to make progress. I feel like I may sound ridiculously positive on here, so let me just say that these past few weeks have absolutely been hard. At many points, I've felt like my progress is lulling, especially when I've thought I've reached an eye only to find that I'm still amidst the stormiest part of the storm. However, something I try to do when I feel that way is put where I'm at in perspective. I try to remind myself of where I was a mere 5 weeks ago, back when I'd never even heard of the kind of circuit I'm researching now. And when I do that, it's much harder to feel down about where I'm at.

Additional Information


Special Thanks

This project was funded by the National Science Foundation, grant number CCF-1852215.