scientific article; zbMATH DE number 2038719

zbMath1039.68048MaRDI QIDQ4449184

Rahul Jain, Pranab Sen

Publication date: 8 February 2004

Full work available at URL: http://link.springer.de/link/service/series/0558/bibs/2719/27190300.htm

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Quantum computation (81P68) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Relative Discrepancy Does not Separate Information and Communication Complexity ⋮ Lower Bounds on Information Complexity via Zero-Communication Protocols and Applications ⋮ Interactive Information Complexity ⋮ A characterization of average case communication complexity ⋮ Interactive Information Complexity ⋮ Superlinear lower bounds for multipass graph processing ⋮ A direct product theorem for two-party bounded-round public-coin communication complexity ⋮ Towards a reverse Newman's theorem in interactive information complexity ⋮ Direct sum fails for zero-error average communication ⋮ Compressing Interactive Communication Under Product Distributions ⋮ Lower bounds for predecessor searching in the cell probe model ⋮ Simulation theorems via pseudo-random properties ⋮ Unnamed Item ⋮ New Strong Direct Product Results in Communication Complexity ⋮ Communication Lower Bounds Via the Chromatic Number ⋮ Choosing, agreeing, and eliminating in communication complexity ⋮ Lifting Theorems for Equality

This page was built for publication: