index.bib
@comment{{This file has been generated by bib2bib 1.96}}
@comment{{Command line: bib2bib -c '$key="SaksS2002" or $key="LeeS2009" or $key="KushilevitzNisan" or $key="JainKZ2010" or $key="ChattopadhyayP2010" or $key="ChakrabartiCM2010" or $key="PonzioRV2001" or $key="Indyk2007" or $key="BravermanR2011-arXiv" or $key="Sherstov2008survey" or $key="jayramKS2008" or $key="PatrascuD2006" or $key="BarakBCR2010" or $key="BeameJR2007" or $key="GavinskyS2010" or $key="Yannakakis1991" or $key="BravermanR2011" or $key="ChakrabartiK2011" or $key="Woodruff2004" or $key="AndoniJP2010" or $key="BlumrosenN2007" or $key="Sherstov-gapHamming" or $key="ChakrabartiR2011" or $key="SenV2008" or $key="Lee2010" or $key="BarYossefJKS2004" or $key="Sherstov-disjmulti" or $key="AroraBarak" or $key="JayramKR2009" or $key="LeeZ2010" or $key="Sherstov2010" or $key="ChakrabartiCM2008" or $key="AlonMS1999" or $key="PatrascuD2004" or $key="BabaiFS1986" or $key="JayramKS2003" or $key="Patrascu2011" or $key="Sen2003" or $key="DammJS1998" or $key="JainK2010" or 1=2' ./jrnl-names-abb.bib ./prahladhbib.bib ./crossref.bib}}
@article{AlonMS1999,
author = {Noga Alon and Yossi Matias and Mario Szegedy},
title = {The Space Complexity of Approximating the Frequency
Moments},
journal = {J. Computer and System Sciences},
volume = 58,
number = 1,
year = 1999,
pages = {137--147},
doi = {10.1006/jcss.1997.1545},
note = {(Preliminary Version in {\em 28th STOC}, 1996)}
}
@inproceedings{AndoniJP2010,
author = {Alexandr Andoni and T. S. Jayram and Mihai Patrascu},
title = {Lower Bounds for Edit Distance and Product Metrics
via {P}oincar{\'e}-Type Inequalities},
pages = {184-192},
url = {http://www.siam.org/proceedings/soda/2010/SODA10_017_andonia.pdf},
crossref = {soda2010}
}
@book{AroraBarak,
author = {Sanjeev Arora and Boaz Barak},
title = {Computational Complexity: A Modern Approach},
publisher = {Cambridge University Press},
year = 2009
}
@inproceedings{BabaiFS1986,
author = {L{\'a}szl{\'o} Babai and Peter Frankl and Janos
Simon},
title = {Complexity classes in communication complexity
theory (preliminary version)},
pages = {337--347},
crossref = {focs1986},
doi = {10.1109/SFCS.1986.15}
}
@article{BarYossefJKS2004,
author = {Ziv {Bar-Yossef} and T. S. Jayram and Ravi Kumar and
D. Sivakumar},
title = {An information statistics approach to data stream
and communication complexity},
journal = {J. Computer and System Sciences},
volume = 68,
number = 4,
year = 2004,
pages = {702--732},
month = jun,
doi = {10.1016/j.jcss.2003.11.006},
note = {(Preliminary Version in {\em 43rd FOCS}, 2002)}
}
@inproceedings{BarakBCR2010,
author = {Boaz Barak and Mark Braverman and Xi Chen and Anup
Rao},
title = {How to compress interactive communication},
pages = {67--76},
doi = {10.1145/1806689.1806701},
crossref = {stoc2010}
}
@inproceedings{BeameJR2007,
author = {Paul Beame and T. S. Jayram and Atri Rudra},
title = {Lower bounds for randomized read/write stream
algorithms},
pages = {689--698},
doi = {10.1145/1250790.1250891},
crossref = {stoc2007}
}
@incollection{BlumrosenN2007,
title = {Combinatorial Auctions},
author = {Liad Blumrosen and Noam Nisan},
chapter = 11,
booktitle = {Algorithmic Game Theory},
editor = {Noam Nisan and Tim Roughgarden and \'{E}va Tardos
and Vijay V. Vazirani},
publisher = {Cambridge University Press},
year = 2007,
pages = {267--300},
url = {http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf}
}
@inproceedings{BravermanR2011,
author = {Mark Braverman and Anup Rao},
title = {Towards coding for maximum errors in interactive
communication},
pages = {159--166},
doi = {10.1145/1993636.1993659},
crossref = {stoc2011},
eccc = {TR10-166},
ecccurlid = {2010/166}
}
@misc{BravermanR2011-arXiv,
author = {Mark Braverman and Anup Rao},
title = {Information Equals Amortized Communication},
year = 2011,
eprint = {1106.3595}
}
@inproceedings{ChakrabartiCM2008,
author = {Amit Chakrabarti and Graham Cormode and Andrew
McGregor},
title = {Robust lower bounds for communication and stream
computation},
pages = {641--650},
doi = {10.1145/1374376.1374470},
crossref = {stoc2008},
eccc = {TR11-062},
ecccurlid = {2011/062}
}
@article{ChakrabartiCM2010,
author = {Amit Chakrabarti and Graham Cormode and Andrew
McGregor},
title = {A near-optimal algorithm for estimating the entropy
of a stream},
journal = {ACM Transactions on Algorithms},
volume = 6,
number = 3,
year = 2010,
doi = {10.1145/1798596.1798604},
note = {(Preliminary version in {\em 18th SODA}, 2007)}
}
@inproceedings{ChakrabartiK2011,
author = {Amit Chakrabarti and Ranganath Kondapally},
title = {Everywhere-Tight Information Cost Tradeoffs for
Augmented Index},
pages = {448--459},
doi = {10.1007/978-3-642-22935-0_38},
crossref = {random11}
}
@inproceedings{ChakrabartiR2011,
author = {Amit Chakrabarti and Oded Regev},
title = {An optimal lower bound on the communication
complexity of gap-{H}amming-distance},
pages = {51--60},
doi = {10.1145/1993636.1993644},
crossref = {stoc2011},
eprint = {1009.3460},
eccc = {TR10-140},
ecccurlid = {2010/140}
}
@article{ChattopadhyayP2010,
author = {Arkadev Chattopadhyay and Toniann Pitassi},
title = {The story of set disjointness},
journal = {{SIGACT} News},
volume = 41,
number = 3,
year = 2010,
pages = {59--85},
doi = {10.1145/1855118.1855133}
}
@article{DammJS1998,
author = {Carsten Damm and Stasys Jukna and Jiri Sgall},
title = {Some Bounds on Multiparty Communication Complexity
of Pointer Jumping},
journal = {Comput. Complexity},
volume = 7,
number = 2,
year = 1998,
pages = {109--127},
doi = {10.1007/PL00001595},
note = {(Preliminary Version in {\em 13th STACS}, 1996)}
}
@article{GavinskyS2010,
author = {Dmitry Gavinsky and Alexander A. Sherstov},
title = {A Separation of {NP} and {coNP} in Multiparty
Communication Complexity},
journal = {Theory of Computing},
volume = 6,
number = 1,
year = 2010,
pages = {227--245},
doi = {10.4086/toc.2010.v006a010}
}
@misc{Indyk2007,
author = {Piotr Indyk},
title = {6.895: {S}ketching, {S}treaming and {S}ub-linear
Space Algorithms},
note = {A course offered at {MIT} ({F}all 2007)},
year = 2007,
url = {http://stellar.mit.edu/S/course/6/fa07/6.895/index.html}
}
@inproceedings{JainK2010,
author = {Rahul Jain and Hartmut Klauck},
title = {The Partition Bound for Classical Communication
Complexity and Query Complexity},
pages = {247--258},
doi = {10.1109/CCC.2010.31},
crossref = {ccc2010},
eprint = {0910.4266}
}
@inproceedings{JainKZ2010,
author = {Rahul Jain and Hartmut Klauck and Shengyu Zhang},
title = {Depth-Independent Lower Bounds on the Communication
Complexity of Read-Once Boolean Formulas},
pages = {54--59},
doi = {10.1007/978-3-642-14031-0_8},
crossref = {cocoon2010},
eprint = {0908.4453}
}
@inproceedings{JayramKR2009,
author = {T. S. Jayram and Swastik Kopparty and Prasad
Raghavendra},
title = {On the Communication Complexity of Read-Once
${AC}^0$ Formulae},
pages = {329--340},
doi = {10.1109/CCC.2009.39},
crossref = {ccc2009}
}
@inproceedings{JayramKS2003,
author = {T. S. Jayram and Ravi Kumar and D. Sivakumar},
title = {Two applications of information complexity},
pages = {673--682},
doi = {10.1145/780542.780640},
crossref = {stoc2003}
}
@article{JayramKS2008,
author = {T. S. Jayram and Ravi Kumar and D. Sivakumar},
title = {The One-Way Communication Complexity of {H}amming
Distance},
journal = {Theory of Computing},
volume = 4,
number = 1,
year = 2008,
pages = {129--135},
doi = {10.4086/toc.2008.v004a006}
}
@book{KushilevitzNisan,
title = {Communication Complexity},
author = {Eyal Kushilevitz and Noam Nisan},
year = 1997,
publisher = {Cambridge University Press},
doi = {10.2277/052102983X}
}
@misc{Lee2010,
author = {Troy Lee},
title = {16:198:671 {C}ommunication {C}omplexity},
note = {A course offered at {R}utgers {U}niversity ({S}pring
2010)},
year = 2010,
url = {http://www.research.rutgers.edu/~troyjlee/cc.html}
}
@article{LeeS2009,
author = {Troy Lee and Adi Shraibman},
title = {Lower Bounds in Communication Complexity},
journal = {Foundations and Trends in Theoretical Computer
Science},
volume = 3,
number = 4,
year = 2009,
pages = {263--398},
doi = {10.1561/0400000040}
}
@inproceedings{LeeZ2010,
author = {Troy Lee and Shengyu Zhang},
title = {Composition Theorems in Communication Complexity},
pages = {475--489},
doi = {10.1007/978-3-642-14165-2_41},
crossref = {icalp2010a},
eprint = {1003.1443}
}
@article{Patrascu2011,
author = {Mihai Patrascu},
title = {Unifying the Landscape of Cell-Probe Lower Bounds},
journal = {SIAM J. Computing},
volume = 40,
number = 3,
year = 2011,
pages = {827--847},
doi = {10.1137/09075336X},
eprint = {1010.3783},
note = {(Preliminary version in {\em 49th FOCS}, 2008)}
}
@inproceedings{PatrascuD2004,
author = {Mihai Patrascu and Erik D. Demaine},
title = {Tight bounds for the partial-sums problem},
pages = {20--29},
doi = {10.1145/982792.982796},
crossref = {soda2004}
}
@article{PatrascuD2006,
author = {Mihai Patrascu and Erik D. Demaine},
title = {Logarithmic Lower Bounds in the Cell-Probe Model},
journal = {SIAM J. Computing},
volume = 35,
number = 4,
year = 2006,
pages = {932--963},
doi = {10.1137/S0097539705447256},
note = {(Preliminary version in {\em 36th STOC}, 2004 and
{\em 15th SODA}, 2004)},
eprint = {cs/0502041}
}
@article{PonzioRV2001,
author = {Stephen Ponzio and Jaikumar Radhakrishnan and
Srinivasan Venkatesh},
title = {The Communication Complexity of Pointer Chasing},
journal = {J. Computer and System Sciences},
volume = 62,
number = 2,
year = 2001,
pages = {323--355},
doi = {10.1006/jcss.2000.1731},
note = {(Preliminary Version in {\em 31st STOC}, 1999)}
}
@inproceedings{SaksS2002,
author = {Michael E. Saks and Xiaodong Sun},
title = {Space lower bounds for distance approximation in the
data stream model},
crossref = {stoc2002},
pages = {360--369},
doi = {10.1145/509907.509963}
}
@inproceedings{Sen2003,
author = {Pranab Sen},
title = {Lower bounds for predecessor searching in the cell
probe model},
pages = {73--83},
doi = {10.1109/CCC.2003.1214411},
crossref = {ccc2003}
}
@article{SenV2008,
author = {Pranab Sen and Srinivasan Venkatesh},
title = {Lower bounds for predecessor searching in the cell
probe model},
journal = {J. Computer and System Sciences},
volume = 74,
number = 3,
year = 2008,
pages = {364--385},
doi = {10.1016/j.jcss.2007.06.016},
note = {(Preliminary version in in {\em 28th ICALP}, 2001
and {\em 18th IEEE Conference on Computational
Complexity}, 2003)},
eprint = {cs/0309033}
}
@techreport{Sherstov-gapHamming,
author = {Alexander A. Sherstov},
title = {The Communication Complexity of Gap {H}amming
Distance},
institution = {Electronic Colloquium on Computational Complexity
(ECCC)},
number = {TR11-063},
year = 2011,
eccc = {TR11-063},
ecccurlid = {2011/063}
}
@article{Sherstov2008survey,
author = {Alexander A. Sherstov},
title = {Communication lower bounds using dual polynomials},
journal = {Bulletin of the EATCS},
volume = 95,
pages = {59--93},
year = 2008,
url = {http://eatcs.org/images/bulletin/beatcs95.pdf},
eprint = {0805.2135}
}
@article{Sherstov2010,
author = {Alexander A. Sherstov},
title = {Communication Complexity Under Product and
Nonproduct Distributions},
journal = {Comput. Complexity},
volume = 19,
number = 1,
year = 2010,
pages = {135--150},
doi = {10.1007/s00037-009-0285-1},
eccc = {TR07-072},
ecccurlid = {2007/072},
note = {(Preliminary version in {\em 23rd IEEE Conference on
Comput. Complexity}, 2008)}
}
@techreport{Sherstov-disjmulti,
author = {Alexander A. Sherstov},
title = {The Multiparty Communication Complexity of Set Disjointness},
institution = {Electronic Colloquium on Computational Complexity
(ECCC)},
number = {TR11-145},
year = 2011,
eccc = {TR11-145},
ecccurlid = {2011/145}
}
@inproceedings{Woodruff2004,
author = {David P. Woodruff},
title = {Optimal space lower bounds for all frequency
moments},
pages = {167--175},
doi = {10.1145/982792.982817},
crossref = {soda2004}
}
@article{Yannakakis1991,
author = {Mihalis Yannakakis},
title = {Expressing Combinatorial Optimization Problems by
Linear Programs},
journal = {J. Computer and System Sciences},
volume = 43,
number = 3,
year = 1991,
pages = {441--466},
doi = {10.1016/0022-0000(91)90024-Y},
note = {(Preliminary Version in {\em 20th STOC}, 1988)}
}
@proceedings{ccc2003,
title = {CCC 2003},
booktitle = {Proc.\ $18$th IEEE Conference on Computational Complexity},
date = {7-10~} # jul,
year = 2003,
city = {Aarhus, Denmark},
confpublisher = {IEEE}
}
@proceedings{ccc2009,
title = {CCC 2009},
booktitle = {Proc.\ $24$th IEEE Conference on Computational Complexity},
date = {15-18~} # jul,
year = 2009,
city = {Paris, France},
confpublisher = {IEEE}
}
@proceedings{ccc2010,
title = {CCC 2010},
booktitle = {Proc.\ $25$th IEEE Conference on Computational Complexity},
date = {9--12~} # jun,
year = 2010,
city = {Cambridge, Massachusetts},
confpublisher = {IEEE}
}
@proceedings{cocoon2010,
editor = {My T. Thai and Sartaj Sahni},
booktitle = {Proc.\ of $16$th Annual International Conference on
Computing and Combinatorics (COCOON)},
city = {Nha Trang, Vietnam},
date = {19--21~} # jul,
title = {COCOON 2011},
publisher = {Springer},
series = {LNCS},
volume = 6196,
year = 2010
}
@proceedings{focs1986,
title = {FOCS 1986},
booktitle = {Proc.\ $27$th IEEE Symp.\ on Foundations of Comp.\ Science (FOCS)},
city = {Toronto, Ontario, Canada},
date = {27--29~} # oct,
year = 1986,
confpublisher = {IEEE}
}
@proceedings{icalp2010a,
editor = {Samson Abramsky and Cyril Gavoille and Claude
Kirchner and Friedhelm Meyer auf der Heide and Paul
G. Spirakis},
booktitle = {Proc.\ $37$th International Colloquium of Automata, Languages and Programming (ICALP), Part I},
title = {ICALP 2010 (part I)},
date = {6--10~} # jul,
city = {Bordeaux, France},
publisher = {Springer},
series = {LNCS},
volume = 6198,
year = 2010
}
@proceedings{random11,
editor = {Leslie Ann Goldberg and Klaus Jansen and R. Ravi and
Jos{\'e} D. P. Rolim},
booktitle = {Proc.\ $15$th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)},
publisher = {Springer},
series = {LNCS},
volume = 6845,
year = 2011,
city = {Princeton, New Jersey},
date = {17--19~} # aug
}
@proceedings{soda2004,
title = {SODA 2004},
booktitle = {Proc.\ $15$th Annual {ACM}-{SIAM} Symposium on Discrete Algorithms (SODA)},
date = {11--13~} # jan,
year = 2004,
confpublisher = {SIAM},
city = {New Orleans, LA}
}
@proceedings{soda2010,
title = {SODA 2010},
booktitle = {Proc.\ $21$th Annual {ACM}-{SIAM} Symposium on Discrete Algorithms (SODA)},
date = {17--19~} # jan,
city = {Austin, Texas},
year = 2010,
confpublisher = {SIAM}
}
@proceedings{stoc2002,
booktitle = {Proc.\ $34$th ACM Symp.\ on Theory of Computing (STOC)},
title = {STOC 2002},
date = {19--21~} # may,
city = {Montr\'{e}al, Qu\'{e}bec, Canada},
year = 2002,
c-organization = {ACM},
confpublisher = {ACM}
}
@proceedings{stoc2003,
booktitle = {Proc.\ $35$th ACM Symp.\ on Theory of Computing (STOC)},
title = {STOC 2003},
date = {9--11~} # jun,
year = 2003,
c-organization = {ACM},
city = {San Diego, California},
key = {ACM},
confpublisher = {ACM}
}
@proceedings{stoc2007,
booktitle = {Proc.\ $39$th ACM Symp.\ on Theory of Computing (STOC)},
title = {STOC 2007},
city = {San Diego, California},
year = 2007,
date = {11--13~} # jun,
c-organization = {ACM},
confpublisher = {ACM}
}
@proceedings{stoc2008,
booktitle = {Proc.\ $40$th ACM Symp.\ on Theory of Computing (STOC)},
title = {STOC 2008},
year = 2008,
city = {Victoria, British Columbia, Canada},
date = {17--20~} # may,
c-organization = {ACM},
confpublisher = {ACM}
}
@proceedings{stoc2010,
booktitle = {Proc.\ $42$nd ACM Symp.\ on Theory of Computing (STOC)},
title = {STOC 2010},
city = {Cambridge, Massachusetts},
year = 2010,
date = {6--8~} # jun,
c-organization = {ACM},
confpublisher = {ACM}
}
@proceedings{stoc2011,
booktitle = {Proc.\ $43$rd ACM Symp.\ on Theory of Computing (STOC)},
title = {STOC 2011},
city = {San Jose, California},
year = 2011,
date = {6--8~} # jun,
c-organization = {ACM},
confpublisher = {ACM}
}