Joshua Brody
  • Member for 11 years, 4 months
  • Last seen more than 2 years ago
Advice on good research practices
30 votes

I'll start with some advice my advisor Amit Chakrabarti gave that I found quite useful: (1) Keep a research journal and write in it every day. Its easy to forget about the details of what I was ...

View answer
Communication lower bounds for partial boolean functions
Accepted answer
11 votes

(1) The way I like to think about partial functions is by defining a total function with three outputs e.g, $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1, *\}$. The $*$ values are where your ...

View answer
Research problems in communication complexity
10 votes

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity. It's hard to say what areas a new communication complexity researcher ...

View answer
How does Theoretical Computer Science relate to security?
10 votes

There's a lot of real-world motivation for the study of streaming algorithms that comes from network intrusion detection. The paper below uses streaming algorithms for empirical entropy to detect ...

View answer
Nondeterministic communication complexity of set disjointness?
Accepted answer
9 votes

$N^1(DISJ_n) \geq n$. The fooling set technique actually provides lower bounds on the cover number. $C^1(f)$ is the minimum number of monochromatic rectangles needed to cover the $1$-inputs of $f$. ...

View answer
On connecting combinatorial rectangles
Accepted answer
4 votes

It's not possible. Consider the following 3x3 boolean matrix: 1 1 0 1 0 1 0 1 1 For every pair of rows {r,r'} , there exists a column c such that {r,r'} X {c} is a combinatorial rectangle. For ...

View answer
"Send Once"-One way Multiparty Communication Complexity
3 votes

There are several flavors of communication complexity. It sounds like your "send once" model is uses one-way communication and private messages. For concreteness, I give short synopses of some ...

View answer