All reports by Author Trinh Huynh:

__
TR09-072
| 3rd September 2009
__

Paul Beame, Trinh Huynh#### Hardness Amplification in Proof Complexity

Revisions: 2
,
Comments: 2

__
TR08-082
| 11th September 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity and Threshold Circuit Size of AC^0

Revisions: 2

__
TR08-061
| 11th June 2008
__

Paul Beame, Trinh Huynh#### Multiparty Communication Complexity of AC^0

Revisions: 1

__
TR08-024
| 26th February 2008
__

Paul Beame, Trinh Huynh#### On the Value of Multiple Read/Write Streams for Approximating Frequency Moments

Revisions: 2

Paul Beame, Trinh Huynh

We present a generic method for converting any family of unsatisfiable CNF formulas that require large resolution rank into CNF formulas whose refutation requires large rank for proof systems that manipulate polynomials or polynomial threshold functions of degree at most $k$ (known as ${\rm Th}(k)$ proofs). Such systems include: Lovasz-Schrijver ... more >>>

Paul Beame, Trinh Huynh

We prove an n^{Omega(1)}/2^{O(k)} lower bound on the randomized k-party communication complexity of read-once depth 4 AC^0 functions in the number-on-forehead (NOF) model for O(log n) players. These are the first non-trivial lower bounds for general NOF multiparty communication complexity for any AC^0 function for omega(log log n) players. For ... more >>>

Paul Beame, Trinh Huynh

We prove n^Omega(1) lower bounds on the multiparty communication complexity of AC^0 functions in the number-on-forehead (NOF) model for up to Theta(log n) players. These are the first lower bounds for any AC^0 function for omega(loglog n) players. In particular we show that there are families of depth 3 read-once ... more >>>

Paul Beame, Trinh Huynh

Recently, an extension of the standard data stream model has been introduced in which an algorithm can create and manipulate multiple read/write streams in addition to its input data stream. Like the data stream model, the most important parameter for this model is the amount of internal memory used by ... more >>>