OmniBib.bib.
Note: Everything is a comment except what starts with "at"
until the end of the entry
Use # to concatenate strings
Strings
@string{jacm={Journal of the ACM}}
@string{sicomp = {SIAM J.~on Computing}}
@string{ipl = {Information Processing Letters}}
@string{compcomp = {Computational Complexity}}
@string{jcss = {J.~of Computer and System Sciences}}
@string{talg = {ACM Trans.~on Algorithms}}
@string{toct = {ACM Trans.~Computation Theory}}
@string{focs = {IEEE Symp.~on Foundations of Computer Science (FOCS)}}
@string{stoc = {ACM Symp.~on the Theory of Computing (STOC)}}
@string{ccc = {IEEE Conf.~on Computational Complexity (CCC)}}
@string{itcs = {ACM Innovations in Theoretical Computer Science conf.~(ITCS)}}
@string{random = {Workshop on Randomization and Computation (RANDOM)}}
@string{icalp = {Coll.~on Automata, Languages and Programming (ICALP)}}
@string{stacs = {Symp.~on Theoretical Aspects of Computer Science (STACS)}}
@string{eccc = {Electronic Coll.~on Computational Complexity (ECCC)}}
@string{lncs = {Lecture Notes in Computer Science}}
@string{soda = {ACM-SIAM Symp.~on Discrete Algorithms (SODA)}}
@string{tcc = {Theory of Cryptography Conf.~(TCC)}}
@string{mfcs = {Symp.~on Math.~Foundations of Computer Science (MFCS)}}
@string{ches = {Int.~Workshop on Cryptographic Hardware and Embedded Systems (CHES)}}
My Papers
@BLAHPRINT{
blahprintl={\Header{PREPRINTS} \begin{revnumerate}},
blahprinth={}
}
@unpublished{Viola-ccsum,
author = {Emanuele Viola},
title = {The communication complexity of addition},
blahdoc = {papers/ccsum.pdf},
year = {2011}
}
@UNPUBLISHED{GalHKPV-codes,
author = {Anna G\'al and Kristoffer Arnsfelt Hansen and Michal Kouck\'{y} and Pavel Pudl\'{a}k and Emanuele Viola},
title = {Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates},
year = {2011},
blahdoc={papers/ecc-ckt.pdf}
}
@unpublished{MilesV-aes,
author = {Eric Miles and Emanuele Viola},
title = {Block ciphers, pseudorandom functions, and natural proofs},
year = {2011},
blahdoc={papers/blockcipher.pdf},
}
@UNPUBLISHED{HLV-arora,
author = {Jasmina Hasanhodzic and Andrew Lo and Emanuele Viola},
title = {Do humans perceive temporal order in asset returns?},
year = {2010},
blahdoc={papers/aroraV3.pdf},
blahnoteh={Play the game
Press coverage: Financial Times (link),
MIT Technology Review
}
}
@UNPUBLISHED{GreenKV-polysearch,
author = {Frederic Green and Daniel Kreymer and Emanuele Viola},
title = {In Brute-Force Search of Correlation Bounds for Polynomials},
year = {2011},
blahdoc={papers/polysearch.pdf},
blahcode={code/poly.c}
}
@BLAHPRINT{
blahprintl={\end{revnumerate} \Header{RESARCH PAPERS} All of the conferences (and journals) below are peer reviewed. \begin{revnumerate}},
blahprinth={}
}
@inproceedings{Viola-stone,
author = {Emanuele Viola},
title = {Extractors for circuit sources},
booktitle = focs,
year = {2011},
blahdoc={papers/stone.pdf},
blahslides={talks/stone-focs-10-2011.pdf},
blahnotel={Invited and submitted to {\bf FOCS Special Issue}},
blahnoteh={Invited and submitted to FOCS Special Issue},
}
@inproceedings{FeffermanSUV10,
author = {Bill Fefferman and Ronen Shaltiel and Christopher Umans and Emanuele Viola},
title = {On beating the hybrid argument},
booktitle = itcs,
year = {2012},
blahdoc={papers/hybrid.pdf}
}
@inproceedings{Viola-rbd,
author = {Emanuele Viola},
title = {Randomness buys depth for approximate counting},
booktitle = focs,
year = {2011},
blahdoc={papers/rbd.pdf},
blahslides={talks/rbd-focs-10-2011.pdf}
}
@inproceedings{MilesV-stre,
author = {Eric Miles and Emanuele Viola},
title = {On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators},
booktitle = tcc,
year = {2011},
pages = {522-539},
blahdoc={papers/stre.pdf}
}
@article{HLV09,
author = {Jasmina Hasanhodzic and Andrew W. Lo and Emanuele Viola},
title = {A Computational View of Market Efficiency},
journal = {Quantitative Finance},
volume = {11},
number = {7},
year = {2011},
blahdoc={papers/HLV-rev-comp-fin.pdf}
}
@inproceedings{Lovett-viola-codes,
AUTHOR = {Shachar Lovett and Emanuele Viola},
title = {Bounded-depth circuits cannot sample good codes},
booktitle = ccc,
year = {2011},
blahdoc={papers/LoV.pdf},
blahnotel = {Invited and submitted to special issue of Computational Complexity}
blahnoteh = {Invited and submitted to special issue of Computational Complexity}
}
@article{viola-are,
author = {Emanuele Viola},
title = {The complexity of distributions},
journal = sicomp,
blahprelimbooktitle = {51th } # focs,
blahprelimyear = {2010},
note = {To appear},
blahdoc={papers/eh.pdf},
blahslides={talks/eh-MIT-3-2011.pdf},
blahvideo={http://ieee-focs.org/},
blahnoteh={Subsumes the manuscript
``Are all distributions easy?''},
}
Place here arora!
@inproceedings{PatrascuV10,
author = "Mihai P{\v a}tra{\c s}cu and Emanuele Viola",
title = "Cell-probe lower bounds for succinct partial sums",
booktitle = {21th } # soda,
pages = {117-122},
year = {2010},
blahdoc={papers/PaV-SODA10.pdf},
blahnoteh={A related Paper},
blahslides={talks/dataStruct-12-2009.pdf}
}
@article{DGJSV-bifh,
author = {Ilias Diakonikolas and Parikshit Gopalan and Ragesh Jaiswal and Rocco A. Servedio and Emanuele Viola},
title = {Bounded Independence Fools Halfspaces},
journal = sicomp,
volume = {39},
number = {8},
pages = {3441-3462},
publisher = {SIAM},
year = {2010},
blahprelimbooktitle = {50th } # focs,
blahprelimyear = {2009},
blahdoc={papers/bifh-final.pdf},
blahslides={talks/halfspaces-IAS-April-2009.pdf},
blahnoteh={This paper in particular shows that the
central-limit theorem holds even for variables that are
only k-wise independent.}
}
@article{viola-triz,
author = {Emanuele Viola},
title = {Bit-probe lower bounds for succinct data structures},
journal = sicomp,
note = {To appear},
blahprelimbooktitle={41th } # stoc,
blahprelimpages={475-482},
blahprelimyear = {2009},
blahnotel={{\bf STOC Special Issue}},
blahnoteh={STOC Special Issue},
blahdoc={papers/triz.pdf},
blahslides={talks/triz-STOC-2009.pdf}
}
@article{DPV08,
author = {Matei David and Toniann Pitassi and Emanuele Viola},
title = {Improved separations between nondeterministic and randomized multiparty communication},
journal = toct,
volume = {1},
number = {2},
year = {2009},
pages = {1--20},
blahprelimbooktitle = {12th } # random,
blahprelimyear = {2008},
blahdoc={papers/DPV-RP_vs_NP-journal-r2.pdf}
}
@article{Viola-d,
author = {Emanuele Viola},
title = {The sum of $d$ small-bias generators fools polynomials of degree $d$},
journal = compcomp,
volume = {18},
number = {2},
year = {2009},
pages = {209-217},
blahnoteh = {Best paper award},
blahnotel = {{\bf Best paper award}},
blahprelimbooktitle = ccc,
blahprelimyear = {2008},
blahdoc={papers/d.pdf},
blahslides={talks/TheoryDay07-talk.pdf}
}
@article{ShV-dec,
author = {Ronen Shaltiel and Emanuele Viola},
title = {Hardness amplification proofs require majority},
journal = sicomp,
volume = {39},
number = {7},
pages = {3122-3154},
year = {2010},
blahprelimbooktitle={40th } # stoc,
blahprelimpages = {589-598},
blahprelimyear = {2008},
blahdoc={papers/dec.pdf},
blahslides={talks/talk-dec-Banff.pdf}
}
@article{ViW-PJ,
author = {Emanuele Viola and Avi Wigderson},
title = {One-way multiparty communication lower bound for pointer jumping with applications},
year = {2009},
volume = {29},
number = {6},
pages = {719-743},
journal = {Combinatorica},
publisher = {Springer},
blahprelimbooktitle ={48th } # focs,
blahprelimyear = {2007},
blahnoteh = {Invited to FOCS Special Issue},
blahnotel = {Invited to {\bf FOCS Special Issue}},
blahdoc={papers/PJguess.pdf},
blahslides={talks/PJ-FOX-2007.pdf}
}
@article{BoV-gen,
author = {Andrej Bogdanov and Emanuele Viola},
title = {Pseudorandom bits for polynomials},
publisher = {SIAM},
year = {2010},
journal = sicomp,
volume = {39},
number = {6},
pages = {2464-2486},
blahdoc={papers/gen2.pdf},
blahslides={talks/genTalk-FOX-07.pdf},
blahprelimbooktitle= focs,
blahprelimyear=2007,
blahnoteh = {FOCS Special Issue},
blahnotel = {{\bf FOCS Special Issue}}
}
@article{ViW-GF2,
author = {Emanuele Viola and Avi Wigderson},
title = {Norms, {XOR} lemmas, and lower bounds for {GF(2)} polynomials and multiparty protocols},
journal = {Theory of Computing},
volume = {4},
pages = {137-168},
year = {2008},
blahprelimbooktitle=ccc,
blahprelimyear=2007,
blahdoc={papers/GF2+CC.pdf},
blahslides={talks/GF2-ccc-June2007.pdf},
blahnoteh={
The results on polynomials appeared also in the 2006
Report "New correlation bounds for GF(2) polynomials
using Gowers uniformity"}
}
@article{ViolaBPvsE,
author = {Emanuele Viola},
title = {On approximate majority and probabilistic time},
journal = compcomp,
volume = {18},
number = {3},
year = {2009},
pages = {337-375},
blahprelimbooktitle=ccc,
blahprelimyear={2007},
blahprelimpages={155-168},
blahdoc={papers/BPvsE.pdf},
blahslides={talks/BPvsE-IAS109.pdf}
}
@article{Viola-SYMAC0,
author = {Emanuele Viola},
title = {Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates},
publisher = {SIAM},
year = {2007},
journal = sicomp,
volume = {36},
number = {5},
pages = {1387-1403},
blahprelimbooktitle = {20th } # ccc,
blahprelimpages = {198-209},
blahprelimyear = {2005},
blahnoteh={SIAM Student Paper Prize},
blahnotel={{\bf SIAM Student Paper Prize}},
blahdoc={papers/SYMAC0.pdf},
blahslides={talks/SYMAC0-1hour.ppt}
}
@inproceedings{Vio04a,
author = {Emanuele Viola},
title = {On Constructing Parallel Pseudorandom Generators from One-Way Functions},
pages = {183-197},
booktitle = {20th } # ccc,
year = {2005},
blahdoc={papers/OnParallelPRG.pdf},
blahslides={talks/OnConstructingParallelPRG.ppt}
}
@inproceedings{HeV06,
author = {Alexander Healy and Emanuele Viola},
title = {Constant-Depth Circuits for Arithmetic in Finite Fields of
Characteristic Two},
booktitle = "23rd " # stacs,
year = {2006},
pages = {672-683},
publisher = {Springer},
blahdoc={papers/FieldOps.pdf}
}
above series = {Lecture Notes in Computer Science, Volume 3884}
@inproceedings{GuV04,
author = "Dan Gutfreund and Emanuele Viola",
title = "Fooling Parity Tests with Parity Gates",
pages = "381-392",
booktitle = {8th} # random,
publisher = {Springer},
year = {2004},
blahdoc={papers/RANDOM04.pdf},
blahslides={talks/RANDOM04.ppt}
}
Above: series = {Lecture Notes in Computer Science, Volume 3122},
@article{HVV-NP,
author = {Alexander Healy and Salil P. Vadhan and Emanuele Viola},
title = {Using Nondeterminism to Amplify Hardness},
journal = sicomp,
volume = {35},
number = {4},
year = {2006},
pages = {903-931},
blahnoteh = {STOC Special Issue},
blahnotel = {{\bf STOC Special Issue}},
blahprelimbooktitle=stoc,
blahprelimyear = {2004},
blahprelimpages = {192--201},
blahdoc={papers/NPJournal.pdf},
blahslides={talks/NPTalkIASShow.pps}
}
@article {Vio04c,
AUTHOR = {Emanuele Viola},
TITLE = {The Complexity of Constructing Pseudorandom Generators from Hard Functions},
JOURNAL = compcomp,
VOLUME = {13},
year = {2004},
NUMBER = {3-4},
PAGES = {147--188},
blahprelimbooktitle=ccc,
blahprelimyear=2003,
blahdoc={papers/JournalCCC03.pdf},
blahslides={talks/CCC03.pdf}
}
@inproceedings{Vio01,
author = "Emanuele Viola",
title = "E-unifiability via Narrowing",
pages = "426-438",
booktitle = "7th Italian Conference on Theoretical Computer Science (ICTCS)",
series = lncs,
volume = {2202},
year = {2001},
blahdoc={papers/EVN.pdf},
blahslides={talks/EVNTalk.ps}
}
@BLAHPRINT{
blahprintl={\end{revnumerate} \Header{SURVEYS AND MY PH.D.~THESIS} All of the surveys below are peer reviewed. \begin{revnumerate}},
blahprinth={}
}
@article{Viola-add,
author = {Emanuele Viola},
title = {Selected Results in Additive Combinatorics: An Exposition},
year = {2011},
pages = {1-15},
journal = {Theory of Computing Library, Graduate Surveys series},
number = {3},
blahdoc={papers/add.pdf}
}
@article{viola-FTTCS09,
author = {Emanuele Viola},
title = {On the power of small-depth computation},
journal = {Foundations and Trends in Theoretical Computer Science},
volume = {5},
number = {1},
year = {2009},
publisher = {Now Publishing},
pages = {1--72},
blahdoc={papers/shallow.pdf},
blahnoteh={Invited survey, subsumes SIGACT 2009 survey},
blahnotel={Invited survey}
}
@article{viola-SIGACT09,
notes = {complexity theory column 61},
author = {Emanuele Viola},
title = {Correlation bounds for polynomials over $\{0,1\}$},
journal = {SIGACT News, Complexity Theory Column},
number = {1},
volume = {40},
year = {2009},
blahdoc={papers/viola-sigact-gf2.pdf},
blahnoteh={Invited survey},
blahnotel={Invited survey}
}
Next is thesis treated as journal for Blah.
A PhDThesis entry is below after BLAHEND
@article{Viola-PhDthesis-journal-hack,
author = {Emanuele Viola},
title= {The Complexity of Hardness Amplification and Derandomization},
journal={Ph.D.~thesis, Harvard University},
year = {2006},
blahdoc={papers/thesis.pdf},
blahslides={talks/DefenseTalk109.pdf}
}
@BLAHPRINT{
blahprintl={\end{revnumerate} \Header{NOTES} \begin{revnumerate}},
blahprinth={}
}
@unpublished{viola-pros,
author = {Emanuele Viola},
title = {Think like the pros},
year = {2011},
blahnotel = {Lecture notes aimed towards students lacking mathematical maturity},
blahnoteh = {Lecture notes aimed towards students lacking mathematical maturity},
blahdoc={papers/pros.pdf}
}
@UNPUBLISHED{Viola-xxx,
author = {Emanuele Viola},
title = {Reducing {3XOR} to listing triangles, an exposition},
year = {2011},
blahdoc={papers/xxx.pdf}
}
@unpublished{viola-gems09,
author = {Emanuele Viola},
title = {Gems of Theoretical Computer Science},
year = {2009},
note = {Lecture notes of the class taught at Northeastern University.
Available at http://www.ccs.neu.edu/home/viola/classes/gems-08/index.html},
blahnoteh = {Lecture notes of the class taught at Northeastern University},
blahnotel = {Lecture notes of the class taught at Northeastern University},
blahdoc={http://www.ccs.neu.edu/home/viola/classes/gems-08/index.html}
}
@BLAHCLOSEH{needssomething,}
%More papers by research group
@BLAHPRINT{
blahprintl={\end{revnumerate} \Header{OTHER WORKS BY RESARCH GROUP} \begin{revnumerate}},
blahprinth={}
}
@unpublished{DuttaPRS11,
Author = {Chinmoy Dutta and Gopal Pandurangan and Rajmohan Rajaraman and Zhifeng Sun},
Title = {Information Spreading in Dynamic Networks},
Year = {2011},
blahnotel= {arXiv:1112.0384},
}
@unpublished{BuschDRS11,
Author = {Costas Busch and Chinmoy Dutta and Jaikumar Radhakrishnan and Rajmohan Rajaraman and Srivathsan Srinivasagopalan},
Title = {Split and Join: Strong Partitions and Universal Steiner Trees for Graphs},
Year = {2011},
blahnotel = {arXiv:1111.4766},
}
@unpublished{DuttaR11,
author = {Chinmoy Dutta and Jaikumar Radhakrishnan},
title = {More on a Problem of Zarankiewicz},
year = {2011}
}
@BLAHPRINT{
blahprintl={\end{revnumerate}},
blahprinth={}
}
@BLAHEND{needsomething,}
Other stuff related to me, including old links just in case
to compile (but many I killed already ;-)
@PhdThesis{Vio-PhD,
author = {Emanuele Viola},
title = {The Complexity of Hardness Amplification and Derandomization},
school = {Harvard University},
year = {2006},
blahdoc={papers/thesis.pdf},
blahslides={talks/DefenseTalk109.pdf}
}
@unpublished{VioSYMAC01SYM-Historical,
author = {Emanuele Viola},
title = {Pseudorandom Bits for Constant-Depth Circuits with One Arbitrary Symmetric Gates},
year = {2005},
note={Unpublished manuscript}
}
@Misc{ViolaGF2,
author = {Emanuele Viola},
title = {New correlation bounds for {GF(2)} polynomials using {G}owers uniformity},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR06-097},
year = {2006},
note = {www.eccc.uni-trier.de/}
}
@inproceedings{ViW-PJ-conferenceVersion,
author = {Emanuele Viola and Avi Wigderson},
title = {One-way multiparty communication lower bound for pointer jumping with applications},
booktitle ={48th } # focs,
year = {2007},
publisher = {IEEE}
}
@MISC{HLV-videogamelink,
author = {Jasmina Hasanhodzic and Andrew Lo and Emanuele Viola},
title = {{ARORA}: {A} {R}andom {O}r {R}eal {A}rray},
note = {www.ccs.neu.edu/home/viola/arora/},
year = {2009}
}
@MISC{viola-rank,
author = {Emanuele Viola},
title = {Cell-probe lower bounds for prefix sums},
note = {arXiv:0906.1370v1},
year = {2009}
}
@misc{viola-theory-phd11,
author = {Emanuele Viola},
title = {Graduate Theory of Computation},
year = {2011},
note = {Class taught at Northeastern University in Spring 2011: http://www.ccs.neu.edu/home/viola/classes/toc-spring11/index.html}
}
@misc{mathoverflow-localview,
note = {http://mathoverflow.net/questions/12154/local-view-of-setting-pn-out-of-n-bits-to-1}
}
Papers by other people
@inproceedings{CzumajKKL99,
author = {Artur Czumaj and
Przemyslawa Kanarek and
Miroslaw Kutylowski and
Krzysztof Lorys},
title = {Delayed Path Coupling and Generating Random Permutations
via Distributed Stochastic Processes},
booktitle = soda,
year = {1999},
pages = {271-280},
ee = {http://doi.acm.org/10.1145/314500.314571},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@misc{CzumajKKL00,
author = {Artur Czumaj and
Przemyslawa Kanarek and
Miroslaw Kutylowski and
Krzysztof Lorys},
title = {Switching Networks for Generating Random Permutations},
booktitle = {In Switching Networks: Recent Advances. Vol.~5 in Series Network Theory and Applications},
year = {2001},
pages = {25 - 61},
publisher = {Kluwer Academic}
}
@article{Holmes2004,
author = {Susan Holmes},
title = {Stein's method for birth and death chains},
volume = {46},
booktitle = {Stein's Method: Expository Lectures and Applications.
IMS Lecture Notes - Monograph Series},
year = {2004}
}
@article{Erdos45,
author={Paul Erd{\H{o}}s},
title={{On a lemma of {L}ittlewood and {O}fford}},
journal={Bull. Amer. Math. Soc.},
year={1945},
volume={51},
pages={898-902}
}
@article{LittlewoodOfford43,
author={John Littlewood and Albert Offord},
title={{On the number of real roots of a random algebraic equation}},
journal={III. Rec. Math. [Mat. Sbornik] N.S.},
year={1943},
volume={12},
pages={277-286}
}
@inproceedings{Sarmenta98,
author = {Luis F. G. Sarmenta},
title = {Bayanihan: Web-Based Volunteer Computing Using Java},
booktitle = {2nd Int. Conf. on Worldwide Computing and Its Applications (WWCA)},
year = {1998},
pages = {444-461}
}
@inproceedings{GoldwasserKR08,
author = {Shafi Goldwasser and
Yael Tauman Kalai and
Guy N. Rothblum},
title = {Delegating computation: interactive proofs for muggles},
booktitle = {40th } # stoc,
publisher = {ACM},
year = {2008},
pages = {113-122}
}
@article {DuenezMRS06,
AUTHOR = {Due{\~n}ez, Eduardo and Miller, Steven J. and Roy, Amitabha
and Straubing, Howard},
TITLE = {Incomplete quadratic exponential sums in several variables},
JOURNAL = {J. Number Theory},
FJOURNAL = {Journal of Number Theory},
VOLUME = {116},
year = {2006},
NUMBER = {1},
PAGES = {168--199},
ISSN = {0022-314X},
CODEN = {JNUTA9},
MRCLASS = {11L07 (11G25)},
MRNUMBER = {MR2197866 (2007c:11092)},
MRREVIEWER = {S. W. Graham},
}
@inproceedings{Bazzi07,
author = {Louay Bazzi},
title={Polylogarithmic Independence can Fool {DNF} Formulas},
booktitle={48th IEEE } # focs,
pages={63-73},
year={2007}
}
@article{Bazzi09,
author = {Louay M. J. Bazzi},
title = {Polylogarithmic Independence Can Fool DNF Formulas},
journal = {SIAM J. Comput.},
volume = {38},
number = {6},
year = {2009},
pages = {2220-2272},
ee = {http://dx.doi.org/10.1137/070691954},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{BellareCHKS96,
author = {Mihir Bellare and
Don Coppersmith and
Johan H{\aa}stad and
Marcos A. Kiwi and
Madhu Sudan},
title = {Linearity testing in characteristic two},
journal = {IEEE Transactions on Information Theory},
volume = {42},
number = {6},
year = {1996},
pages = {1781-1795}
}
@article{BlumLR93,
author = {Manuel Blum and
Michael Luby and
Ronitt Rubinfeld},
title = {Self-Testing/Correcting with Applications to Numerical Problems},
journal = {J. Comput. Syst. Sci.},
volume = {47},
number = {3},
year = {1993},
pages = {549-595}
}
@article{Trevisan09-SIGACT,
author = {Luca Trevisan},
title = {Additive combinatorics and theoretical computer
science},
journal = {SIGACT News},
volume = {40},
number = {2},
year = {2009},
pages = {50-66}
}
@inproceedings{MatiasV91,
author = {Yossi Matias and
Uzi Vishkin},
title = {Converting High Probability into Nearly-Constant Time-with
Applications to Parallel Hashing},
booktitle = {23rd } # stoc,
publisher = {ACM},
year = {1991},
pages = {307-316}
}
@inproceedings{Hagerup91,
author = {Torben Hagerup},
title = {Fast Parallel Generation of Random Permutations},
booktitle = {18th } # icalp,
year = {1991},
pages = {405-416},
publisher = {Springer}
}
@inproceedings{Trevisan04,
author = {Luca Trevisan},
title = {A Note on Approximate Counting for k-{DNF}},
booktitle = {7th } # random,
year = {2004},
pages = {417-426},
publisher = {Springer},
series = lncs,
volume = {3122}
}
@article{GuruswamiUV09,
author = {Venkatesan Guruswami and
Christopher Umans and
Salil P. Vadhan},
title = {Unbalanced expanders and randomness extractors from Parvaresh--Vardy
codes},
journal = {J. ACM},
volume = {56},
number = {4},
year = {2009},
ee = {http://doi.acm.org/10.1145/1538902.1538904},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{DurisGS87,
author = {Pavol Duris and
Zvi Galil and
Georg Schnitger},
title = {Lower Bounds on Communication Complexity},
journal = {Inf. Comput.},
volume = {73},
number = {1},
year = {1987},
pages = {1-22},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Rossman08,
author = {Benjamin Rossman},
title = {On the constant-depth complexity of k-clique},
booktitle={40th } # stoc,
publisher = {ACM},
year = {2008},
}
@inproceedings{Braverman09,
author={Mark Braverman},
title={{Poly-logarithmic independence fools $AC^0$ circuits}},
booktitle = {24th } # ccc,
year={2009},
publisher = {IEEE}
}
@inproceedings{Gronemeier06,
author = {Andre Gronemeier},
title = {NOF-Multiparty Information Complexity Bounds for Pointer
Jumping},
booktitle = {31st } # mfcs,
year = {2006},
pages = {459-470},
publisher = {Springer},
series = lncs,
volume = {4162}
}
@inproceedings{Brody09,
author={Joshua Brody},
title={The Maximum Communication Complexity of Multiparty Pointer Jumping},
booktitle = {Proc. 24th } # ccc,
year={2009},
publisher = {IEEE}
}
@inproceedings{IwamaM02,
author = {Kazuo Iwama and
Hiroki Morizumi},
title = {An Explicit Lower Bound of $5n - o(n)$ for Boolean Circuits},
booktitle = {Mathematical Foundations of Computer Science (MFCS)},
year = {2002},
pages = {353-364}
}
@inproceedings{AgrawalV08,
author = {Manindra Agrawal and
V. Vinay},
title = {Arithmetic Circuits: A Chasm at Depth Four},
booktitle = {49th IEEE } # focs,
year = {2008},
pages = {67-75}
}
@proceedings{DBLP:conf/focs/2008,
title = {49th IEEE Symposium on Foundations of Computer Science,
FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA},
booktitle = {FOCS},
publisher = {IEEE Computer Society},
year = {2008},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@misc{PaT09Succincterer,
author = "Mihai P{\v a}tra{\c s}cu and Mikkel Thorup",
title = "Succincter-er",
note = {Manuscript},
pages = {305-313},
year = {2009}
}
%%Voting
@UNPUBLISHED{Rivest08,
AUTHOR = {Ronald L. Rivest},
TITLE = {A ``sum of square roots'' ({SSR}) pseudorandom sampling method for election audits},
NOTE = {Working paper available at: http://people.csail.mit.edu/rivest/publications},
year = {2008}
}
@MISC{APR08,
author = {Javed Aslam and Raluca A. Popa and Ronald L. Rivest.},
title = {On Auditing Elections When Precincts Have Different Sizes},
note = {Working paper. Available at \texttt{http://people.csail.mit.edu/rivest/publications.html}},
url = {http://people.csail.mit.edu/rivest/publications.html},
month = {January},
day = {17},
year = {2008}
}
@inproceedings{Wigderson:amazingPower,
author = {Wigderson, Avi},
title = {The amazing power of pairwise independence},
booktitle = {26th ACM } # stoc,
year = {1994},
publisher = {ACM}
}
@article{BGL06,
author = {Nayantara Bhatnagar and
Parikshit Gopalan and
Richard J. Lipton},
title = {Symmetric polynomials over ${Z}_m$ and simultaneous
communication protocols},
journal = {J. Comput. Syst. Sci.},
volume = {72},
number = {2},
year = {2006},
pages = {252-285},
ee = {http://dx.doi.org/10.1016/j.jcss.2005.06.007},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{CaiGT96,
author = {Jin-Yi Cai and
Frederic Green and
Thomas Thierauf},
title = {On the Correlation of Symmetric Functions},
journal = {Mathematical Systems Theory},
volume = {29},
number = {3},
year = {1996},
pages = {245-258},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Freund95,
author = {Freund, Y. },
citeulike-article-id = {1109942},
doi = {http://dx.doi.org/10.1006/inco.1995.1136},
journal = {Information and Computation},
keywords = {boosting, majority},
month = {September},
number = {2},
pages = {256--285},
posted-at = {2007-02-16 17:34:28},
priority = {3},
title = {Boosting a Weak Learning Algorithm by Majority},
url = {http://dx.doi.org/10.1006/inco.1995.1136},
volume = {121},
year = {1995}
}
@inproceedings{GalTrifonov06,
author = {Anna G{\'a}l and
Vladimir Trifonov},
title = {On the Correlation Between Parity and Modular Polynomials},
booktitle = {31st Symposium on Mathematical Foundations of Computer Science (MFCS)},
year = {2006},
pages = {387-398},
publisher = {Springer},
series = lncs,
volume = {4162}
}
@proceedings{mfcs2006,
editor = {Rastislav Kralovic and
Pawel Urzyczyn},
title = {Mathematical Foundations of Computer Science 2006, 31st
Symposium, MFCS 2006, Star{\'a} Lesn{\'a},
Slovakia, August 28-September 1, 2006, Proceedings},
booktitle = {MFCS},
publisher = {Springer},
series = lncs,
volume = {4162},
year = {2006},
isbn = {3-540-37791-3},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book{DrmotaTichy1997,
author = {Drmota, Michael and Tichy, Robert F.},
title = {Sequences, Discrepancies and Applications},
series = {Lecture Notes in Mathematics},
volume = {1651},
publisher = {Springer},
year = {1997}
}
@book{BabaiF92,
author = {L{\'a}szl{\'o} Babai and
Peter Frankl},
title = {Linear algebra methods in combinatorics},
year = {1992}
}
@book{SanjeevBarak2007,
AUTHOR = {Arora, Sanjeev and Barak, Boaz},
TITLE = compcomp,
NOTE = {A modern approach},
PUBLISHER = {Cambridge University Press},
year = {2009},
PAGES = {xxiv+579},
ISBN = {978-0-521-42426-4}
}
@incollection {BoppanaSipser90,
AUTHOR = {Boppana, Ravi B. and Sipser, Michael},
TITLE = {The complexity of finite functions},
BOOKTITLE = {Handbook of theoretical computer science, {V}ol.\ {A}},
PAGES = {757--804},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
year = {1990},
MRCLASS = {68Q15},
MRNUMBER = {MR1127180}
}
@book{CloteKranakis2002,
author = {Clote, Peter and Kranakis, Evangelos },
citeulike-article-id = {3377572},
keywords = {phd},
posted-at = {2008-10-05 20:38:23},
priority = {0},
publisher = {Springer},
title = {{B}oolean Functions and Computation Models},
year = {2002}
}
@book{Dickson19,
author = {L. E. Dickson},
title = {History of the Theory of Numbers, Vol. 1},
publisher = {Chelsea, New York, NY},
year = {1919}
}
@inproceedings{GranvilleRudnick07,
author = {Andrew Granville and Ze{\'e}v Rudnick},
title = {Uniform distribution},
booktitle = {Equidistribution in Number Theory, An Introduction},
SERIES = {NATO Science Series II: Mathematics, Physics and Chemistry},
VOLUME = {237},
PUBLISHER = {Springer},
year = {2007},
ISBN = {978-1-4020-5403-7},
pages = {1-13}
}
@book{BakerWustholz2007,
AUTHOR = {Baker, Alan and W{\"u}stholz, Gisbert},
TITLE = {Logarithmic forms and {D}iophantine geometry},
SERIES = {New Mathematical Monographs},
VOLUME = {9},
PUBLISHER = {Cambridge University Press},
year = {2007}
}
@book{Baker1990,
AUTHOR = {Baker, Alan},
TITLE = {Transcendental number theory},
SERIES = {Cambridge Mathematical Library},
EDITION = {Second},
PUBLISHER = {Cambridge University Press},
year = {1990}
}
@book{NumberTheoryIV-1998,
title = {Number Theory IV. Transcendental Numbers},
editor = {Parshin, A.N.; Shafarevich, I.R.},
publisher = {Springer},
year = {1998},
series = {Encyclopaedia of Mathematical Sciences , Vol. 44},
ISBN = {978-3-540-61467-8}
}
@book{MiP69,
title = {Perceptrons},
address = {Cambridge, MA},
author = {Marvin Minsky and Seymour Papert},
publisher = {MIT Press},
year = {1969}
}
@article {BGKL03,
AUTHOR = {Babai, L{\'a}szl{\'o} and G{\'a}l, Anna and Kimmel, Peter G.
and Lokam, Satyanarayana V.},
TITLE = {Communication complexity of simultaneous messages},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {33},
year = {2003},
NUMBER = {1},
PAGES = {137--166},
ISSN = {0097-5397},
MRCLASS = {68Q17 (68R05)},
MRNUMBER = {MR2033656 (2005a:68084)},
MRREVIEWER = {Johan H{\aa}stad},
}
@inproceedings{GolynskiGGRR07,
author = {Alexander Golynski and
Roberto Grossi and
Ankur Gupta and
Rajeev Raman and
S. Srinivasa Rao},
title = {On the Size of Succinct Indices},
booktitle = {ESA},
year = {2007},
pages = {371-382},
ee = {http://dx.doi.org/10.1007/978-3-540-75520-3_34},
crossref = {esa2007},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{esa2007,
editor = {Lars Arge and
Michael Hoffmann and
Emo Welzl},
title = {Algorithms - ESA 2007, 15th European Symposium, Eilat,
Israel, October 8-10, 2007, Proceedings},
booktitle = {ESA},
publisher = {Springer},
series = lncs,
volume = {4698},
year = {2007},
isbn = {978-3-540-75519-7}
}
@inproceedings{GolynskiRR08,
author = {Alexander Golynski and
Rajeev Raman and
S. Srinivasa Rao},
title = {On the Redundancy of Succinct Data Structures},
booktitle = {SWAT},
year = {2008},
pages = {148-159},
ee = {http://dx.doi.org/10.1007/978-3-540-69903-3_15},
crossref = {SWAT2008}
}
@proceedings{SWAT2008,
editor = {Joachim Gudmundsson},
title = {11th Scandinavian Workshop on Algorithm Theory (SWAT) 2008},
booktitle = {SWAT},
publisher = {Springer},
series = lncs,
volume = {5124},
year = {2008},
isbn = {978-3-540-69900-2}
}
@article{GearyRRR06,
author = {Richard F. Geary and
Naila Rahman and
Rajeev Raman and
Venkatesh Raman},
title = {A simple optimal representation for balanced parentheses},
journal = {Theor. Comput. Sci.},
volume = {368},
number = {3},
year = {2006},
pages = {231-246},
ee = {http://dx.doi.org/10.1016/j.tcs.2006.09.014},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@misc{Miltersen99cellprobe,
author = {Peter Bro Miltersen},
title = {Cell probe complexity - a survey},
note = {Invited talk/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS'99)},
year = {1999}
}
@article {GalMiltersen07,
AUTHOR = {G{\'a}l, Anna and Miltersen, Peter Bro},
TITLE = {The cell probe complexity of succinct data structures},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {379},
year = {2007},
NUMBER = {3},
PAGES = {405--417},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68P05 (68Q25)},
MRNUMBER = {MR2329209 (2008f:68021)},
}
@article {BMRV02,
AUTHOR = {Harry Buhrman and Peter Bro Miltersen and Jaikumar Radhakrishnan and Venkatesh Srinivasan},
TITLE = {Are bitvectors optimal?},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {31},
year = {2002},
NUMBER = {6},
PAGES = {1723--1744},
ISSN = {0097-5397},
MRCLASS = {68P10 (68P05 68P20)},
MRNUMBER = {MR1954872 (2004a:68014)},
}
@inproceedings{Patrascu08Succincter,
author = "Mihai P{\v a}tra{\c s}cu",
title = "Succincter",
booktitle = {49th } # focs,
publisher = {IEEE},
year = {2008}
}
@inproceedings{AlonBK08,
author = {Noga Alon and
Ido Ben-Eliezer and
Michael Krivelevich},
title = {Small Sample Spaces Cannot Fool Low Degree Polynomials},
booktitle = {12th } # random,
year = {2008},
publisher = {Springer},
pages = {266-275}
}
@inproceedings{BeameH09,
author = {Paul Beame and Dang-Trinh Huynh-Ngoc},
title = {Multiparty communication complexity and threshold circuit size of $\mathit{AC^0}$},
booktitle = {50th } # focs,
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR08-061},
publisher = {IEEE},
note = {To appear},
year = {2009}
}
@Misc{BeH08,
author = {Paul Beame and Dang-Trinh Huynh-Ngoc},
title = {Multiparty Communication Complexity of $\mathit{AC^0}$},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR08-061},
year = {2008},
note = {www.eccc.uni-trier.de/}
}
@Article{NisanRonen01,
author={Noam Nisan and Amir Ronen},
title={Algorithmic Mechanism Design},
journal={Games and Economic Behavior},
year=2001,
volume={35},
number={1-2},
pages={166-196},
month={April},
url={http://ideas.repec.org/a/eee/gamebe/v35y2001i1-2p166-196.html}
}
@article{Fama65,
author = {Eugene Fama},
title = {The behavior of stock market prices},
journal = {Journal of Business},
number = {38},
year = {1965},
pages = {34�105}
}
@article{Samuelson65,
author = {Paul Samuelson},
title = {Proof that properly anticipated prices fluctuate randomly},
journal = {Journal of Business},
number = {6},
year = {1965},
pages = {41�9}
}
@article{MorrisS04,
author = {Ben Morris and
Alistair Sinclair},
title = {Random Walks on Truncated Cubes and Sampling 0-1 Knapsack
Solutions},
journal = {SIAM J. Comput.},
volume = {34},
number = {1},
year = {2004},
pages = {195-226},
ee = {http://epubs.siam.org/sam-bin/dbq/article/41191},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Novikoff1963,
author = {Novikoff, Albert B. },
booktitle = {Symposium on the Mathematical Theory of Automata},
citeulike-article-id = {2073209},
keywords = {perceptron-learning-rule},
pages = {615--622},
posted-at = {2007-12-07 15:56:34},
priority = {2},
title = {On convergence proofs for perceptrons},
url = {http://citeseer.comp.nus.edu.sg/context/494822/0},
volume = {12},
year = {1963}
}
@article{Block1962,
author = {Block, H. },
citeulike-article-id = {2073744},
journal = {Reviews of Modern Physics},
keywords = {perceptron-learning-rule},
pages = {123--135},
posted-at = {2007-12-07 15:58:25},
priority = {2},
title = {The perceptron: a model for brain functioning},
volume = {34},
year = {1962}
}
@incollection{Pomerance86,
owner = "K",
author = "Carl Pomerance",
booktitle = "Discrete Algorithms and Complexity ( Japan-US Joint Seminar on Discrete Algorithms and
Complexity Theory)",
pages = "119--143",
publisher = "Academic Press",
title = "Fast, Rigorous Factorization and Discrete Logarithm
Algorithms",
year = "1986"
}
@article{GoldmannHR92,
author = {Mikael Goldmann and
Johan H{\aa}stad and
Alexander A. Razborov},
title = {Majority Gates VS. General Weighted Threshold Gates},
journal = compcomp,
volume = {2},
year = {1992},
pages = {277-300},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{CohnKSU05,
author = {Henry Cohn and
Robert D. Kleinberg and
Bal{\'a}zs Szegedy and
Christopher Umans},
title = {Group-theoretic Algorithms for Matrix Multiplication},
pages = {379-388},
crossref = {FOCS2005}
}
@proceedings{FOCS2005,
title = {46th IEEE Symposium on Foundations of Computer Science
(FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
booktitle = {46th IEEE Symposium on Foundations of Computer Science
(FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
publisher = {IEEE Computer Society},
year = {2005},
isbn = {0-7695-2468-0},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{BeameCH86,
author = {Paul Beame and
Stephen A. Cook and
H. James Hoover},
title = {Log Depth Circuits for Division and Related Problems},
journal = {SIAM J. Comput.},
volume = {15},
number = {4},
year = {1986},
pages = {994-1003},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{DaskalakisGP06,
author = {Constantinos Daskalakis and
Paul W. Goldberg and
Christos H. Papadimitriou},
title = {The complexity of computing a Nash equilibrium},
pages = {71-78},
booktitle = {38th } # stoc,
year = {2006},
publisher = {ACM}
}
@inproceedings{ChenD06,
author = {Xi Chen and
Xiaotie Deng},
title = {Settling the Complexity of Two-Player Nash Equilibrium},
pages = {261-272},
booktitle = {47th IEEE Symposium on Foundations of Computer Science
(FOCS)},
year = {2006}
}
@article{ApplebaumIK08,
author = {Benny Applebaum and
Yuval Ishai and
Eyal Kushilevitz},
title = {On Pseudorandom Generators with Linear Stretch in {$NC^0$}},
journal = compcomp,
volume = {17},
number = {1},
year = {2008},
pages = {38-69},
ee = {http://dx.doi.org/10.1007/s00037-007-0237-6},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{ApplebaumIK06RANDOM,
author = {Benny Applebaum and
Yuval Ishai and
Eyal Kushilevitz},
title = {On Pseudorandom Generators with Linear Stretch in NC$^{\mbox{0}}$},
booktitle = {APPROX-RANDOM},
year = {2006},
pages = {260-271},
ee = {http://dx.doi.org/10.1007/11830924_25},
crossref = {RANDOM2006},
bibsource = {DBLP, http://dblp.uni-trier.de},
note = { To appear in Journal of Computational Complexity, Special issue for Random 2006}
}
@proceedings{RANDOM2006,
editor = {Josep D\'{\i}az and
Klaus Jansen and
Jos{\'e} D. P. Rolim and
Uri Zwick},
title = {Approximation, Randomization, and Combinatorial Optimization.
Algorithms and Techniques, 9th Workshop on
Approximation Algorithms for Combinatorial Optimization
Problems, APPROX 2006 and 10th Workshop on
Randomization and Computation, RANDOM 2006, Barcelona, Spain,
August 28-30 2006, Proceedings},
booktitle = {APPROX-RANDOM},
publisher = {Springer},
series = lncs,
volume = {4110},
year = {2006},
isbn = {3-540-38044-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{GuR08,
author = {Dan Gutfreund and Guy Rothblum},
title = {The Complexity of Local List Decoding},
booktitle = {12th Intl. } # random,
year = {2008}
}
@misc{Kayal07,
AUTHOR = {N. Kayal},
TITLE = {The Complexity of the Annihilating Polynomial},
note = {Available at \texttt{http://www.math.ias.edu/csdm/06-07/files/kayal.pdf}},
year = {2007}
}
@inproceedings{Shpilka06,
author = {Amir Shpilka},
title = {Constructions of Low-Degree and Error-Correcting in-Biased
Generators},
booktitle = {IEEE Conference on Computational Complexity},
year = {2006},
pages = {33-45},
ee = {http://doi.ieeecomputersociety.org/10.1109/CCC.2006.15},
crossref = {CCC2006},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{CCC2006,
title = {21st IEEE Conference on Computational Complexity
(CCC 2006), 16-20 July 2006, Prague, Czech Republic},
booktitle = {IEEE Conference on Computational Complexity},
publisher = {IEEE Computer Society},
year = {2006},
isbn = {0-7695-2596-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{MosselST06,
author = {Elchanan Mossel and
Amir Shpilka and
Luca Trevisan},
title = {On epsilon-biased generators in {NC}$^{\mbox{0}}$},
journal = {Random Struct. Algorithms},
volume = {29},
number = {1},
year = {2006},
pages = {56-81},
ee = {http://dx.doi.org/10.1002/rsa.20112},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Sha48,
author = {Claude Shannon},
title = {A mathematical theory of communication},
journal = {Bell Systems Technical Journal},
volume = {27},
pages = {379-423 and 623-656},
year = {1948}
}
@article{Sha49,
author = {Claude Shannon},
title = {Communication Theory of Secrecy Systems},
journal = {Bell Systems Technical Journal},
volume = {28},
number = {4},
pages = {656-715},
year = {1949}
}
@article{MetropolisU49,
author = {Metropolis, Nicholas and Ulam, S. },
citeulike-article-id = {1886002},
journal = {Journal of the American Statistical Association},
number = {247},
pages = {335--341},
posted-at = {2007-11-08 20:07:21},
priority = {2},
title = {The Monte Carlo Method},
url = {http://www.jstor.org/stable/2280232},
volume = {44},
year = {1949}
}
@inproceedings{CalandrinoHF07,
author = {Joseph Calandrino and Alex Halderman and Edward Felten},
title = {Machine-Assisted Election Auditing},
booktitle = {Proceedings of Electronic Voting Technology (EVT)},
year = {2007},
note = {Available at: http://itpolicy.princeton.edu/voting/audit07full.pdf}
}
@inproceedings{Dyer03,
author = {Martin E. Dyer},
title = {Approximate counting by dynamic programming},
pages = {693-699},
crossref = {STOC2003}
}
@proceedings{STOC2003,
title = {35th ACM Symposium on Theory of
Computing (STOC), June 9-11, 2003, San Diego, CA, USA},
booktitle = {35th ACM Symposium on Theory of
Computing (STOC), June 9-11, 2003, San Diego, CA, USA},
publisher = {ACM},
year = {2003},
isbn = {1-58113-674-9}
}
@article{Servedio07,
author = {Rocco A. Servedio},
title = {Every Linear Threshold Function has a Low-Weight Approximator},
journal = compcomp,
volume = {16},
number = {2},
year = {2007},
pages = {180-209},
ee = {http://dx.doi.org/10.1007/s00037-007-0228-7},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@Misc{BeameH08,
author = {Paul Beame and Dang-Trinh Huynh-Ngoc},
title = {Multiparty Communication Complexity of $AC^0$},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR08-061},
year = {2008}
}
@article{AllenderBKMR06,
author = {Eric Allender and
Harry Buhrman and
Michal Kouck{\'y} and
Dieter van Melkebeek and
Detlef Ronneburger},
title = {Power from Random Strings},
journal = {SIAM J. Comput.},
volume = {35},
number = {6},
year = {2006},
pages = {1467-1493},
ee = {http://dx.doi.org/10.1137/050628994},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{KabanetsI04,
author = {Valentine Kabanets and
Russell Impagliazzo},
title = {Derandomizing Polynomial Identity Tests Means Proving Circuit
Lower Bounds},
journal = compcomp,
volume = {13},
number = {1-2},
year = {2004},
pages = {1-46},
ee = {http://dx.doi.org/10.1007/s00037-004-0182-6},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{AllenderK08,
author = {Eric Allender and
Michal Kouck{\'y}},
title = {Amplifying Lower Bounds by Means of Self-Reducibility},
booktitle = {IEEE Conference on Computational Complexity},
year = {2008},
pages = {31-40},
ee = {http://doi.ieeecomputersociety.org/10.1109/CCC.2008.11},
crossref = {CCC2008},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{AllenderK10,
author = {Eric Allender and
Michal Kouck{\'y}},
title = {Amplifying lower bounds by means of self-reducibility},
journal = {J. ACM},
volume = {57},
number = {3},
year = {2010},
ee = {http://doi.acm.org/10.1145/1706591.1706594},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Shor97,
author = {Peter W. Shor},
title = {Polynomial-Time Algorithms for Prime Factorization and Discrete
Logarithms on a Quantum Computer},
journal = {SIAM J. Comput.},
volume = {26},
number = {5},
year = {1997},
pages = {1484-1509},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{IshaiKOS08,
author = {Yuval Ishai and
Eyal Kushilevitz and
Rafail Ostrovsky and
Amit Sahai},
title = {Cryptography with constant computational overhead},
pages = {433-442},
year = {2008},
booktitle={40th ACM } # stoc
}
@inproceedings{KrauseL01,
author = {Matthias Krause and
Stefan Lucks},
title = {On the Minimal Hardware Complexity of Pseudorandom Function
Generators},
booktitle = stacs,
year = {2001},
pages = {419-430}
}
@inproceedings{AaronsonW08,
author = {Scott Aaronson and
Avi Wigderson},
title = {Algebrization: a new barrier in complexity theory},
pages = {731-740},
booktitle={40th ACM } # stoc,
year = {2008}
}
@article{AgrawalB03,
author = {Manindra Agrawal and
Somenath Biswas},
title = {Primality and identity testing via Chinese remaindering},
journal = {J. ACM},
volume = {50},
number = {4},
year = {2003},
pages = {429-443},
ee = {http://doi.acm.org/10.1145/792538.792540},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{RozenmanV05,
author = {Eyal Rozenman and
Salil P. Vadhan},
title = {Derandomized Squaring of Graphs},
booktitle = {APPROX-RANDOM},
year = {2005},
pages = {436-447},
ee = {http://dx.doi.org/10.1007/11538462_37},
crossref = {RANDOM2005},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{RANDOM2005,
editor = {Chandra Chekuri and
Klaus Jansen and
Jos{\'e} D. P. Rolim and
Luca Trevisan},
title = {Approximation, Randomization and Combinatorial Optimization,
Algorithms and Techniques, 8th Workshop on
Approximation Algorithms for Combinatorial Optimization
Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization
and Computation, RANDOM 2005, Berkeley, CA, USA, August
22-24, 2005, Proceedings},
booktitle = {APPROX-RANDOM},
publisher = {Springer},
series = lncs,
volume = {3624},
year = {2005},
}
@proceedings{RANDOM2008,
title = {12th Intl. Workshop on Randomization and Computation, RANDOM 2008, MIT, Boston, MA, August, 2008},
publisher = {Springer},
booktitle = {12th Intl. Workshop on Randomization and Computation, RANDOM 2008, MIT, Boston, MA, August, 2008},
series = lncs,
year = {2008},
}
@INPROCEEDINGS{DvirGabizonWigderson07,
AUTHOR = {Zeev Dvir and Ariel Gabizon and Avi Wigderson},
TITLE = {Extractors and Rank Extractors for Polynomial Sources},
BOOKTITLE = {FOCS '07: 48th IEEE Symposium on Foundations of Computer Science},
year = {2007},
ISBN = {0-7695-3010-9},
PAGES = {52--62},
DOI = {http://dx.doi.org/10.1109/FOCS.2007.26},
PUBLISHER = {IEEE Computer Society},
ADDRESS = {Washington, DC, USA},
crossref = {FOCS2007}
}
@MISC{Dvir08,
author = {Zeev Dvir},
title = {On the size of Kakeya sets in finite fields},
url = {http://www.citebase.org/abstract?id=oai:arXiv.org:0803.2336},
year = {2008}
}
@inproceedings{ReingoldTTV08,
author = {Omer Reingold and Luca Trevisan and Madhur Tulsiani and Salil Vadhan},
title = {Dense Subsets of Pseudorandom Sets},
booktitle = {49th } # focs,
publisher = {IEEE},
year = {2008}
}
@inproceedings{GopalanKS07,
author = {Parikshit Gopalan and
Subhash Khot and
Rishi Saket},
title = {Hardness of Reconstructing Multivariate Polynomials over
Finite Fields},
pages = {349-359},
booktitle={48th IEEE } # focs,
year = {2007}
}
@UNPUBLISHED{BHL08,
AUTHOR = {Ido Ben-Eliezer and Rani Hod and Shachar Lovett},
TITLE = {Random low degree polynomials are hard to approximate},
NOTE = {Manuscript},
year = {2008}
}
@UNPUBLISHED{BDVY08,
AUTHOR = {A. Bogdanov and Z. Dvir and E. Verbin and A. Yehudayoff},
TITLE = {Pseudorandomness for Width 2 Branching Programs},
NOTE = {Manuscript},
year = {2008},
URL = {http://www.wisdom.weizmann.ac.il/~zdvir/papers/lop.html/BDVY08.pdf}
}
@book{AiZ03,
author = {Aigner, Martin and Ziegler, G\"{u}nter M. },
isbn = {3540404600},
publisher = {Springer},
title = {Proofs from THE BOOK},
year = {2003}
}
@book{ScP98,
author = {Uwe Sch\"{o}ning and Randall Pruim},
title = {Gems of Theoretical Computer Science},
year = {1998},
publisher = {Springer-Verlag},
address = {New York, USA}
}
@inproceedings{Holenstein06,
author = {Thomas Holenstein},
title = {Pseudorandom Generators from One-Way Functions: A Simple
Construction for Any Hardness},
booktitle = {TCC},
year = {2006},
pages = {443-461},
ee = {http://dx.doi.org/10.1007/11681878_23},
crossref = {TCC2006},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@proceedings{TCC2006,
editor = {Shai Halevi and
Tal Rabin},
title = {Theory of Cryptography, Third Theory of Cryptography Conference,
TCC 2006, New York, NY, USA, March 4-7, 2006, Proceedings},
booktitle = {TCC},
publisher = {Springer},
series = lncs,
volume = {3876},
year = {2006},
isbn = {3-540-32731-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{She08-survey,
author = {Alexander A. Sherstov},
title = {Communication Lower Bounds Using Dual Polynomials},
journal = {Bulletin of the EATCS},
volume = {95},
pages = {59--93},
year = {2008}
}
@MISC{beame-trinh,
author={Beame, Paul and Huynh-Ngoc, Dang-Trinh},
title = {Multiparty Communication Complexity and Threshold Size of {$AC^0$}},
year={2008},
note = {Manuscript.},
}
@inproceedings{FoG05,
author = {Jeff Ford and
Anna G{\'a}l},
title = {Hadamard Tensors and Lower Bounds on Multiparty Communication
Complexity},
booktitle = {32th } # icalp,
year = {2005},
pages = {1163-1175},
publisher = {Springer}
}
@inproceedings{Pat92,
author = {Ramamohan Paturi},
title = {On the Degree of Polynomials that Approximate Symmetric
{B}oolean Functions},
booktitle = {24th Symposium on
Theory of Computing (STOC)},
year = {1992},
pages = {468-474},
publisher = {ACM}
}
@proceedings{STOC92,
title = {Twenty Fourth ACM Symposium on
Theory of Computing, 4-6 May 1992, Victoria, British Columbia,
Canada},
booktitle = {STOC},
publisher = {ACM},
year = {1992},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{BDPW07,
author = {Paul Beame and
Matei David and
Toniann Pitassi and
Philipp Woelfel},
title = {Separating Deterministic from Nondeterministic NOF Multiparty
Communication Complexity},
booktitle = {34th } # icalp,
year = {2007},
pages = {134-145},
publisher = {Springer}
}
@proceedings{ICALP2007,
editor = {Lars Arge and
Christian Cachin and
Tomasz Jurdzinski and
Andrzej Tarlecki},
title = {Automata, Languages and Programming, 34th Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007,
Proceedings},
booktitle = {ICALP},
publisher = {Springer},
series = lncs,
volume = {4596},
year = {2007},
isbn = {978-3-540-73419-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{BFS86,
author = {L{\'a}szl{\'o} Babai and
Peter Frankl and
Janos Simon},
title = {Complexity classes in communication complexity theory},
booktitle = {27th } # focs,
year = {1986},
pages = {337-347},
publisher = {IEEE}
}
@proceedings{FOCS86,
title = {27th Symposium on Foundations of Computer Science,
27-29 October 1986, Toronto, Ontario, Canada},
booktitle = {FOCS},
year = {1986},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Raz03,
author={Alexander Razborov},
title={Quantum communication complexity of symmetric predicates},
journal={Izvestiya: Mathematics},
volume=67,
number=1,
pages={145-159},
year=2003
}
@misc{ChA08,
author = {Arkadev Chattopadhyay and
Anil Ada},
title = {Multiparty Communication Complexity of Disjointness},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR08-002},
year = {2008},
}
@article{LeeS09,
author = {Troy Lee and Adi Shraibman},
title = {Disjointness is Hard in the Multiparty Number-on-the-Forehead
Model},
journal = compcomp,
volume = {18},
number = {2},
year = {2009},
pages = {309-336},
ee = {http://dx.doi.org/10.1007/s00037-009-0276-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{LeS08,
author = {Troy Lee and
Adi Shraibman},
title = {Disjointness is hard in the multi-party number on the forehead
model},
crossref = {CCC2008}
}
@inproceedings{Chatto07,
author = {Arkadev Chattopadhyay},
title = {Discrepancy and the Power of Bottom Fan-in in Depth-three
Circuits},
pages = {449-458},
booktitle={48th } # focs,
publisher = {IEEE},
year = {2007}
}
@article{BPS07,
author = {Paul Beame and
Toniann Pitassi and
Nathan Segerlind},
title = {Lower Bounds for Lov{\'a}sz--Schrijver Systems and Beyond
Follow from Multiparty Communication Complexity},
journal = {SIAM J. Comput.},
volume = {37},
number = {3},
year = {2007},
pages = {845-869},
ee = {http://dx.doi.org/10.1137/060654645},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{NiS94,
author = {Noam Nisan and Mario Szegedy},
title = {On the Degree of {B}oolean Functions as Real Polynomials},
journal = compcomp,
volume = {4},
year = {1994},
pages = {301-313}
}
@inproceedings{GoG08,
author = {Parikshit Gopalan and Venkatesan Guruswami},
title = {Hardness amplification within {NP} against deterministic algorithms},
crossref = {CCC2008}
}
@inproceedings{IJKW08,
author = {Russell Impagliazzo and Ragesh Jaiswal and Valentine Kabanets and Avi Wigderson},
title = {Uniform Direct-Product Theorems: Simplified, Optimized, and Derandomized},
booktitle={40th ACM } # stoc,
year = {2008}
}
@article {PatrascuTarnita07,
AUTHOR = {P{\v{a}}tra{\c{s}}cu, Mihai and Tarni{\c{t}}{\v{a}}, Corina
E.},
TITLE = {On dynamic bit-probe complexity},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {380},
year = {2007},
NUMBER = {1-2},
PAGES = {127--142},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68Q17 (68Q25)},
MRNUMBER = {MR2330646 (2008h:68046)},
}
@inproceedings{Mitzenmacher01,
author = {Michael Mitzenmacher},
title = {Compressed bloom filters},
booktitle = {20th Symposium on Principles of distributed computing (PODC)},
year = {2001},
pages = {144--150},
publisher = {ACM}
}
@inproceedings{Golynski09,
author = {Alexander Golynski},
title = {Cell probe lower bounds for succinct data structures},
booktitle = {20th } # soda,
year = {2009},
pages = {625-634},
publisher = {ACM-SIAM}
}
@inproceedings{PaghSTOC01,
author = {Rasmus Pagh},
title = {On the cell probe complexity of membership and perfect hashing},
booktitle = {33rd } # stoc,
year = {2001},
pages = {425-432},
publisher = {ACM}
}
@article {Pagh01,
AUTHOR = {Pagh, Rasmus},
TITLE = {Low redundancy in static dictionaries with constant query
time},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {31},
year = {2001},
NUMBER = {2},
PAGES = {353--363 },
ISSN = {0097-5397},
MRCLASS = {68P10 (68P20 68P30)},
MRNUMBER = {MR1861279 (2002h:68039)},
MRREVIEWER = {Erkki M{\"a}kinen},
}
@article{EIRS01,
author = {Jeff Edmonds and
Russell Impagliazzo and
Steven Rudich and
Jiri Sgall},
title = {Communication complexity towards lower bounds on circuit
depth},
journal = compcomp,
volume = {10},
number = {3},
year = {2001},
pages = {210-246},
ee = {http://link.springer.de/link/service/journals/00037/bibs/1010003/10100210.htm},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Szemeredi75,
author = {Endre Szemer{\'e}di},
title = {On sets of integers containing no $k$ elements in arithmetic progression},
journal = {Acta Arithmetica},
volume = {27},
pages = {199--245},
year = {1975}
}
@inproceedings{PPST83,
author = {Wolfgang J. Paul and
Nicholas Pippenger and
Endre Szemer{\'e}di and
William T. Trotter},
title = {On Determinism versus Non-Determinism and Related Problems
(Preliminary Version)},
booktitle = {FOCS},
year = {1983},
pages = {429-438},
crossref = {FOCS1983},
}
@proceedings{FOCS1983,
title = {24th Symposium on Foundations of Computer Science,
7-9 November 1983, Tucson, Arizona, USA},
booktitle = {FOCS},
publisher = {IEEE},
year = {1983}
}
@inproceedings{EtY07,
author = {Kousha Etessami and Mihalis Yannakakis},
title = {On the complexity of Nash equilibria and other fixed points},
crossref = {FOCS2007}
}
@article{ShaltielU06,
author = {Ronen Shaltiel and
Christopher Umans},
title = {Pseudorandomness for Approximate Counting and Sampling},
journal = compcomp,
volume = {15},
number = {4},
year = {2006},
pages = {298-341},
ee = {http://dx.doi.org/10.1007/s00037-007-0218-9},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@MISC{GrT07,
author = {Ben Green and Terence Tao},
title = {The distribution of polynomials over finite fields, with applications to the {G}owers norms},
note = {arXiv:0711.3191v1},
year = {2007}
}
@article {GrT09,
AUTHOR = {Green, Ben and Tao, Terence},
TITLE = {The distribution of polynomials over finite fields, with
applications to the {G}owers norms},
JOURNAL = {Contrib. Discrete Math.},
FJOURNAL = {Contributions to Discrete Mathematics},
VOLUME = {4},
year = {2009},
NUMBER = {2},
PAGES = {1--36},
ISSN = {1715-0868},
MRCLASS = {11B30 (11B75 11K36 11P70)},
MRNUMBER = {2592422},
}
@inproceedings{LMS07,
author = {Shachar Lovett and Roy Meshulam and Alex Samorodnitsky},
title = {Inverse Conjecture for the {G}owers norm is false},
year = {2008},
pages= {547-556},
booktitle={40th } # stoc,
publisher = {ACM}
}
@book{CsK82,
author = {Imre Csiszar and Janos Korner},
title = {Information Theory: Coding Theorems for Discrete Memoryless Systems},
year = {1982},
isbn = {0121984508},
publisher = {Academic Press, Inc.},
}
@inproceedings{LTW07-Weakly,
author = {Chi-Jen Lu and
Shi-Chun Tsai and
Hsin-Lung Wu},
title = {Impossibility Results on Weakly Black-Box Hardness Amplification},
booktitle = {16th Symposium on Fundamentals of Computation Theory (FCT)},
publisher = {Springer},
series = lncs,
volume = {4639},
year = {2007},
pages = {400-411}
}
@proceedings{DBLP:conf/fct/2007,
editor = {Erzs{\'e}bet Csuhaj-Varj{\'u} and
Zolt{\'a}n {\'E}sik},
title = {Fundamentals of Computation Theory, 16th Symposium,
FCT 2007, Budapest, Hungary, August 27-30, 2007, Proceedings},
booktitle = {FCT},
publisher = {Springer},
series = lncs,
volume = {4639},
year = {2007},
isbn = {978-3-540-74239-5},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{LTW07-NP,
author = {Chi-Jen Lu and
Shi-Chun Tsai and
Hsin-Lung Wu},
title = {Improved hardness amplification in {NP}},
journal = {Theor. Comput. Sci.},
volume = {370},
number = {1-3},
year = {2007},
pages = {293-298},
ee = {http://dx.doi.org/10.1016/j.tcs.2006.10.009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{LinTrevisanWee05,
author = {Henry Lin and
Luca Trevisan and
Hoeteck Wee},
title = {On Hardness Amplification of One-Way Functions},
pages = {34-49},
booktitle = {2nd Theory of Cryptography Conference (TCC)},
publisher = {Springer},
series = lncs,
volume = {3378},
year = {2005}
}
@article{BoT06,
author = {Andrej Bogdanov and
Luca Trevisan},
title = {On Worst-Case to Average-Case Reductions for {NP} Problems},
journal = {SIAM J. Comput.},
volume = {36},
number = {4},
year = {2006},
pages = {1119-1159},
ee = {http://dx.doi.org/10.1137/S0097539705446974},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{BoT06-survey,
author = {Andrej Bogdanov and
Luca Trevisan},
title = {Average-Case Complexity},
journal = {Foundations and Trends� in
Theoretical Computer Science},
volume = {2},
number = {1},
year = {2006}
}
@inproceedings{GuK06,
author = {Venkatesan Guruswami and
Valentine Kabanets},
title = {Hardness Amplification Via Space-Efficient Direct Products},
booktitle = {7th Latin American Symposium on Theoretical Informatics (LATIN)},
year = {2006},
pages = {556-568},
ee = {http://dx.doi.org/10.1007/11682462_52}
}
@inproceedings{Tre05,
author = {Luca Trevisan},
title = {On uniform amplification of hardness in {NP}},
booktitle = {37th } # stoc,
publisher = {ACM},
year = {2005},
pages = {31-38}
}
@proceedings{STOC2005,
editor = {Harold N. Gabow and
Ronald Fagin},
title = {37th ACM Symposium on Theory of
Computing, Baltimore, MD, USA, May 22-24, 2005},
booktitle = {STOC},
publisher = {ACM},
year = {2005},
isbn = {1-58113-960-8},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{IJK06,
author = {Russell Impagliazzo and
Ragesh Jaiswal and
Valentine Kabanets},
title = {Approximately List-Decoding Direct Product Codes and Uniform
Hardness Amplification},
booktitle = {47th IEEE Symposium on Foundations of Computer Science
(FOCS)},
year = {2006},
pages = {187-196}
}
@inproceedings{GHKR07,
author = {Shafi Goldwasser and
Dan Gutfreund and
Alexander Healy and
Tali Kaufman and
Guy N. Rothblum},
title = {Verifying and decoding in constant depth},
booktitle = {39th ACM } # stoc,
year = {2007},
pages = {440-449}
}
@inproceedings{LTW07,
author = {Chi-Jen Lu and
Shi-Chun Tsai and
Hsin-Lung Wu},
title = {On the Complexity of Hard-Core Set Constructions},
booktitle = {34th } # icalp,
publisher = {Springer},
series = lncs,
volume = {4596},
year = {2007},
pages = {183-194}
}
@article{CanettiEvenGoldreich95,
author = "Ran Canetti and Guy Even and Oded Goldreich",
title = "Lower Bounds for Sampling Algorithms for Estimating the Average",
journal = ipl,
volume = "53",
number = "1",
pages = "17-25",
year = "1995",
url = "citeseer.ist.psu.edu/canetti94lower.html" }
@article {BIW06,
AUTHOR = {Barak, Boaz and Impagliazzo, Russell and Wigderson, Avi},
TITLE = {Extracting randomness using few independent sources},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {36},
year = {2006},
NUMBER = {4},
PAGES = {1095--1118},
ISSN = {0097-5397},
MRCLASS = {68Q10 (05C55 68W20)},
MRNUMBER = {MR2272272},
MRREVIEWER = {Heng Liang},
}
@article{BaS94,
AUTHOR = {Balog, Antal and Szemer{\' e}di, Endre},
TITLE = {A statistical theorem of set addition},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal on Combinatorics and
the Theory of Computing},
VOLUME = {14},
year = {1994},
NUMBER = {3},
PAGES = {263--268},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {11B25 (11B75)},
MRNUMBER = {MR1305895 (95m:11019)},
MRREVIEWER = {Anne Ludington Young}
}
@book {Fre73,
AUTHOR = {Fre{\u\i}man, Gregory},
TITLE = {Foundations of a structural theory of set addition},
NOTE = {Translated from the Russian,
Translations of Mathematical Monographs, Vol 37},
PUBLISHER = {American Mathematical Society},
year = {1973},
PAGES = {vii+108},
MRCLASS = {10J99 (10AXX)},
MRNUMBER = {MR0360496 (50 \#12944)},
}
@article{GreenT09-FreimanviaExtremal,
author = {Ben Green and Terence Tao},
title = {Freiman's theorem in finite fields via extremal set theory},
journal = {Combinatorics, Probability and Computing},
volulme = {18},
year = {2009},
number = {3},
pages = {335--355}
}
@article{GreenT09-ANote,
author = {Ben Green and Terence Tao},
title = {A note on the {F}reiman and {B}alog-{S}zemer�di-{G}owers theorems in finite fields},
journal = {J. Aust. Math. Soc.},
volume = {86},
year = {2009},
number = {1},
pages = {61--74}
}
@article{Lov09,
author = {Shachar Lovett},
title = {Unconditional Pseudorandom Generators for Low Degree Polynomials},
journal = {Theory of Computing},
year = {2009},
pages = {69-82},
publisher = {Theory of Computing},
doi = {10.4086/toc.2009.v005a003},
volume = {5},
number = {1},
URL = {http://www.theoryofcomputing.org/articles/v005a003},
eprint = {toc:v005/a003}
}
@inproceedings{Lov07,
author = {Shachar Lovett},
title = {Unconditional pseudorandom generators for low degree polynomials},
pages={557-562},
year = {2008},
booktitle={40th } # stoc,
publisher = {ACM}
}
@MISC{Gre04-finite,
author = {Ben Green},
title = {Finite field models in additive combinatorics},
note = {Surveys in Combinatorics, London Math. Soc. Lecture Notes 327, 1-27},
year = {2005}
}
@inproceedings{BRW08,
author = {Avraham Ben-Aroya and
Oded Regev and
Ronald de Wolf},
title = {A Hypercontractive Inequality for Matrix-Valued Functions
with Applications to Quantum Computing and {LDC}s},
booktitle = {49th IEEE } # focs,
year = {2008},
publisher = {IEEE Computer Society},
pages = {477-486}
}
@book {TaV06,
AUTHOR = {Tao, Terence and Vu, Van},
TITLE = {Additive combinatorics},
SERIES = {Cambridge Studies in Advanced Mathematics},
VOLUME = {105},
PUBLISHER = {Cambridge University Press},
year = {2006},
PAGES = {xviii+512},
ISBN = {978-0-521-85386-6; 0-521-85386-9},
MRCLASS = {11-02 (05-02 11P70 11P82 28D05 37A45)},
MRNUMBER = {MR2289012},
}
@article {Ruz99,
AUTHOR = {Ruzsa, Imre Z.},
TITLE = {An analog of {F}reiman's theorem in groups},
JOURNAL = {Ast\'erisque},
FJOURNAL = {Ast\'erisque},
NUMBER = {258},
year = {1999},
PAGES = {xv, 323--326},
ISSN = {0303-1179},
MRCLASS = {11P70 (11B25 11B75)},
MRNUMBER = {MR1701207 (2000h:11111)},
MRREVIEWER = {Norbert Hegyv{\'a}ri},
}
@article {KoS03,
AUTHOR = {Kostochka, Alexandr and Sudakov, Benny},
TITLE = {On {R}amsey numbers of sparse graphs},
JOURNAL = {Combinatorics, Probability and Computing},
VOLUME = {12},
year = {2003},
NUMBER = {5-6},
PAGES = {627--641},
ISSN = {0963-5483},
MRCLASS = {05C55},
MRNUMBER = {MR2037075 (2004m:05177)},
MRREVIEWER = {R. H. Schelp},
}
@article {SSV05,
AUTHOR = {Sudakov, Benny and Szemer{\'e}di, Endre and Vu, Van},
TITLE = {On a question of {E}rd{\H o}s and {M}oser},
JOURNAL = {Duke Math. J.},
FJOURNAL = {Duke Mathematical Journal},
VOLUME = {129},
year = {2005},
NUMBER = {1},
PAGES = {129--155},
ISSN = {0012-7094},
CODEN = {DUMJAO},
MRCLASS = {11P70 (05D05 11B75)},
MRNUMBER = {MR2155059 (2006c:11118)},
MRREVIEWER = {Mei Chu Chang},
}
@article {JoP83,
AUTHOR = {Joag-Dev, Kumar and Proschan, Frank},
TITLE = {Negative association of random variables, with applications},
JOURNAL = {Ann. Statist.},
FJOURNAL = {The Annals of Statistics},
VOLUME = {11},
year = {1983},
NUMBER = {1},
PAGES = {286--295},
ISSN = {0090-5364},
CODEN = {ASTSC7},
MRCLASS = {62H05 (62H20)},
MRNUMBER = {MR684886 (85d:62058)},
MRREVIEWER = {C. G. Khatri},
}
@inproceedings {Bog05,
AUTHOR = {Bogdanov, Andrej},
TITLE = {Pseudorandom generators for low degree polynomials},
BOOKTITLE = {37th Symposium on
Theory of Computing (STOC)},
PAGES = {21--30},
PUBLISHER = {ACM},
year = {2005},
MRCLASS = {68Q25 (68R05 68W20)},
MRNUMBER = {MR2181598 (2006g:68103)},
}
@article{ABNNR92,
author = {Noga Alon and
Jehoshua Bruck and
Joseph Naor and
Moni Naor and
Ron M. Roth},
title = {Construction of asymptotically good low-rate error-correcting
codes through pseudo-random graphs.},
journal = {IEEE Transactions on Information Theory},
volume = {38},
number = {2},
year = {1992},
pages = {509--516},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{BSVW03,
AUTHOR = {Ben-Sasson, Eli and Sudan, Madhu and Vadhan, Salil and
Wigderson, Avi},
TITLE = {Randomness-efficient low degree tests and short {PCP}s via
epsilon-biased sets},
BOOKTITLE = {35th Symposium on Theory
of Computing (STOC)},
PAGES = {612--621},
publisher = {ACM},
year = {2003}
}
@inproceedings{NiB97,
AUTHOR = {Nisan, Noam and Bar-Yossef, Ziv},
TITLE = {Pointer jumping requires concurrent read},
booktitle = {29th ACM } # stoc,
PAGES = {549--558},
year={1997}
}
@article {BIP98,
AUTHOR = {Beame, Paul and Impagliazzo, Russell and Pitassi, Toniann},
TITLE = {Improved depth lower bounds for small distance connectivity},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {7},
year = {1998},
NUMBER = {4},
PAGES = {325--345},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q17 (68Q15 68Q25)},
MRNUMBER = {MR1691495 (2000k:68061)},
MRREVIEWER = {Frederic Green},
}
@inproceedings{AUY83,
author = {Alfred V. Aho and Jeffrey D. Ullman and Mihalis Yannakakis},
title = {On notions of information transfer in VLSI circuits},
booktitle = {15th ACM } # stoc,
year = {1983},
pages = {133--139},
publisher = {ACM Press}
}
@article {AlM88,
AUTHOR = {Alon, Noga and Maass, Wolfgang},
TITLE = {Meanders and their applications in lower bounds arguments},
NOTE = {Twenty-Seventh IEEE Symposium on the Foundations of
Computer Science (Toronto, ON, 1986)},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {37},
year = {1988},
NUMBER = {2},
PAGES = {118--129},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (11B83 11Y55)},
MRNUMBER = {MR979114 (90h:68047)},
}
@article {AWYU82,
AUTHOR = {Aho, A. V. and Wyner, A. D. and Yannakakis, M. and Ullman, J.
D.},
TITLE = {Bounds on the size and transmission rate of communications
protocols},
JOURNAL = {Comput. Math. Appl.},
FJOURNAL = {Computers \& Mathematics with Applications. An Journal},
VOLUME = {8},
year = {1982},
NUMBER = {3},
PAGES = {205--214},
ISSN = {0097-4943},
CODEN = {CMAPDK},
MRCLASS = {68D35 (94A40)},
MRNUMBER = {MR662583 (83i:68091)},
}
@article {PaS84,
AUTHOR = {Papadimitriou, Christos H. and Sipser, Michael},
TITLE = {Communication complexity},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {28},
year = {1984},
NUMBER = {2},
PAGES = {260--269},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (68Q30)},
MRNUMBER = {MR760547 (86h:68061)},
MRREVIEWER = {Joseph Ja'Ja'},
}
@article {KNR99,
AUTHOR = {Kremer, Ilan and Nisan, Noam and Ron, Dana},
TITLE = {Errata for: ``{O}n randomized one-round communication
complexity'' [{C}omput. {C}omplexity {\bf 8} (1999), no. 1,
21--49; {MR}1700215 (2000c:68070)]},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {10},
year = {2001},
NUMBER = {4},
PAGES = {314--315},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q25 (60A10 68Q15 68Q32)},
MRNUMBER = {MR1978069 (2004d:68057)},
}
@article {AMS99,
AUTHOR = {Alon, Noga and Matias, Yossi and Szegedy, Mario},
TITLE = {The space complexity of approximating the frequency moments},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {58},
year = {1999},
NUMBER = {1, part 2},
PAGES = {137--147},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q25 (68W20)},
MRNUMBER = {MR1688610 (2000h:68087)},
MRREVIEWER = {Hsien-Kuei Hwang},
}
@article {BJKS04,
AUTHOR = {Bar-Yossef, Ziv and Jayram, T. S. and Kumar, Ravi and
Sivakumar, D.},
TITLE = {An information statistics approach to data stream and
communication complexity},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {68},
year = {2004},
NUMBER = {4},
PAGES = {702--732},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (62B10 68Q17 94A15)},
MRNUMBER = {MR2059642 (2005b:68099)},
MRREVIEWER = {Ulrich Tamm},
}
@inproceedings{She08,
author = {Alexander A. Sherstov},
title = {The Pattern Matrix Method for Lower Bounds on Quantum Communication},
year = {2008},
booktitle={40th } # stoc,
pages = {85-94},
publisher = {ACM}
}
@article{She07,
author = {Alexander A. Sherstov},
title = {Separating {AC}$^0$ from Depth-$2$ Majority Circuits},
journal = {SIAM J. Comput.},
volume = {38},
number = {6},
year = {2009},
pages = {2113-2129}
}
@article {NiW93,
AUTHOR = {Nisan, Noam and Wigderson, Avi},
TITLE = {Rounds in communication complexity revisited},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {22},
year = {1993},
NUMBER = {1},
PAGES = {211--219},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {68Q25 (94A05 94A17)},
MRNUMBER = {MR1202870 (94c:68093)},
}
@inproceedings{BPSW05,
author = {Paul Beame and
Toniann Pitassi and
Nathan Segerlind and
Avi Wigderson},
title = {A Direct Sum Theorem for Corruption and the Multiparty NOF
Communication Complexity of Set Disjointness},
pages = {52-66},
booktitle = {20th } # ccc,
year = {2005},
organization = {IEEE}
}
@incollection {BPS05,
AUTHOR = {Beame, Paul and Pitassi, Toniann and Segerlind, Nathan},
TITLE = {Lower bounds for {L}ov\'asz-{S}chrijver systems and beyond
follow from multiparty communication complexity},
BOOKTITLE = {Automata, languages and programming},
SERIES = {Lecture Notes in Comput. Sci.},
VOLUME = {3580},
PAGES = {1176--1188},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
year = {2005},
MRCLASS = {90B18 (03F20 68Q15)},
MRNUMBER = {MR2184710 (2006g:90013)},
}
@inproceedings{BrodyC08,
author = {Joshua Brody and
Amit Chakrabarti},
title = {Sublinear Communication Protocols for Multi-Party Pointer
Jumping and a Related Lower Bound},
booktitle = {25th } # stacs,
year = {2008},
pages = {145-156}
}
@proceedings{STACS2008,
editor = {Susanne Albers and
Pascal Weil},
title = {STACS 2008, 25th Symposium on Theoretical Aspects
of Computer Science, Bordeaux, France, February 21-23, 2008,
Proceedings},
booktitle = {STACS},
publisher = {Internationales Begegnungs- und Forschungszentrum fuer Informatik
(IBFI), Schloss Dagstuhl, Germany},
series = {Dagstuhl Seminar Proceedings},
volume = {08001},
year = {2008},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article {PRS97,
AUTHOR = {Pudl{\'a}k, Pavel and R{\"o}dl, Vojt{\v{e}}ch and Sgall,
Ji{\v{r}}{\'{\i}}},
TITLE = {{B}oolean circuits, tensor ranks, and communication complexity},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {26},
year = {1997},
NUMBER = {3},
PAGES = {605--633},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {68Q15 (68Q25 68R10)},
MRNUMBER = {MR1448624 (98h:68093)},
MRREVIEWER = {Frederic Green},
}
@book{Jukna2012,
author = {Jukna, Stasys},
title = {Boolean Function Complexity: Advances and Frontiers},
year = {2012},
note = {Available from the author's webpage}
}
@article {DJS98,
AUTHOR = {Damm, Carsten and Jukna, Stasys and Sgall, Ji{\v{r}}{\'{\i}}},
TITLE = {Some bounds on multiparty communication complexity of pointer
jumping},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {7},
year = {1998},
NUMBER = {2},
PAGES = {109--127},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q15 (68Q25)},
MRNUMBER = {MR1652807 (99h:68053)},
}
@inproceedings{Chakrabarti07,
author = {Amit Chakrabarti},
title = {Lower Bounds for Multi-Player Pointer Jumping},
crossref = {CCC07}
}
@article{BeL00,
author = {Claudia Bertram-Kretzberg and
Hanno Lefmann},
title = {MOD$_{\mbox{p}}$-tests, almost independence and small probability
spaces.},
journal = {Random Struct. Algorithms},
volume = {16},
number = {4},
year = {2000},
pages = {293-313},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book {LiN97,
AUTHOR = {Lidl, Rudolf and Niederreiter, Harald},
TITLE = {Finite fields},
SERIES = {Encyclopedia of Mathematics and its Applications},
VOLUME = {20},
EDITION = {Second},
PUBLISHER = {Cambridge University Press},
year = {1997}
}
@article {BabaiHayesKimmel01,
AUTHOR = {Babai, L{\'a}szl{\'o} and Hayes, Thomas P. and Kimmel, Peter
G.},
TITLE = {The cost of the missing bit: communication complexity with
help},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal on Combinatorics and
the Theory of Computing},
VOLUME = {21},
year = {2001},
NUMBER = {4},
PAGES = {455--488},
ISSN = {0209-9683},
MRCLASS = {68Q05 (03D15 11K38 68Q15 68R05 94A15)},
MRNUMBER = {MR1863574 (2002i:68039)},
MRREVIEWER = {Ulrich Tamm},
}
@article {Grolmusz95,
AUTHOR = {Grolmusz, Vince},
TITLE = {Separating the communication complexities of {${\rm MOD}\,m$}
and {${\rm MOD}\,p$} circuits},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {51},
year = {1995},
NUMBER = {2},
PAGES = {307--313},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (68Q10)},
MRNUMBER = {MR1356509 (97b:68068)},
MRREVIEWER = {A. D. Korshunov},
}
@article {Hoe63,
AUTHOR = {Hoeffding, Wassily},
TITLE = {Probability inequalities for sums of bounded random variables},
JOURNAL = {J. Amer. Statist. Assoc.},
FJOURNAL = {Journal of the American Statistical Association},
VOLUME = {58},
year = {1963},
PAGES = {13--30},
ISSN = {0162-1459},
MRCLASS = {60.20},
MRNUMBER = {MR0144363 (26 \#1908)},
MRREVIEWER = {E. H. Lehman, Jr.},
}
@article {DubhashiRa98,
AUTHOR = {Dubhashi, Devdatt and Ranjan, Desh},
TITLE = {Balls and bins: a study in negative dependence},
JOURNAL = {Random Structures Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {13},
year = {1998},
NUMBER = {2},
PAGES = {99--124},
ISSN = {1042-9832},
MRCLASS = {60E99 (68Q25)},
MRNUMBER = {MR1642566 (99k:60048)},
MRREVIEWER = {Colin J. H. McDiarmid},
}
@book{DuP05,
AUTHOR = {Dubhashi, Devdatt and Panconesi, Alessandro},
TITLE = {Concentration of measure for the analysis of randomized
algorithms},
PUBLISHER = {Cambridge University Press},
year = {2009},
PAGES = {xvi+196},
ISBN = {978-0-521-88427-3},
MRCLASS = {68W20 (60C05 60F10 68-02 68W40)},
MRNUMBER = {MR2547432},
}
@article{Reingold08,
author = {Omer Reingold},
title = {Undirected connectivity in log-space},
journal = {J. ACM},
volume = {55},
number = {4},
year = {2008},
ee = {http://doi.acm.org/10.1145/1391289.1391291},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings {Rei05,
AUTHOR = {Reingold, Omer},
TITLE = {Undirected {ST}-connectivity in log-space},
BOOKTITLE = {37th } # stoc,
PAGES = {376--385},
PUBLISHER = {ACM},
year = {2005}
}
@techreport{Fei95,
author = {U. Feige},
title = {Error reduction by parallel repetition-the state of the art},
year = {1995},
publisher = {Weizmann Science Press of Israel},
address = {Jerusalem, Israel, Israel},
}
@incollection {Holenstein07,
AUTHOR = {Holenstein, Thomas},
TITLE = {Parallel repetition: simplifications and the no-signaling case},
BOOKTITLE = {39th {S}ymposium on {T}heory of {C}omputing (STOC)},
PAGES = {411--419},
PUBLISHER = {ACM},
year = {2007}
}
@article {Raz98,
AUTHOR = {Raz, Ran},
TITLE = {A parallel repetition theorem},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {27},
year = {1998},
NUMBER = {3},
PAGES = {763--803},
ISSN = {0097-5397},
MRCLASS = {68Q15 (68Q25)},
MRNUMBER = {MR1612640 (2000c:68057)},
}
@article {NRS99,
AUTHOR = {Nisan, Noam and Rudich, Steven and Saks, Michael},
TITLE = {Products and help bits in decision trees},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {28},
year = {1999},
NUMBER = {3},
PAGES = {1035--1050},
ISSN = {0097-5397},
MRCLASS = {68Q25 (68Q05 68Q99)},
MRNUMBER = {MR1670070 (99m:68089)},
}
@inproceedings{CFL83,
author = {Ashok K. Chandra and Merrick L. Furst and Richard J. Lipton},
title = {Multi-party protocols},
booktitle = {15th } # stoc,
publisher = {ACM},
pages = {94-99},
year = {1983},
}
@inproceedings{Yao79,
author = {Andrew Chi-Chih Yao},
title = {Some complexity questions related to distributive computing},
booktitle = {11th ACM } # stoc,
year = {1979},
pages = {209--213},
publisher = {ACM Press}
}
@MISC{Razborov02-03,
author = {Alexander Razborov},
title = {Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution},
year = {2002-2003},
note = {Manuscript. Available from http://www.mi.ras.ru/$\sim$razborov/}
}
@article {Chu90,
AUTHOR = {Chung, Fan R. K.},
TITLE = {Quasi-random classes of hypergraphs},
JOURNAL = {Random Structures Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {1},
year = {1990},
NUMBER = {4},
PAGES = {363--382},
ISSN = {1042-9832},
MRCLASS = {05C65 (05C80)},
MRNUMBER = {MR1138430 (93b:05126)},
MRREVIEWER = {A. G. Thomason},
}
@article{Raz00,
AUTHOR = {Raz, Ran},
TITLE = {The {BNS}-{C}hung criterion for multi-party communication
complexity},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {9},
year = {2000},
NUMBER = {2},
PAGES = {113--122},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q17},
MRNUMBER = {MR1809687 (2002a:68048)},
MRREVIEWER = {Ulrich Tamm},
}
@article{Sha03,
AUTHOR = {Shaltiel, Ronen},
TITLE = {Towards proving strong direct product theorems},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {12},
year = {2003},
NUMBER = {1-2},
PAGES = {1--22},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q17 (68Q15)},
MRNUMBER = {MR2054892 (2005a:68091)},
MRREVIEWER = {Yongge Wang},
}
@incollection{PRW97,
AUTHOR = {Parnafes, Itzhak and Raz, Ran and Wigderson, Avi},
TITLE = {Direct product results and the {GCD} problem, in old and new
communication models},
BOOKTITLE = {STOC '97 (El Paso, TX)},
PAGES = {363--372},
PUBLISHER = {ACM},
ADDRESS = {New York},
year = {1999},
MRCLASS = {68Q25 (68Q10)},
MRNUMBER = {MR1715645},
}
@Misc{Han06,
author = {Kristoffer Arnsfelt Hansen},
title = {Lower Bounds for Circuits with Few Modular Gates using Exponential Sums},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR06-079},
year = {2006},
note = {www.eccc.uni-trier.de/}
}
@Misc{Cha06,
author = {Arkadev Chattopadhyay},
title = {An improved bound on correlation between polynomials over ${Z}_m$ and $MOD_q$},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR06-107},
year = {2006}
}
@inproceedings{AlB01,
author = {Noga Alon and Richard Beigel},
title = {Lower bounds for approximations by low degree polynomials over ${Z}_m$},
pages = {184-187},
crossref = {CCC01}
}
@article {Gre04,
AUTHOR = {Green, Frederic},
TITLE = {The correlation between parity and quadratic polynomials mod
3},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {69},
year = {2004},
NUMBER = {1},
PAGES = {28--44},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (68Q17)},
MRNUMBER = {MR2070798 (2005e:68064)},
MRREVIEWER = {Bruce Edward Litow},
}
@article{Healy08,
author = {Healy, Alexander},
journal = compcomp,
month = {April},
number = {1},
pages = {3--37},
title = {Randomness-Efficient Sampling within ${NC}^1$},
url = {http://dx.doi.org/10.1007/s00037-007-0238-5},
volume = {17},
year = {2008}
}
@inproceedings{Sam07,
author = {Alex Samorodnitsky},
title = {Low-degree tests at large distances},
booktitle = "{39th } # stoc",
year = "2007",
pages = {506-515},
publisher = {ACM}
}
@inproceedings{SmT06,
author = {Alex Samorodnitsky and Luca Trevisan},
title = {{Gowers} uniformity, influence of variables, and {PCP}s},
pages = {11-20},
booktitle = {38th } # stoc,
year = {2006},
publisher = {ACM}
}
@Proceedings{STOC2007,
booktitle = "{39th ACM Symposium
on Theory of Computing, San Diego, CA USA}",
title = "{39th ACM Symposium
on Theory of Computing, San Diego, CA USA}",
year = "2007"
}
@article {Gow01,
AUTHOR = {Timothy Gowers},
TITLE = {A new proof of {S}zemer\'edi's theorem},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {11},
year = {2001},
NUMBER = {3},
PAGES = {465--588},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {11B25 (11K38 11K45)},
MRNUMBER = {MR1844079 (2002k:11014)},
MRREVIEWER = {Hillel Furstenberg},
}
@article {Gow98,
AUTHOR = {Timothy Gowers},
TITLE = {A new proof of {S}zemer\'edi's theorem for arithmetic
progressions of length four},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {8},
year = {1998},
NUMBER = {3},
PAGES = {529--551},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {11B25 (11N13)},
MRNUMBER = {MR1631259 (2000d:11019)},
MRREVIEWER = {D. R. Heath-Brown},
}
@article {ChT93,
AUTHOR = {Chung, Fan R. K. and Tetali, Prasad},
TITLE = {Communication complexity and quasi randomness},
JOURNAL = {SIAM J. Discrete Math.},
FJOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {6},
year = {1993},
NUMBER = {1},
PAGES = {110--123},
ISSN = {0895-4801},
CODEN = {SJDMEC},
MRCLASS = {05D05 (05C65 68M10 68Q30)},
MRNUMBER = {MR1201994 (93k:05181)},
}
@article{JPRZ04,
author = {Charanjit S. Jutla and Anindya C. Patthak and Atri Rudra and David Zuckerman},
title = {Testing Low-Degree Polynomials over Prime Fields},
journal = {focs},
volume = {00},
year = {2004},
issn = {0272-5428},
pages = {423-432},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2004.64},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
@incollection{AKKLR03,
AUTHOR = {Alon, Noga and Kaufman, Tali and Krivelevich, Michael and
Litsyn, Simon and Ron, Dana},
TITLE = {Testing low-degree polynomials over {${\rm GF}(2)$}},
BOOKTITLE = {7th Workshop on
Randomization and Approximation Techniques in Computer Science (RANDOM)},
SERIES = lncs,
VOLUME = {2764},
PAGES = {188--199},
PUBLISHER = {Springer},
year = {2003}
}
@article{GrT08,
author = {Green,Ben and Tao,Terence},
title = {An inverse theorem for the {G}owers ${U}^3({G})$ norm},
journal = {Edinburgh Mathematical Society (Series 2)},
volume = {51},
number = {01},
pages = {73-153},
year = {2008}
}
@article {Bou05,
AUTHOR = {Bourgain, Jean},
TITLE = {Estimation of certain exponential sums arising in complexity
theory},
JOURNAL = {C. R. Math. Acad. Sci. Paris},
FJOURNAL = {Comptes Rendus Math\'ematique. Acad\'emie des Sciences. Paris},
VOLUME = {340},
year = {2005},
NUMBER = {9},
PAGES = {627--631},
ISSN = {1631-073X},
MRCLASS = {11L07 (68Q15 94C10)},
MRNUMBER = {MR2139268 (2006a:11104)},
MRREVIEWER = {Serge{\u\i} V. Konyagin},
}
@article {GRS05,
AUTHOR = {Green, Frederic and Roy, Amitabha and Straubing, Howard},
TITLE = {Bounds on an exponential sum arising in {B}oolean circuit
complexity},
JOURNAL = {C. R. Math. Acad. Sci. Paris},
FJOURNAL = {Comptes Rendus Math\'ematique. Acad\'emie des Sciences. Paris},
VOLUME = {341},
year = {2005},
NUMBER = {5},
PAGES = {279--282},
ISSN = {1631-073X},
MRCLASS = {11L07 (68Q15)},
MRNUMBER = {MR2166139 (2006e:11117)},
MRREVIEWER = {Serge{\u\i} V. Konyagin},
}
@article {ChS98,
AUTHOR = {Berg, Christer and Ulfberg, Staffan},
TITLE = {A lower bound for perceptrons and an oracle separation of the
{$\rm PP\sp {PH}$} hierarchy},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {56},
year = {1998},
NUMBER = {3},
PAGES = {263--271},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (68Q17)},
MRNUMBER = {MR1633969 (2000d:68049)},
MRREVIEWER = {Frederic Green},
}
@incollection{Raz95,
AUTHOR = {Razborov, Alexander},
TITLE = {Bounded arithmetic and lower bounds in {B}oolean complexity},
BOOKTITLE = {Feasible mathematics, II (Ithaca, NY, 1992)},
SERIES = {Progr. Comput. Sci. Appl. Logic},
VOLUME = {13},
PAGES = {344--386},
PUBLISHER = {Birkh\"auser Boston},
ADDRESS = {Boston, MA},
year = {1995},
MRCLASS = {03D15 (03F30 06E30 68Q15)},
MRNUMBER = {MR1322282 (96d:03057)},
MRREVIEWER = {Shih Ping Tung},
}
@article {AlH94,
AUTHOR = {Allender, Eric and Hertrampf, Ulrich},
TITLE = {Depth reduction for circuits of unbounded fan-in},
JOURNAL = {Inform. and Comput.},
FJOURNAL = {Information and Computation},
VOLUME = {112},
year = {1994},
NUMBER = {2},
PAGES = {217--238},
ISSN = {0890-5401},
MRCLASS = {68Q15},
MRNUMBER = {MR1280582 (95m:68050)},
MRREVIEWER = {A. D. Korshunov},
}
@article {Che52,
AUTHOR = {Chernoff, Herman},
TITLE = {A measure of asymptotic efficiency for tests of a hypothesis
based on the sum of observations},
JOURNAL = {Ann. Math. Statistics},
VOLUME = {23},
year = {1952},
PAGES = {493--507},
MRCLASS = {62.0X},
MRNUMBER = {MR0057518 (15,241c)},
MRREVIEWER = {H. Teicher},
}
@incollection {Tre04,
AUTHOR = {Trevisan, Luca},
TITLE = {Some applications of coding theory in computational
complexity},
BOOKTITLE = {Complexity of computations and proofs},
SERIES = {Quad. Mat.},
VOLUME = {13},
PAGES = {347--424},
PUBLISHER = {Dept. Math., Seconda Univ. Napoli, Caserta},
year = {2004},
MRCLASS = {68Q15 (68Q17 94A24 94B99)},
MRNUMBER = {MR2131413 (2005k:68071)},
MRREVIEWER = {Ulrich Tamm},
}
@article {SaV03,
AUTHOR = {Sahai, Amit and Vadhan, Salil},
TITLE = {A complete problem for statistical zero knowledge},
JOURNAL = jacm,
FJOURNAL = jacm,
VOLUME = {50},
year = {2003},
NUMBER = {2},
PAGES = {196--249},
ISSN = {0004-5411},
MRCLASS = {68Q15 (68Q17)},
MRNUMBER = {MR2147529 (2005m:68082)},
}
@article {BGS75,
AUTHOR = {Baker, Theodore and Gill, John and Solovay, Robert},
TITLE = {Relativizations of the {{\em P}=?{\em N}{\em P}} question},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {4},
year = {1975},
NUMBER = {4},
PAGES = {431--442},
ISSN = {1095-7111},
MRCLASS = {68A20},
MRNUMBER = {MR0395311 (52 \#16108)},
MRREVIEWER = {Ronald V. Book},
}
@INPROCEEDINGS{Imp95-survey,
AUTHOR = "Russell Impagliazzo",
TITLE = "A Personal View of Average-Case Complexity",
BOOKTITLE = "10th Structure in Complexity Theory Conference",
year = "1995",
pages = "134--147",
OPTc-address = "Minneapolis, Minnesota",
OPTmonth = "19--22 June",
organization = "IEEE"
}
@MISC{For03,
author = "Lance Fortnow",
title = "Balanced {NP} sets",
howpublished = "{\it Computational Complexity Weblog}",
year = "2003",
OPTmonth = "12 September",
note = "\verb|http://weblog.fortnow.com/archive/2003_09_07_archive.html|"
}
@inproceedings{LTW05,
author = {Chi-Jen Lu and Shi-Chun Tsai and Hsin-Lung Wu},
title = {On the Complexity of Hardness Amplification},
pages = {170-182},
booktitle = {20th } # ccc,
year = {2005},
organization = {IEEE}
}
@book{KuN97,
AUTHOR = {Kushilevitz, Eyal and Nisan, Noam},
TITLE = {Communication complexity},
PUBLISHER = {Cambridge University Press},
year = {1997},
PAGES = {xiv+189},
ISBN = {0-521-56067-5},
MRCLASS = {68Q15 (68-02 68Q10 68Q25 94C10)},
MRNUMBER = {MR1426129 (98c:68074)},
MRREVIEWER = {Juraj Hromkovi{\v{c}}},
}
@book{CLRS01,
AUTHOR = {Cormen, Thomas H. and Leiserson, Charles E. and Rivest, Ronald
L. and Stein, Clifford},
TITLE = {Introduction to algorithms},
EDITION = {Second},
PUBLISHER = {MIT Press},
ADDRESS = {Cambridge, MA},
year = {2001},
PAGES = {xxii+1180},
ISBN = {0-262-03293-7},
MRCLASS = {68-01 (05-01 05C85 68P05 68P10 68Q25 68Wxx)},
MRNUMBER = {MR1848805 (2002e:68001)},
}
@article {Mar73,
AUTHOR = {G. A. Margulis},
TITLE = {Explicit construction of concentrators},
JOURNAL = {Problems Inform. Transmission},
VOLUME = {9},
year = {1973},
PAGES = {325--332},
}
@article {ESY84,
AUTHOR = {Even, Shimon and Selman, Alan L. and Yacobi, Yacov},
TITLE = {The complexity of promise problems with applications to
public-key cryptography},
JOURNAL = {Inform. and Control},
FJOURNAL = {Information and Control},
VOLUME = {61},
year = {1984},
NUMBER = {2},
PAGES = {159--173},
ISSN = {0019-9958},
CODEN = {IFCNA4},
MRCLASS = {94A60 (68P25)},
MRNUMBER = {MR772678 (86e:94018)},
MRREVIEWER = {Evangelos Kranakis},
}
@article {Gil98,
AUTHOR = {Gillman, David},
TITLE = {A {C}hernoff bound for random walks on expander graphs},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {27},
year = {1998},
NUMBER = {4},
PAGES = {1203--1220},
ISSN = {0097-5397},
MRCLASS = {60F10 (60J10 68Q25)},
MRNUMBER = {MR1621958 (99e:60076)},
MRREVIEWER = {Mark R. Jerrum},
}
@article {JiM87,
AUTHOR = {Jimbo, S. and Maruoka, A.},
TITLE = {Expanders obtained from affine transformations},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal of the J\'anos Bolyai
Mathematical Society},
VOLUME = {7},
year = {1987},
NUMBER = {4},
PAGES = {343--355},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {68R10 (05C99)},
MRNUMBER = {89d:68071},
MRREVIEWER = {Mirko K{\v{r}}iv{\'a}nek},
}
@article {GG81,
AUTHOR = {O. Gabber and Z. Galil},
TITLE = {Explicit constructions of linear size superconcentrators},
JOURNAL = {Journal of Computer and System Sciences},
VOLUME = {22},
year = {1981},
PAGES = {407--420},
}
% BPvsE papers
@inproceedings{ChR96,
author = {Shiva Chaudhuri and
Jaikumar Radhakrishnan},
title = {Deterministic Restrictions in Circuit Complexity},
booktitle = {28th } # stoc,
year = 1996,
pages = {30-36}
}
@article {Kah95,
AUTHOR = {Kahale, Nabil},
TITLE = {Eigenvalues and expansion of regular graphs},
JOURNAL = {J. Assoc. Comput. Mach.},
FJOURNAL = {Journal of the Association for Computing Machinery},
VOLUME = {42},
year = {1995},
NUMBER = {5},
PAGES = {1091--1106},
ISSN = {0004-5411},
CODEN = {JACOAH},
MRCLASS = {68R10 (05C50 68Q25)},
MRNUMBER = {MR1412045 (97f:68149)},
}
@Misc{AHMcCPS05,
author = {Eric Allender and Lisa Hellerstein and Paul McCabe and Toniann Pitassi and Michael Saks},
title = {Minimizing DNF Formulas and AC0 Circuits Given a Truth Table},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR05-126, },
year = {2005}
}
@Misc{Zuc05,
author = {David Zuckerman},
title = {Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR05-100},
month = {September},
year = {2005}
}
@article {MaS87,
AUTHOR = {Maass, Wolfgang and Schorr, Amir},
TITLE = {Speed-up of {T}uring machines with one work tape and a two-way
input tape},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {16},
year = {1987},
NUMBER = {1},
PAGES = {195--202},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {68Q05 (03D10 03D15 68Q15)},
MRNUMBER = {MR873261 (88b:68043)},
MRREVIEWER = {G. Wechsung},
}
@article {SaV08,
AUTHOR = {Sanghvi, Saurabh and Vadhan, Salil},
TITLE = {The round complexity of two-party random selection},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {38},
year = {2008},
NUMBER = {2},
PAGES = {523--550},
ISSN = {0097-5397},
MRCLASS = {68Q10 (68Q85 68W15)},
MRNUMBER = {MR2411034},
}
@inproceedings{SaV05,
author = {Saurabh Sanghvi and Salil Vadhan},
title = {The round complexity of two-party random selection},
booktitle = {37th } # stoc,
publisher = {ACM},
year = {2005},
pages = {338--347}
}
@article {RuS98,
AUTHOR = {Russell, Alexander and Sundaram, Ravi},
TITLE = {Symmetric alternation captures {BPP}},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {7},
year = {1998},
NUMBER = {2},
PAGES = {152--162},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q15},
MRNUMBER = {MR1652815 (2000g:68047)},
}
@article {Can96,
AUTHOR = {Canetti, Ran},
TITLE = {More on {BPP} and the polynomial-time hierarchy},
JOURNAL = ipl,
FJOURNAL = ipl,
VOLUME = {57},
year = {1996},
NUMBER = {5},
PAGES = {237--241},
ISSN = {0020-0190},
CODEN = {IFPLAT},
MRCLASS = {68Q15},
MRNUMBER = {MR1384168 (96k:68066)},
}
@book{BDG88,
author = {Jos\&\#233; Luis Balcazar and Jose Diaz and Joaquim Gabarro},
title = {Structural complexity Theory},
year = {1988},
isbn = {0-387-18622-0},
publisher = {Springer-Verlag New York, Inc.},
address = {New York, NY, USA},
}
@article {Nis93,
AUTHOR = {Nisan, Noam},
TITLE = {On read-once vs.\ multiple access to randomness in logspace},
NOTE = {Structure in complexity theory (Barcelona, 1990)},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {107},
year = {1993},
NUMBER = {1},
PAGES = {135--144},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68Q15 (03D15 68Q05)},
MRNUMBER = {MR1201169 (93i:68075)},
}
@Article{Sto85,
title={On Approximation Algorithms for {{\#P}}},
author={Larry Stockmeyer},
pages={849--861},
journal=sicomp,
month=nov,
year=1985,
volume=14,
number=4,
preliminary={STOC::Stockmeyer1983:118},
source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}
}
@article {BSSV03,
AUTHOR = {Beame, Paul and Saks, Michael and Sun, Xiaodong and Vee, Erik},
TITLE = {Time-space trade-off lower bounds for randomized computation
of decision problems},
JOURNAL = jacm,
FJOURNAL = jacm,
VOLUME = {50},
year = {2003},
NUMBER = {2},
PAGES = {154--195},
ISSN = {0004-5411},
MRCLASS = {68Q17 (68Q15 68Q25 68W20)},
MRNUMBER = {MR2147528},
}
%for entry below editor ={G. Paun and G. Rozenberg and A. Salomaa},
@inproceedings{vMe04,
author={D. van Melkebeek},
title={Time-Space Lower Bounds for NP-Complete Problems},
booktitle={Current Trends in Theoretical Computer Science},
publisher={World Scientific},
year = {2004},
pages={265-291},
}
@article {DvM06,
AUTHOR = {Diehl, Scott and van Melkebeek, Dieter},
TITLE = {Time-space lower bounds for the polynomial-time hierarchy on
randomized machines},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {36},
year = {2006},
NUMBER = {3},
PAGES = {563--594},
ISSN = {0097-5397},
MRCLASS = {68Q15 (68Q10 68Q17)},
MRNUMBER = {MR2263002}
}
@inproceedings{DvM05-Old,
author={S. Diehl and D. van Melkebeek},
title={Time-Space Lower Bounds for the Polynomial-Time Hierarchy on Randomized Machines},
crossref={ICALP05},
pages={982-993},
}
@article{FLvMV05,
author = {Lance Fortnow and Richard Lipton and Dieter van Melkebeek and Anastasios Viglas},
title = {Time-space lower bounds for satisfiability},
journal = {J. ACM},
volume = {52},
number = {6},
year = {2005},
issn = {0004-5411},
pages = {835--865},
doi = {http://doi.acm.org/10.1145/1101821.1101822},
publisher = {ACM Press},
address = {New York, NY, USA},
}
%note={Previous version titled `Time-Space Tradeoffs for %Nondeterministic Computation.' In 15th %IEEE Conference on Computational Complexity, pages 2-13, %2000.}
@inproceedings{vMR04,
title={A Time Lower Bound for Satisfiability},
author={D. van Melkebeek and R. Raz},
booktitle={31st } # icalp,
pages = {971-982},
year = {2004}
}
@InProceedings{AKRRV01,
title={Time-Space Tradeoffs in the Counting Hierarchy},
author={Eric Allender and Michal Kouck\'{y} and Detlef Ronneburger and Sambuddha Roy and V. Vinay},
pages={295--302},
crossref={CCC01}
}
@article {Lau83,
AUTHOR = {Lautemann, Clemens},
TITLE = {B{PP} and the polynomial hierarchy},
JOURNAL = ipl,
FJOURNAL = ipl,
VOLUME = {17},
year = {1983},
NUMBER = {4},
PAGES = {215--217},
ISSN = {0020-0190},
CODEN = {IFPLAT},
MRCLASS = {03D15 (68Q05 68Q15)},
MRNUMBER = {MR742072 (85j:03063)},
}
@article {CaW04,
AUTHOR = {Cai, Jin-Yi and Watanabe, Osamu},
TITLE = {On proving circuit lower bounds against the polynomial-time
hierarchy},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {33},
year = {2004},
NUMBER = {4},
PAGES = {984--1009},
ISSN = {0097-5397},
MRCLASS = {68Q15 (68Q17)},
MRNUMBER = {MR2065342 (2005e:68061)},
MRREVIEWER = {Bruce Edward Litow},
}
@article {NRS95,
AUTHOR = {Naik, Ashish V. and Regan, Kenneth W. and Sivakumar, D.},
TITLE = {On quasilinear-time complexity theory},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {148},
year = {1995},
NUMBER = {2},
PAGES = {325--349},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68Q15 (03D15 68Q05)},
MRNUMBER = {MR1355592 (96j:68076)},
MRREVIEWER = {William Gasarch},
}
@article {SBI04,
AUTHOR = {Segerlind, Nathan and Buss, Sam and Impagliazzo, Russell},
TITLE = {A switching lemma for small restrictions and lower bounds for {$k$}-{DNF} resolution},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {33},
year = {2004},
NUMBER = {5},
PAGES = {1171--1200},
ISSN = {0097-5397},
MRCLASS = {03F20 (68Q15)},
MRNUMBER = {MR2084484 (2005g:03097)},
MRREVIEWER = {Jan Kraj{\'{\i}}{\v{c}}ek},
}
%Field stuff papers
@article {FiT88,
AUTHOR = {Fich, Faith E. and Tompa, Martin},
TITLE = {The parallel complexity of exponentiating polynomials over
finite fields},
JOURNAL = {J. Assoc. Comput. Mach.},
FJOURNAL = {Journal of the Association for Computing Machinery},
VOLUME = {35},
year = {1988},
NUMBER = {3},
PAGES = {651--667},
ISSN = {0004-5411},
CODEN = {JACOAH},
MRCLASS = {12-04 (11T06 11Y16 68Q25)},
MRNUMBER = {MR963165 (90c:12001)},
MRREVIEWER = {Heinrich Rolletschek},
}
@Misc{MoS83,
author = {Moshe Morgensteren and Eli Shamir},
title = {Parallel Algorithms for Arithmetics, Irreducibility and
Factoring of GFq-Polynomials},
howpublished = {Stanford University
Technical Report STAN-CS-83-991},
month = {December},
year = {1983}
}
@article {Rab80,
AUTHOR = {Michael O. Rabin},
TITLE = {Probabilistic Algorithms in Finite Fields},
JOURNAL = sicomp,
FJOURNAL = sicomp,
VOLUME = {9},
year = {1980},
NUMBER = {2},
PAGES = {273--280},
ISSN = {0097-5397}
}
@article {FVB94,
AUTHOR = {Frandsen, Gudmund S. and Valence, Mark and Barrington, David
A. Mix},
TITLE = {Some results on uniform arithmetic circuit complexity},
JOURNAL = {Math. Systems Theory},
FJOURNAL = {Mathematical Systems Theory. An Journal on
Mathematical Computing Theory},
VOLUME = {27},
year = {1994},
NUMBER = {2},
PAGES = {105--124},
ISSN = {0025-5661},
CODEN = {MASTBA},
MRCLASS = {68Q05},
MRNUMBER = {MR1255452 (94m:68039)},
MRREVIEWER = {Marius Zimand},
}
@article {StF93,
AUTHOR = {Sturtivant, Carl and Frandsen, Gudmund Skovbjerg},
TITLE = {The computational efficacy of finite-field arithmetic},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {112},
year = {1993},
NUMBER = {2},
PAGES = {291--309},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {11Y16 (11T30 68Q40)},
MRNUMBER = {MR1216324 (94e:11144)},
MRREVIEWER = {Lajos R{\'o}nyai},
}
@article {BFS93,
AUTHOR = {Boyar, Joan and Frandsen, Gudmund and Sturtivant, Carl},
TITLE = {An arithmetic model of computation equivalent to threshold
circuits},
JOURNAL = {Theoret. Comput. Sci.},
FJOURNAL = {Theoretical Computer Science},
VOLUME = {93},
year = {1992},
NUMBER = {2},
PAGES = {303--319},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68Q05 (94C05)},
MRNUMBER = {MR1146198 (93f:68023)},
MRREVIEWER = {Friedhelm Meyer auf der Heide},
}
@article {ABDvzGSS03,
AUTHOR = {Allender, Eric and Bernasconi, Anna and Damm, Carsten and von
zur Gathen, Joachim and Saks, Michael and Shparlinski, Igor},
TITLE = {Complexity of some arithmetic problems for binary polynomials},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {12},
year = {2003},
NUMBER = {1-2},
PAGES = {23--47},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q25 (11Y16 68Q17 94A60 94C10)},
MRNUMBER = {MR2054893 (2005b:68119)},
MRREVIEWER = {Bruce Edward Litow},
}
@article {ABI86,
AUTHOR = {Noga Alon and L{\'a}szl{\'o} Babai and Alon Itai},
TITLE = {A fast and simple randomized
algorithm for the maximal
independent set problem},
JOURNAL = {Journal of Algorithms},
VOLUME = {7},
year = {1986},
PAGES = {567--583},
}
@article {AGHP92,
AUTHOR = {Alon, Noga and Goldreich, Oded and
H{\aa}stad, Johan and Peralta, Ren{\'e}},
TITLE = {Simple constructions of almost {$k$}-wise
independent random variables},
JOURNAL = {Random Structures \& Algorithms},
FJOURNAL = {Random Structures \& Algorithms},
VOLUME = {3}, year = {1992}, NUMBER = {3},
PAGES = {289--304}, ISSN = {1042-9832}, MRCLASS
= {94A55 (65C10 68Q30)}, MRNUMBER =
{93k:94006a}, }
@article{NaN93,
author = {Joseph Naor and Moni Naor},
title = {Small-bias probability spaces: efficient constructions and applications},
journal = {SIAM J. Comput.},
volume = {22},
number = {4},
year = {1993},
issn = {0097-5397},
pages = {838--856},
doi = {http://dx.doi.org/10.1137/0222053},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA}
}
@InProceedings{NaN90,
title={Small-bias probability spaces: efficient
constructions and applications},
author={J. Naor and M. Naor},
pages={213--223},
booktitle={22nd } # stoc,
publisher = {ACM},
year=1990
}
@InProceedings{CFG+85,
title={The bit extraction problem and
$t$-resilient functions},
author = {Benny Chor and
Oded Goldreich and
Johan H{\aa}stad and
Joel Friedman and
Steven Rudich and
Roman Smolensky},
booktitle={26th IEEE } # focs,
pages={396--407},
year = {1985}
}
@article {ReifTate92,
AUTHOR = {Reif, J. and Tate, S.},
TITLE = {On threshold circuits and polynomial computation},
JOURNAL = sicomp,
VOLUME = {21},
year = {1992},
NUMBER = {5},
PAGES = {896--908}
}
@article {Reif86,
AUTHOR = {Reif, J.},
TITLE = {Logarithmic depth circuits for algebraic functions},
JOURNAL = sicomp,
VOLUME = {15},
year = {1986},
NUMBER = {1},
PAGES = {231--242}
}
@article{Eberly89,
AUTHOR = {Eberly, W.},
TITLE = {Very fast parallel polynomial arithmetic},
JOURNAL = sicomp,
VOLUME = {18},
year = {1989},
NUMBER = {5},
PAGES = {955--976}
}
@article{Siev72,
AUTHOR = {Sieveking, M.},
TITLE = {An algorithm for division of power series},
JOURNAL = {Computing},
VOLUME = {10},
year = {1972},
PAGES = {153--156},
}
@article {Kung74,
AUTHOR = {Kung, H. T.},
TITLE = {On computing reciprocals of power series},
JOURNAL = {Numerical Math},
VOLUME = {22},
year = {1974},
PAGES = {341--348},
}
%end field stuff papers
@inproceedings{ChH05,
AUTHOR = {Chattopadhyay, Arkadev and Hansen, Kristoffer Arnsfelt},
TITLE = {Lower Bounds for Circuits With Few Modular and Symmetric Gates},
crossref={ICALP05},
}
@Proceedings{CCC2008,
title = {23rd Conference on Computational Complexity},
booktitle = {23rd Conference on Computational Complexity},
year = {2008},
organization = {IEEE},
crossrefonly = 1
}
@Proceedings{CCC07,
title = {22nd Conference
on Computational Complexity},
booktitle = {22nd Conference
on Computational Complexity},
year = {2007},
c-address = {San Diego, California},
month = {June 13--16},
organization = {IEEE},
crossrefonly = 1
}
@inproceedings{Bei93,
AUTHOR = {Beigel, Richard},
TITLE = {The polynomial method in circuit complexity},
BOOKTITLE = {8th Structure in Complexity
Theory Conference},
PAGES = {82--95},
PUBLISHER = {IEEE},
year = {1993}
}
@inproceedings{Yao90,
author = "A. C. Yao",
title = "On ACC and threshold circuits",
booktitle = "Proc. 31st Ann. IEEE Symp. Found. Comput. Sci.",
pages = "619-627",
year = "1990"
}
@inproceedings{BRS91,
author = "Richard Beigel and Nick Reingold and Daniel Spielman",
title = "The Perceptron Strikes Back",
booktitle = "Structure in Complexity Theory Conference",
pages = "286-291",
year = "1991",
url = "citeseer.ist.psu.edu/beigel91perceptron.html"
}
@article {BeT94,
AUTHOR = {R. Beigel and J. Tarui},
TITLE = {On ACC},
NOTE = {Special issue devoted to the 4th McGill Workshop on Complexity Theory. Preliminary version in FOCS '91.},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {4},
year = {1994},
NUMBER = {4},
PAGES = {350-3-66}
}
@inproceedings{Yao85,
author = {Yao, Andrew},
title = {Separating the polynomial-time hierarchy by oracles},
booktitle = {26th } # focs,
year = {1985},
pages = {1--10},
publisher = {IEEE}
}
@article {BrS92,
AUTHOR = {Bruck, Jehoshua and Smolensky, Roman},
TITLE = {Polynomial threshold functions, {${\rm AC}\sp 0$} functions, and spectral norms},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {21},
year = {1992},
NUMBER = {1},
PAGES = {33--42},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {68Q25 (68M07 94C10)},
MRNUMBER = {MR1148813 (93a:68053)},
}
@InProceedings{All89,
title={A Note on the Power of Threshold Circuits},
author={Eric Allender},
pages={580--584},
crossref={FOCS30},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@article{GreenRoy07,
author = {Frederic Green and Amitabha Roy},
title = {Uniqueness of Optimal Mod 3 Circuits for Parity},
journal = {Journal of Number Theory},
volume = {130},
issue = {4},
pages = {961 - 975},
year = {2010}
}
@article {ABFR94,
AUTHOR = {Aspnes, James and Beigel, Richard and Furst, Merrick and Rudich, Steven},
TITLE = {The expressive power of voting polynomials},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal on Combinatorics and the Theory of Computing},
VOLUME = {14},
year = {1994},
NUMBER = {2},
PAGES = {135--148},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {68Q15 (06E30)},
MRNUMBER = {MR1289068 (96b:68057)},
MRREVIEWER = {Norbert Blum},
}
@inproceedings{LVW93,
author = {Michael Luby and Boban Veli{\v c}kovi{\'c} and Avi Wigderson},
title = {Deterministic approximate counting of depth-2 circuits},
booktitle = {2nd Israeli Symposium on Theoretical Computer Science (ISTCS)},
pages = "18-24",
year = "1993",
}
@article {HMPST93,
AUTHOR = {Hajnal, Andr{\'a}s and Maass, Wolfgang and Pudl{\'a}k, Pavel
and Szegedy, M{\'a}ri{\'o} and Tur{\'a}n, Gy{\"o}rgy},
TITLE = {Threshold circuits of bounded depth},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {46},
year = {1993},
NUMBER = {2},
PAGES = {129--154},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q10 (68Q25 94C10)},
MRNUMBER = {MR1217153 (94c:68062)},
MRREVIEWER = {Juraj Hromkovi{\v{c}}},
}
@article {BNS92,
AUTHOR = {Babai, L{\'a}szl{\'o} and Nisan, Noam and Szegedy,
M{\'a}ri{\'o}},
TITLE = {Multiparty protocols, pseudorandom generators for logspace,
and time-space trade-offs},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {45},
year = {1992},
NUMBER = {2},
PAGES = {204--232},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q05 (68Q15 68Q22 68Q25 68Q30)},
MRNUMBER = {MR1186884 (93m:68048)},
MRREVIEWER = {Norbert Blum},
}
@article {RaW93,
AUTHOR = {Razborov, Alexander and Wigderson, Avi},
TITLE = {{$n\sp {\Omega(\log n)}$} lower bounds on the size of
depth-{$3$} threshold circuits with {AND} gates at the bottom},
JOURNAL = ipl,
FJOURNAL = ipl,
VOLUME = {45},
year = {1993},
NUMBER = {6},
PAGES = {303--307},
ISSN = {0020-0190},
CODEN = {IFPLAT},
MRCLASS = {68Q15},
MRNUMBER = {MR1216940 (94c:68075)},
}
@article {Bei94,
AUTHOR = {Beigel, Richard},
TITLE = {When do extra majority gates help? {${\rm polylog}(N)$}
majority gates are equivalent to one},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {4},
year = {1994},
NUMBER = {4},
PAGES = {314--324},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q15 (68Q25 94C10)},
MRNUMBER = {MR1313532 (96d:68059)},
MRREVIEWER = {Juraj Hromkovi{\v{c}}},
}
@article {HaG91,
AUTHOR = {H{\aa}stad, Johan and Goldmann, Mikael},
TITLE = {On the power of small-depth threshold circuits},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {1},
year = {1991},
NUMBER = {2},
PAGES = {113--129},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q20 (68R10)},
MRNUMBER = {MR1134945 (93e:68025)},
MRREVIEWER = {Frederic Green},
}
@inproceedings{HaM04,
author = "Kristoffer Arnsfelt Hansen and Peter Bro Miltersen ",
title = "Some Meet-in-the-Middle Circuit Lower Bounds",
pages = "334 - 345",
booktitle = {29th Symposium on Mathematical Foundations of Computer Science (MFCS)},
year = {2004},
series = {Lecture Notes in Computer Science, Volume 3153},
}
@book {Gol99,
AUTHOR = {Goldreich, Oded},
TITLE = {Modern cryptography, probabilistic proofs and
pseudorandomness},
SERIES = {Algorithms and Combinatorics},
VOLUME = {17},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin},
year = {1999},
PAGES = {xvi+182},
ISBN = {3-540-64766-X},
MRCLASS = {94A60 (68-02 68P25 68Q15)},
MRNUMBER = {2000f:94029},
MRREVIEWER = {Simon R. Blackburn},
}
@TechReport{Bea94,
author = {Paul Beame},
title = {A switching lemma primer},
institution = {Department of Computer Science and Engineering, University of Washington},
year = {1994},
month = {November},
number = {UW-CSE-95-07-01},
note = {Available from http://www.cs.washington.edu/homes/beame/}
}
@unpublished{Thapen09,
author={Neil Thapen},
title={Notes on switching lemmas},
year={2009},
note={http://www.math.cas.cz/$\sim$thapen/}
}
@inproceedings{ImZ89,
author = "Russell Impagliazzo and David Zuckerman",
title = "How to Recycle Random Bits",
pages = "248-253",
crossref={FOCS30},
}
@Proceedings{MFCS2004,
title = {29th Symposium on Mathematical Foundations of Computer Science (MFCS)},
booktitle = {29th Symposium on Mathematical Foundations of Computer Science (MFCS)},
year = {2004},
c-address = {Prague, Czech Republic},
month = {August 22--27},
crossrefonly = 1
}
%%month = {August 22--24},
@Proceedings{RANDOM2004,
title = {8th } # random,
booktitle = {8th } # random,
year = {2004},
publisher = {Springer-Verlag},
c-address = {Cambridge, Massachusetts},
crossrefonly = 1
}
@article {HAB01,
AUTHOR = {Hesse, William and Allender, Eric and Barrington, David A.
Mix},
TITLE = {Uniform constant-depth threshold circuits for division and
iterated multiplication},
NOTE = {Special issue on complexity, 2001 (Chicago, IL)},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {65},
year = {2002},
NUMBER = {4},
PAGES = {695--716},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (03D15 68Q19 68Q25)},
MRNUMBER = {2004b:68057},
MRREVIEWER = {Bruce Edward Litow},
}
@article{ApplebaumIK06,
author = {Benny Applebaum and
Yuval Ishai and
Eyal Kushilevitz},
title = {Cryptography in {$NC^0$}},
journal = {SIAM J. Comput.},
volume = {36},
number = {4},
year = {2006},
pages = {845-888},
ee = {http://dx.doi.org/10.1137/S0097539705446950},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{AIK04,
author = "Benny Applebaum and Yuval Ishai and Eyal Kushilevitz",
title = "Cryptography in {$NC^0$}",
crossref={FOCS45}
}
@inproceedings{CSS97,
author = {Cai, Jin-Yi and Sivakumar, D. and Strauss, Martin},
title = "Constant Depth Circuits and the Lutz Hypothesis",
pages = "595-604",
crossref={FOCS38}
}
@incollection {Val77,
AUTHOR = {Valiant, Leslie G.},
TITLE = {Graph-theoretic arguments in low-level complexity},
BOOKTITLE = {6th Symposium on Mathematical Foundations of Computer Science},
PAGES = {162--176},
series = lncs,
volume = {53},
PUBLISHER = {Springer},
year = {1977}
}
@InProceedings{Smo87,
title={Algebraic methods in the theory of lower bounds for {B}oolean circuit complexity},
author={Smolensky, Roman},
pages={77--82},
booktitle={19th } # stoc,
year=1987,
publisher={ACM}
}
@article {Raz87,
AUTHOR = {Razborov, Alexander},
TITLE = {Lower bounds on the dimension of schemes of bounded depth in a complete basis containing the logical addition function},
JOURNAL = {Mat. Zametki},
FJOURNAL = {Akademiya Nauk SSSR. Matematicheskie Zametki},
VOLUME = {41},
year = {1987},
NUMBER = {4},
PAGES = {598--607},
note = {English translation in Mathematical Notes of the Academy of Sci. of the USSR, 41(4):333-338, 1987.}
}
@article {CaW79,
AUTHOR = {Carter, J. Lawrence and Wegman, Mark N.},
TITLE = {Universal classes of hash functions},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {18},
year = {1979},
NUMBER = {2},
PAGES = {143--154},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68H05 (68C25)},
MRNUMBER = {80f:68110a},
}
@article{Nao91,
author = "Moni Naor",
title = "Bit Commitment Using Pseudorandomness",
journal = "Journal of Cryptology: the journal of the Association for Cryptologic Research",
volume = "4",
number = "2",
pages = "151--158",
year = "1991",
url = "citeseer.ist.psu.edu/naor91bit.html" }
@article {AKS04,
AUTHOR = {M. Agrawal and N. Kayal and N. Saxena},
TITLE = {PRIMES in P},
JOURNAL = {Ann. of Math.},
FJOURNAL = {Annals of Pure Mathematics},
VOLUME = {160},
year = {2004},
NUMBER = {2},
PAGES = {781--793}
}
@article {Ajt83,
AUTHOR = {Ajtai, Mikl{\'o}s},
TITLE = {{$\Sigma \sp{1}\sb{1}$}-formulae on finite structures},
JOURNAL = {Ann. Pure Appl. Logic},
FJOURNAL = {Annals of Pure and Applied Logic},
VOLUME = {24},
year = {1983},
NUMBER = {1},
PAGES = {1--48},
ISSN = {0168-0072},
CODEN = {APALD7},
MRCLASS = {03C13 (03B10 03B15 03C35)},
MRNUMBER = {85b:03048},
MRREVIEWER = {A. H. Lachlan},
}
@article{Ajt89,
AUTHOR = {Ajtai, Mikl{\'o}s},
TITLE = {First-order definability on finite structures},
JOURNAL = {Ann. Pure Appl. Logic},
FJOURNAL = {Annals of Pure and Applied Logic},
VOLUME = {45},
year = {1989},
NUMBER = {3},
PAGES = {211--225},
ISSN = {0168-0072},
CODEN = {APALD7},
MRCLASS = {03C13 (03C40)},
MRNUMBER = {91i:03066},
MRREVIEWER = {M. Yasuhara},
}
@article {BoL87,
AUTHOR = {Ravi Boppana and Lagarias, Jeffrey},
TITLE = {One-way functions and circuit complexity},
JOURNAL = {Inform. and Comput.},
FJOURNAL = {Information and Computation},
VOLUME = {74},
year = {1987},
NUMBER = {3},
PAGES = {226--240},
ISSN = {0890-5401},
MRCLASS = {68Q15 (94A60 94C15)},
MRNUMBER = {88k:68028},
MRREVIEWER = {Ingo Wegener},
}
@article{GennaroGKT05,
author = {Rosario Gennaro and
Yael Gertner and
Jonathan Katz and
Luca Trevisan},
title = {Bounds on the Efficiency of Generic Cryptographic Constructions},
journal = {SIAM J. Comput.},
volume = {35},
number = {1},
year = {2005},
pages = {217-246},
ee = {http://epubs.siam.org/SICOMP/volume-35/art_44327.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@incollection {GeT00,
AUTHOR = {Gennaro, Rosario and Trevisan, Luca},
TITLE = {Lower bounds on the efficiency of generic cryptographic
constructions},
BOOKTITLE = {41st Symposium on Foundations of Computer Science
(Redondo Beach, CA, 2000)},
PAGES = {305--313},
PUBLISHER = {IEEE Comput. Soc. Press},
ADDRESS = {Los Alamitos, CA},
year = {2000},
MRCLASS = {94A60 (68Q17)},
MRNUMBER = {1 931 828},
}
@article {Lev87,
AUTHOR = {Levin, Leonid A.},
TITLE = {One way functions and pseudorandom generators},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal of the J\'anos Bolyai
Mathematical Society},
VOLUME = {7},
year = {1987},
NUMBER = {4},
PAGES = {357--363},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {68Q25 (03D15 65C10)},
MRNUMBER = {89c:68048},
MRREVIEWER = {Cristian Calude},
}
@article {GKL93,
AUTHOR = {Goldreich, Oded and Krawczyk, Hugo and Luby, Michael},
TITLE = {On the existence of pseudorandom generators},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {22},
year = {1993},
NUMBER = {6},
PAGES = {1163--1175},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {11K45 (11T71 65C10)},
MRNUMBER = {95f:11054},
}
@inproceedings{RTV04,
author = "Omer Reingold and Luca Trevisan and Salil Vadhan",
title = "Notions of Reducibility between Cryptographic Primitives",
booktitle = "1st Theory of Cryptography Conference (Feb 19-21, 2004: Cambridge, MA, USA)",
publisher = "Springer-Verlag",
year = "2004"
}
@Article{MNT93,
author = "Yishay Mansour and Noam Nisan and Prasoon Tiwari",
title = "The Computational Complexity of Universal Hashing",
journal = "Theoretical Computer Science",
volume = "107",
pages = "121--133",
year = "1993"
}
@inproceedings{MNT90,
author = "Yishay Mansour and Noam Nisan and Prasoon Tiwari",
title = "The Computational Complexity of Universal Hashing",
booktitle = "22nd {ACM} Symposium on Theory of Computing (May 14--16 1990: Baltimore, {MD}, {USA})",
publisher = "ACM Press",
address = "New York, NY 10036, USA",
isbn = "0-89791-361-2",
pages = "235--243",
year = "1990",
url = "citeseer.nj.nec.com/mansour02computational.html" }
@article {AAIPR01,
AUTHOR = {Agrawal, Manindra and Allender, Eric and Impagliazzo, Russell
and Pitassi, Toniann and Rudich, Steven},
TITLE = {Reducing the complexity of reductions},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {10},
year = {2001},
NUMBER = {2},
PAGES = {117--138},
ISSN = {1016-3328},
CODEN = {CPTCEU},
MRCLASS = {68Q17 (68Q15)},
MRNUMBER = {2003g:68046},
}
@article{DBLP:journals/ipl/Goldmann95,
author = {Mikael Goldmann},
title = {A Note on the Power of Majority Gates and Modular Gates},
journal = {Inf. Process. Lett.},
volume = {53},
number = {6},
year = {1995},
pages = {321-327},
ee = {http://dx.doi.org/10.1016/0020-0190(94)00221-J},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{GNR01,
AUTHOR = {Goldmann, Mikael and N{\"a}slund, Mats and Russell, Alexander},
TITLE = {Complexity bounds on general hard-core predicates},
JOURNAL = {J. Cryptology},
FJOURNAL = {Journal of Cryptology. The Journal of the Association for Cryptologic Research},
VOLUME = {14},
year = {2001},
NUMBER = {3},
PAGES = {177--195},
ISSN = {0933-2790},
CODEN = {JOCREQ},
MRCLASS = {94C10 (68Q17 94A60)},
MRNUMBER = {2002d:94074},
MRREVIEWER = {Ronald E. Prather},
}
@InProceedings{AjB84,
title={A Theorem on Probabilistic Constant Depth Computation},
author={Mikl{\'o}s Ajtai and Michael Ben-Or},
pages={471--474},
booktitle = "16th ACM " # stoc,
year = "1984"
}
@InProceedings{ImR89,
title={Limits on the provable consequences of one-way permutations},
author={Impagliazzo, Russell and Rudich, Steven},
pages={44--61},
crossref={STOC21}
}
@InProceedings{INW94,
title={Pseudorandomness for Network Algorithms},
author={Russell Impagliazzo and Noam Nisan and Avi Wigderson},
pages={356--364},
booktitle = {26th ACM } # stoc,
year = {1994}
}
@article{TrV07,
author = {Luca Trevisan and Salil Vadhan},
title = {Pseudorandomness and Average-Case Complexity Via Uniform Reductions},
journal = {Comput. Complex.},
volume = {16},
number = {4},
year = {2007},
issn = {1016-3328},
pages = {331--364},
doi = {http://dx.doi.org/10.1007/s00037-007-0233-x},
publisher = {Birkhauser Verlag},
address = {Basel, Switzerland, Switzerland},
}
@InProceedings{TrV02,
author={Luca Trevisan and Salil Vadhan},
title={Pseudorandomness and Average-Case Complexity via Uniform Reductions},
booktitle={17th {IEEE} Conference on Computational Complexity},
year={2002},
organization={IEEE},
address={Montr{\'e}al, CA},
month={May},
pages={129--138}
}
@Article{KlS03,
author = {Adam Klivans and Rocco A. Servedio},
title = {Boosting and Hard-Core Sets},
journal = {Machine Learning},
pages = {217-238},
year = {2003},
volume = {53},
number = {3}
}
@book{And02,
AUTHOR = {Anderson, Ian},
TITLE = {Combinatorics of finite sets},
NOTE = {Corrected reprint of the 1989
edition},
PUBLISHER = {Dover Publications Inc.},
ADDRESS = {Mineola, NY},
year = {2002},
PAGES = {xvi+250},
ISBN = {0-486-42257-7},
MRCLASS = {05-01},
MRNUMBER = {2003b:05001}
}
@Proceedings{STOC26,
title={26th ACM Symposium on the Theory of Computing},
booktitle={26th ACM Symposium on the Theory of Computing},
month={23--25 } # may,
year=1994,
address={Montr\'eal, Qu\'ebec, Canada},
c-organization={ACM},
key={ACM},
crossrefonly=1}
@InProceedings{Tre03,
author = "Luca Trevisan",
title = "List Decoding Using the {XOR} Lemma",
pages = {126--135},
crossref={FOCS44}
}
@InProceedings{BoT03,
author = "Andrej Bogdanov and Luca Trevisan",
title = "On Worst-Case to Average-Case Reductions for {NP} Problems",
pages = "308-317",
crossref={FOCS44}
}
@Article{HaR03,
author = {T. Hartman and R. Raz},
title = {On the Distribution of the Number of Roots of Polynomials and Explicit Weak Designs},
journal = {Random Structures \& Algorithms},
year = {2003},
pages = {235-263},
volume = {23},
number = {3},
}
@article{MoO03,
author = {Elchanan Mossel and Ryan O'Donnell},
title = {On the noise sensitivity of monotone functions},
journal = {Random Struct. Algorithms},
volume = {23},
number = {3},
year = {2003},
issn = {1042-9832},
pages = {333--350},
doi = {http://dx.doi.org/10.1002/rsa.10097},
publisher = {John Wiley \& Sons, Inc.},
}
@Article{Nis92,
author = "Noam Nisan",
title = "Pseudorandom Generators for Space-bounded Computation",
journal = "Combinatorica",
number = "4",
pages = "449-461",
volume = "12",
year = "1992",
}
@inproceedings {Lev95,
AUTHOR = {Levin, Leonid A.},
TITLE = {Randomness and nondeterminism},
BOOKTITLE = {Congress of Mathematicians,
Vol.\ 1, 2 (Z\"urich, 1994)},
PAGES = {1418--1419},
PUBLISHER = {Birkh\"auser},
ADDRESS = {Basel},
year = {1995},
MRCLASS = {68Q10 (03D15 68P25 68Q15 68Q30)},
MRNUMBER = {1 404 044},
}
@inproceedings{BJT99,
author = "Nader H. Bshouty and Jeffrey C. Jackson and Christino Tamon",
title = "More Efficient {PAC}-Learning of {DNF} with Membership Queries Under the Uniform Distribution",
booktitle = "Computational Learing Theory",
pages = "286-295",
year = "1999",
url = "citeseer.nj.nec.com/article/bshouty99more.html" }
Citations (may not include all citations):
@Article{KM93,
author = "Eyal Kushilevitz and Yishay Mansour",
title = "Learning Decision Trees Using the {Fourier} Spectrum",
journal = "SIAM Journal on Computing",
volume = "22",
number = "6",
pages = "1331--1348",
month = dec,
year = "1993",
coden = "SMJCAT",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
mrclass = "68T05 (42A38 68Q25)",
mrnumber = "94j:68256",
bibdate = "Sat Jan 18 18:03:50 MST 1997",
acknowledgement = ack-nhfb,
}
@incollection {BRST02,
AUTHOR = {Ziv Bar-Yossef and Omer Reingold and Ronen Shaltiel and Luca Trevisan},
TITLE = {Streaming through combinatorial objects},
BOOKTITLE = {Seventeenth IEEE Conference on Computational Complexity},
PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA},
year = {2002}
}
@article{ImN96,
author = "Russell Impagliazzo and Moni Naor",
title = "Efficient Cryptographic Schemes Provably as Secure as Subset Sum",
journal = "Journal of Cryptology",
volume = "9",
number = "4",
pages = "199--216",
year = "1996"
}
@article{Tre01,
author = "Luca Trevisan",
title = "Extractors and pseudorandom generators",
journal = jacm,
volume = "48",
number = "4",
pages = "860-879",
year = "2001"
}
@article {Wag86,
AUTHOR = {Wagner, Klaus W.},
TITLE = {The complexity of combinatorial problems with succinct input
representation},
JOURNAL = {Acta Inform.},
FJOURNAL = {Acta Informatica},
VOLUME = {23},
year = {1986},
NUMBER = {3},
PAGES = {325--356},
ISSN = {0001-5903},
CODEN = {AINFA2},
MRCLASS = {68Q15},
MRNUMBER = {88i:68040},
MRREVIEWER = {Sam M. Kim},
}
@article {Bop97,
AUTHOR = {Boppana, Ravi},
TITLE = {The average sensitivity of bounded-depth circuits},
JOURNAL = ipl,
FJOURNAL = ipl,
VOLUME = {63},
year = {1997},
NUMBER = {5},
PAGES = {257--261},
ISSN = {0020-0190},
CODEN = {IFPLAT},
MRCLASS = {68Q15},
MRNUMBER = {98f:68093},
}
@article {Jac97,
AUTHOR = {Jackson, Jeffrey C.},
TITLE = {An efficient membership-query alogithm for learning {DNF} with
respect to the uniform distribution},
NOTE = {35th Symposium on Foundations of Computer Science
(Santa Fe, NM, 1994)},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {55},
year = {1997},
NUMBER = {3},
PAGES = {414--440},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68T05 (68Q99)},
MRNUMBER = {98m:68230},
}
@article{Sha02,
author = "Ronen Shaltiel",
title = "Recent Developments in Explicit Constructions of Extractors",
journal = "Bulletin of the European Association for Theoretical Computer Science",
volume = "77",
pages = "182--194",
year = "2002"
}
@article{AlW90,
author = "Eric W. Allender and Klaus W. Wagner",
title = "Counting Hierarchies: Polynomial Time and Constant Depth Circuits",
journal = "Bulletin of the European Association for Theoretical Computer Science",
volume = "40",
pages = "182--194",
year = "1990",
url = "citeseer.nj.nec.com/allender90counting.html" }
@article{FSS84,
title = {Parity, Circuits, and the Polynomial-Time Hierarchy.},
author = {Merrick L. Furst and James B. Saxe and Michael Sipser},
journal = {Mathematical Systems Theory},
volume = {17},
number = {1},
pages = {13--27},
year = {1984}
}
@article{IPZ01,
title = {Which problems have strongly exponential complexity?},
author = {Russell Impagliazzo and Ramamohan Paturi and Francis Zane},
journal = {J. Computer \& Systems Sciences},
volume = {63},
number = {4},
pages = {512--530},
month = {Dec},
year = {2001}}
@article{Nep70,
author = "Valery A. Nepomnja\v{s}\v{c}i\u{\i}",
title = "Rudimentary predicates and {T}uring calculations",
journal = "Soviet Mathematics-Doklady",
volume = "11",
number = "6",
year = "1970",
pages = {1462--1465} }
@article{Gol97,
author = "Oded Goldreich",
title = "A Sample of Samplers - A Computational Perspective on Sampling (survey)",
journal = eccc,
volume = "4",
number = "020",
year = "1997",
url = "citeseer.nj.nec.com/goldreich97sample.html" }
@article {LPS88,
AUTHOR = {Lubotzky, Alexander and Phillips, R. and Sarnak, P.},
TITLE = {Ramanujan graphs},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal of the J\'anos Bolyai Mathematical Society},
VOLUME = {8},
year = {1988},
NUMBER = {3},
PAGES = {261--277},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {05C75 (05C25 05C50)},
MRNUMBER = {89m:05099},
MRREVIEWER = {Dave Witte},
}
@book{Ros02,
AUTHOR = {Ross, Sheldon},
TITLE = {Probability Models for Computer Science},
PUBLISHER = {Academic Press},
ADDRESS = {Berlin},
year = {2002},
}
@book {Vol99,
AUTHOR = {Vollmer, Heribert},
TITLE = {Introduction to circuit complexity},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin},
year = {1999},
PAGES = {xii+270},
ISBN = {3-540-64310-9},
MRCLASS = {68Q15 (68Q05 68Q10 94-02 94C05)},
MRNUMBER = {2001b:68047},
MRREVIEWER = {Frederic Green},
}
@article {Uma03,
AUTHOR = {Umans, Christopher},
TITLE = {Pseudo-random generators for all hardnesses},
NOTE = {Special issue on STOC2002 (Montreal, QC)},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {67},
year = {2003},
NUMBER = {2},
PAGES = {419--440},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (11K45 65C10)},
MRNUMBER = {MR2022839 (2004k:68055)},
MRREVIEWER = {Peter Bro Miltersen},
}
@inproceedings{Uma02,
author = {Christopher Umans},
title = {Pseudo-random generators for all hardnesses},
booktitle = {34th } # stoc,
publisher = {ACM},
year = {2002},
pages = {627--634}
}
@article{ODo04,
author = {Ryan O'Donnell},
title = {Hardness Amplification Within {$NP$}},
pages={68--94},
journal=jcss,
year=2004,
month=aug,
volume=69,
number=1
}
@article {Nis91,
AUTHOR = {Noam Nisan},
TITLE = {Pseudorandom bits for constant depth circuits},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal on Combinatorics and
the Theory of Computing},
VOLUME = {11},
year = {1991},
NUMBER = {1},
PAGES = {63--70},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {68Q15 (03D15 68Q25)},
MRNUMBER = {92g:68055},
}
@InProceedings{Kli01,
author = "Adam R. Klivans",
title = "On the Derandomization of Constant Depth Circuits",
booktitle = {5th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)},
publisher = {Springer},
year = {2001}
}
@InProceedings{HaR00,
author = "Tzvika Hartman and Ran Raz",
title = "On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors",
crossref = {RANDOM2000},
pages = {3--22}
}
@book {vLi99,
AUTHOR = {van Lint, J. H.},
TITLE = {Introduction to coding theory},
EDITION = {Third},
PUBLISHER = {Springer-Verlag},
ADDRESS = {Berlin},
year = {1999},
PAGES = {xiv+227},
ISBN = {3-540-64133-5},
MRCLASS = {94-01 (11T71 94Bxx)},
MRNUMBER = {2000a:94001},
MRREVIEWER = {Ruud Pellikaan},
}
@article {BIS90,
AUTHOR = {Barrington, David A. Mix and Immerman, Neil and Straubing,
Howard},
TITLE = {On uniformity within {$NC^1$}},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {41},
year = {1990},
NUMBER = {3},
PAGES = {274--306},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (03D15)},
MRNUMBER = {91h:68059},
}
@article {LMN93,
AUTHOR = {Linial, Nathan and Mansour, Yishay and Nisan, Noam},
TITLE = {Constant depth circuits, {F}ourier transform, and
learnability},
JOURNAL = jacm,
VOLUME = {40},
year = {1993},
NUMBER = {3},
PAGES = {607--620},
ISSN = {0004-5411}
}
@incollection {Ajt93,
AUTHOR = {Ajtai, Mikl{\'o}s},
TITLE = {Approximate counting with uniform constant-depth circuits},
BOOKTITLE = {Advances in computational complexity theory},
PAGES = {1--20},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
year = {1993}
}
@article {STV01,
AUTHOR = {Sudan, Madhu and Trevisan, Luca and Vadhan, Salil},
TITLE = {Pseudorandom generators without the {X}{O}{R} lemma},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {62},
year = {2001},
NUMBER = {2},
PAGES = {236--266},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (65C10 68W20)},
MRNUMBER = {2002f:68040},
MRREVIEWER = {Frederic Green},
}
@incollection{Agr01,
AUTHOR = {Agrawal, Manindra},
TITLE = {Hard Sets and Pseudo-random Generators for Constant Depth Circuits},
BOOKTITLE = {21st Foundations of Software Technology and Theoretical Computer Science},
PAGES = {58--69 },
year = {2001},
PUBLISHER = {Springer-Verlag}
}
@incollection {KvM99,
AUTHOR = {Klivans, Adam R. and van Melkebeek, Dieter},
TITLE = {Graph nonisomorphism has subexponential size proofs unless the
polynomial-time hierarchy collapses},
BOOKTITLE = {ACM Symposium on Theory of Computing (Atlanta, GA,
1999)},
PAGES = {659--667},
PUBLISHER = {ACM},
ADDRESS = {New York},
year = {1999},
MRCLASS = {68Q15 (68Q25 68W20)},
MRNUMBER = {2001i:68051},
}
@incollection {YuY94,
AUTHOR = {Yu, Xiangdong and Yung, Moti},
TITLE = {Space Lower-Bounds for Pseudorandom-Generators},
BOOKTITLE = {Ninth Structure in Complexity Theory Conference},
PAGES = {186--197},
PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA},
year = {1994}
}
@incollection {CrM01,
AUTHOR = {Cryan, Mary and Miltersen, Peter Bro},
TITLE = {On Pseudorandom Generators in {$NC^0$}},
BOOKTITLE = {26th Symposium on Mathematical Foundations of Computer Science (MFCS 01)},
PAGES = {272--284},
PUBLISHER = {Springer-Verlag},
year = {2001}
}
@incollection {MR1824582,
AUTHOR = {Goldreich, Oded and Vadhan, Salil},
TITLE = {Comparing entropies in statistical zero knowledge with
applications to the structure of {S}{Z}{K}},
BOOKTITLE = {Fourteenth IEEE Conference on Computational Complexity
(Atlanta, GA, 1999)},
PAGES = {54--73},
PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA},
year = {1999},
MRCLASS = {68Q15},
MRNUMBER = {1 824 582},
}
@incollection {RRV99,
AUTHOR = {Raz, Ran and Reingold, Omer and Vadhan, Salil},
TITLE = {Extracting all the randomness and reducing the error in
{T}revisan's extractors},
BOOKTITLE = {ACM Symposium on Theory of Computing (Atlanta, GA,
1999)},
PAGES = {149--158},
PUBLISHER = {ACM},
ADDRESS = {New York},
year = {1999},
MRCLASS = {68W20},
MRNUMBER = {1 797 473},
}
@TechReport{Vinodchandran00,
author = {N. V. Vinodchandran},
title = {A Note on {NP}$\cap$co-{NP}/poly},
institution = {BRICS, Department of Computer Science, University of Aarhus},
year = {2000},
number = {RS-00-19}
}
@incollection {CaiNeSi99,
AUTHOR = {Cai, Jin-Yi and Nerurkar, Ajay and Sivakumar, D.},
TITLE = {Hardness and hierarchy theorems for probabilistic
quasi-polynomial time},
BOOKTITLE = {ACM Symposium on Theory of Computing (Atlanta, GA,
1999)},
PAGES = {726--735},
PUBLISHER = {ACM},
ADDRESS = {New York},
year = {1999},
MRCLASS = {68Q15},
MRNUMBER = {2001i:68048},
}
@article{BK95,
title = {Designing programs that check their work},
author = {Manuel Blum and Sampath Kannan},
journal = {Journal of the {ACM}},
volume = 42,
number = 1,
pages = {269--291},
year = 1995}
@inproceedings {ImL90,
title = {No Better Ways to Generate Hard {NP} Instances than Picking
Uniformly at Random},
author = {Russell Impagliazzo and Leonid A. Levin},
booktitle = {31st IEE Simposium on Foundations
of Computer Science},
pages = {812--821},
year = 1990}
@article {BenDavidChGoLu92,
author = {S. {Ben-D}avid and B. Chor and O. Goldreich and M. Luby},
title = {On the theory of average-case complexity},
journal = {J. of Computer and System Sciences},
volume =44,
number = 2,
year = 1992,
pages = {193--219}}
@Article{Levin86,
title={Average Case Complete Problems},
author={Leonid A. Levin},
pages={285--286},
journal=sicomp,
year=1986,
month=feb,
volume=15,
number=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}
}
@article{Elias72,
title = {The efficient construction of an unbiased
random sequence},
author = {P. Elias},
year = 1972,
volume = 42,
number = 3,
pages = {865--870},
journal = {Annals of Math. Stat.}}
@TechReport{GNW95,
author = {Oded Goldreich and Noam Nisan and Avi Wigderson},
title = {On {Y}ao's {XOR} lemma},
institution = {{\em Electronic Colloquium on Computational Complexity}},
year = {1995},
number = {TR95--050},
month = {March},
note = {www.eccc.uni-trier.de/}
}
@TechReport{Vadhan98-eccc,
author = {Salil P. Vadhan},
title = {Extracting all the Randomness from a Weakly Random Source},
institution = {Electronic Colloquium on Computational Complexity},
year = {1998},
number = {TR98--047}
}
@InProceedings{Trevisan99,
author = {Luca Trevisan},
title = {Constructions of Near-Optimal Extractors Using
Pseudo-Random Generators},
crossref = {STOC31},
pages = {141--148}
}
@techreport{Trevisan98,
author = {Luca Trevisan},
title = {Constructions of Near-Optimal Extractors Using
Pseudo-Random Generators},
year = {1998},
institution = {Electronic Colloquium on Computational Complexity},
note = {Extended abstract in these proceedings},
number = {TR98-055}
}
@Article{FeF93,
title={Random-Self-Reducibility of Complete Sets},
author={Joan Feigenbaum and Lance Fortnow},
pages={994--1005},
journal=sicomp,
year=1993,
month=oct,
volume=22,
number=5,
source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}
}
@string{cc = compcomp}
@Article{FeigeLu96,
title={On the Hardness of Computing the Permanent of Random Matrices},
author={Uriel Feige and Carsten Lund},
journal=cc,
pages={101--132},
year=1996,
volume=6,
number=2,
source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/cc/cc.bib}
}
@Article{NiW94,
title={Hardness vs Randomness},
author={Noam Nisan and Avi Wigderson},
pages={149--167},
journal={J. Computer \& Systems Sciences},
year=1994,
volume=49,
number=2,
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}
@article {HILL99,
AUTHOR = {H{\r{a}}stad, Johan and Impagliazzo, Russell and Levin, Leonid A. and Luby, Michael},
TITLE = {A pseudorandom generator from any one-way function},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {28},
year = {1999},
NUMBER = {4},
PAGES = {1364--1396},
ISSN = {1095-7111},
MRCLASS = {65C10 (68P25 68Q25 94A60)},
MRNUMBER = {2000b:65010},
MRREVR = {Francesco Fabris},
}
@Article{BlM84,
title={How to Generate Cryptographically Strong Sequences of
Pseudo-Random Bits},
author={Manuel Blum and Silvio Micali},
pages={850--864},
journal=sicomp,
year=1984,
month=nov,
volume=13,
number=4,
preliminary={FOCS::BlumM1982:112},
}
@article{WigdersonZ99,
author = {Avi Wigderson and
David Zuckerman},
title = {Expanders That Beat the Eigenvalue Bound: Explicit Construction
and Applications},
journal = {Combinatorica},
volume = {19},
number = {1},
year = {1999},
pages = {125-138},
ee = {http://dx.doi.org/10.1007/s004930050049},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{AK97,
author = {V. Arvind and J. K{\"o}bler},
title = {On resource-bounded measure and pseudorandomness},
booktitle = {17th Conference on Foundations
of Software Technology and Theoretical Computer Science},
publisher = {LNCS 1346, Springer-Verlag},
pages = {235-249},
year = 1997}
@TechReport{KlivansMe98,
author = {Klivans, Adam and van Melkebeek, Dieter},
title = {Graph Nonisomorphism has Subexponential Size Proofs unless the Polynomial-Time Hierarchy Collapses},
institution = {University of Chicago, Department of Computer Science},
year = {1998},
number = {TR-98-12},
month = {December},
note = {Extended abstract in these proceedings}
}
@inproceedings{KlivansMe99,
author = {Klivans, Adam and van Melkebeek, Dieter},
title = {Graph Nonisomorphism has Subexponential Size Proofs unless the Polynomial-Time Hierarchy Collapses},
booktitle = {Proceedings of 31st ACM Symposium on Theory of Computing},
pages = {659--667},
year = 1999
}
@techreport{Melkebeek98,
author = {van Melkebeek, Dieter},
title = {Derandomizing {A}rthur-{M}erlin Games},
institution = {University of Chicago, Department of Computer Science},
number = {TR98-08},
year = 1998}
@Article{GoldwasserMi84,
title={Probabilistic Encryption},
author={Shafi Goldwasser and Silvio Micali},
pages={270--299},
journal=jcss,
year=1984,
month=apr,
volume=28,
number=2,
}
preliminary={STOC::GoldwasserM1982},
@InProceedings{Yao82,
title={Theory and Applications of Trapdoor Functions},
author={Yao, Andrew},
pages={80--91},
booktitle={23rd } # focs,
organization={IEEE},
year=1982
}
@Proceedings{FOCS2007,
title={48th } # focs,
booktitle={48th IEEE } # focs,
year=2007,
month=oct,
organization={IEEE},
crossrefonly=1,
}
@Proceedings{FOCS23,
title={23rd } # focs,
booktitle={23rd } # focs,
month={3--5 } # nov,
year=1982,
address={Chicago, Illinois},
organization={IEEE},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Article{Zuckerman97,
author = {David Zuckerman},
title = {Randomness-Optimal Oblivious Sampling},
journal = {Random Structures \& Algorithms},
year = {1997},
volume = {11},
number = {4},
pages = {345--367}
}
@Article{GoldreichWi97,
author = {Oded Goldreich and Avi Wigderson},
title = {Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing},
journal = {Random Structures \& Algorithms},
year = {1997},
volume = {11},
number = {4},
pages = {315--343}
}
@InProceedings{TaShma96,
title={On Extracting Randomness From Weak Random Sources},
author={Amnon Ta-Shma},
pages={276--285},
crossref={STOC28},
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@Proceedings{STOC28,
title={28th ACM Symposium on
the Theory of Computing},
booktitle={28th ACM Symposium on
the Theory of Computing},
month={22--24 } # may,
year=1996,
address={Philadelphia, Pennsylvania},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@Proceedings{STOC31,
title={35th ACM Symposium on
the Theory of Computing},
booktitle={35th ACM Symposium on
the Theory of Computing},
month={1--4 } # may,
year=1999,
address={Atlanta, Georgia},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@Proceedings{STOC36,
title={36th ACM Symposium on
the Theory of Computing},
booktitle={36th ACM Symposium on
the Theory of Computing},
month={13--15 } # jun,
year=2004,
address={Chicago, IL},
c-organization={ACM},
key={ACM},
crossrefonly=1,
}
@InProceedings{TaShma98,
author = {Amnon Ta-Shma},
title = {Almost Optimal Dispersers},
booktitle = "30th ACM Symposium on
Theory of Computing",
year = "1998",
organization = "ACM",
address = "Dallas, TX",
month = "May",
pages = "196--202"
}
@InProceedings{Sip83,
author = {Michael Sipser},
title = {Borel sets and circuit complexity},
crossref={STOC15},
pages = {61--69},
}
@InProceedings{Sip83b,
title={A Complexity Theoretic Approach to Randomness},
author={Sipser, Michael},
pages={330--335},
crossref={STOC15},
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@InProceedings{AKS87,
title={Deterministic simulation in LOGSPACE},
author={M. Ajtai and J. Komlos and E. Szemeredi},
pages={132-140},
booktitle={19th ACM Symposium on Theory of Computing (STOC)},
year=1987
}
@InProceedings{Bus87,
title={The {Boolean} Formula Value Problem Is in {ALOGTIME}},
author={Buss, Samuel R.},
pages={123--131},
booktitle={19th ACM Symposium on Theory of Computing (STOC)},
year=1987
}
@Proceedings{STOC15,
title={15th ACM Symposium on Theory of
Computing},
booktitle={15th ACM Symposium on Theory
of Computing},
month={25--27 } # apr,
year=1983,
address={Boston, Massachusetts},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@Article{NiZ96,
title={Randomness is Linear in Space},
author={Noam Nisan and David Zuckerman},
pages={43--52},
journal=jcss,
year=1996,
month=feb,
volume=52,
number=1,
preliminary={STOC::NisanZ1993},
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}
@string{algor={Algorithmica}}
@Article{Zuckerman96,
title={Simulating {BPP} Using a General Weak Random Source},
author={David Zuckerman},
pages={367--391},
journal=algor,
year=1996,
month=oct # "/" # nov,
volume=16,
number={4/5},
source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/misc/algor.bib}
}
@Misc{GoZ97,
author = {Oded Goldreich and David Zuckerman},
title = {Another proof that $\mbox{BPP}\subseteq\mbox{PH}$ (and more)},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR97-045},
month = {September},
year = {1997}
}
@article {ACR99,
AUTHOR = {Alexander E. Andreev, Andrea E. F. Clementi and Jos� D. P. Rolim},
TITLE = {Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs},
JOURNAL = {Theoretical Computer Science},
VOLUME = {221},
year = {1999},
NUMBER = {3-18},
PAGES = {189--201},
}
%ICALP05 editor taken out editor={Lu�s Caires and Giuseppe F. Italiano and Lu�s Monteiro and Catuscia Palamidessi and Moti Yung},
@Proceedings{ICALP05,
title={32th } # icalp,
booktitle={32th } # icalp,
address={Lisboa, Portugal},
month={11--5~} # jul,
volume = {3580},
year=2005,
series=lncs,
publisher={Springer-Verlag},
crossrefonly=1
}
@Proceedings{ICALP97,
editor={Pierpaolo Degano and Robert Gorrieri and Alberto
Marchetti-Spaccamela},
title={Automata, Languages and Programming, 24th Colloquium},
booktitle={Automata, Languages and Programming, 24th Colloquium},
address={Bologna, Italy},
month={7--11~} # jul,
year=1997,
series=lncs,
volume=1256,
publisher={Springer-Verlag},
comment={ISBN 3-540-63165-8},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/icalp/icalp.bib}
}
@Article{SanthaVa86,
title={Generating Quasi-random Sequences from Semi-random Sources},
author={Miklos Santha and Umesh V. Vazirani},
pages={75--87},
journal=jcss,
year=1986,
month=aug,
volume=33,
number=1,
preliminary={FOCS::SanthaV1984},
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}
@InProceedings{Vazirani87b,
title={Efficiency Considerations in Using Semi-random Sources},
author={Vazirani, Umesh V.},
pages={160--168},
booktitle={19th ACM Symposium on Theory of Computing (STOC)},
year=1987
}
@InProceedings{VaziraniVa85,
title={Random Polynomial Time Is Equal to Slightly-random Polynomial
Time},
author={Vazirani, Umesh V. and Vazirani, Vijay V.},
pages={417--428},
crossref={FOCS26},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Article{Vazirani87a,
author = {Umesh V. Vazirani},
title = {Strong communication complexity or generating quasirandom sequences from two communicating semirandom sources},
journal = {Combinatorica},
year = {1987},
volume = {7},
number = {4},
pages = {375--392}
}
@Article{ChorGo88,
title={Unbiased Bits from Sources of Weak Randomness and Probabilistic
Communication Complexity},
author={Benny Chor and Oded Goldreich},
pages={230--261},
journal=sicomp,
year=1988,
month=apr,
volume=17,
number=2,
source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}
}
@article {vonNeumann51,
author = {John von Neumann},
title = {Various techniques used in connection with random digits},
journal = {National Bureau of Standards, Applied Mathematics Series},
volume = 12,
pages = {36--38},
year = 1951}
@Misc{SrinivasanZu98,
author = "Aravind Srinivasan and David Zuckerman",
title = "Computing with Very Weak Random Sources",
howpublished = "To appear in {\em SIAM Journal on Computing}",
year = "1998"
}
@InProceedings{RaTa97,
title={Tight bounds for depth-two superconcentrators},
author={Jaikumar Radhakrishnan and Amnon {Ta-S}hma},
pages={585--594},
crossref={FOCS38},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@InProceedings{RadhakrishnanTa97,
title={Tight bounds for depth-two superconcentrators},
author={Jaikumar Radhakrishnan and Amnon {Ta-S}hma},
pages={585--594},
crossref={FOCS38},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@article{NaR04,
author = {Moni Naor and
Omer Reingold},
title = {Number-theoretic constructions of efficient pseudo-random
functions},
journal = {J. ACM},
volume = {51},
number = {2},
year = {2004},
pages = {231-262},
ee = {http://doi.acm.org/10.1145/972639.972643},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@InProceedings{NaR97,
author = "Moni Naor and Omer Reingold",
title = "Number-Theoretic Constructions of Efficient Pseudo-Random Functions",
pages = "458--467",
crossref={FOCS38}
}
@article{NaorR99,
author = {Moni Naor and
Omer Reingold},
title = {Synthesizers and Their Application to the Parallel Construction
of Pseudo-Random Functions},
journal = {J. Comput. Syst. Sci.},
volume = {58},
number = {2},
year = {1999},
pages = {336-375},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@Proceedings{FOCS38,
title={38th Symposium on Foundations of Computer Science},
booktitle={38th Symposium on Foundations of Computer
Science},
month={20--22 } # oct,
year=1997,
address={Miami Beach, Florida},
organization={IEEE},
crossrefonly=1,
pubinfo={IEEE Computer Society Press Order Number PR08197; IEEE Order
Plan Catalog Number 97CH36130; ISBN 0-8186-8197-7; ISBN 0-8186-8198-5
(case); ISBN 0-8186-8199-3 (microfiche); ISSN 0272-5428},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Article{SaksSrZh98,
title={Explicit {OR}-Dispersers with Polylogarithmic Degree},
author={Michael Saks and Aravind Srinivasan and Shiyu Zhou},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={123--154},
year=1998,
volume=45,
number=1
}
@PhdThesis{Spielman95,
author = {Daniel Spielman},
title = {Computationally Efficient Error-Correcting Codes and Holographic Proofs},
school = {Massachusetts Institute of Technology},
year = {1995}
}
@PhdThesis{Fortnow89,
author = {Lance Fortnow},
title = {Complexity-theoretic aspects of interactive proof systems},
school = {Massachusetts Institute of Technology},
note = {Tech Report MIT/LCS/TR-447},
year = {1989}
}
@PhdThesis{Tor88,
author = {Jacobo Tor{\'a}n},
title = {Structural properties of the counting hierarchies},
school = {Facultat d'Informatica de Barcelona, Barcelona, Spain},
year = {1988}
}
@book{Has87,
author = {Johan H{\r{a}}stad},
title = {Computational limitations of small-depth circuits},
year = {1987},
isbn = {0262081679},
publisher = {MIT Press},
}
@PhdThesis{Vazirani86,
author = {Umesh V. Vazirani},
title = {Randomness, Adversaries, and Computation},
school = {University of California, Berkeley},
year = {1984}
}
@Misc{GoldreichWi94,
author = {Oded Goldreich and Avi Wigderson},
title = {Tiny Families of Functions with Random Properties: A Quality-Size Trade-off for Hashing},
howpublished = {{\em Electronic Colloquium on Computational Complexity}, Technical Report TR94-002},
year = {1994}
}
@InProceedings{ILL89,
title={Pseudo-random Generation from one-way functions},
author={Impagliazzo, Russell and Levin, Leonid A. and Luby, Michael},
pages={12--24},
crossref={STOC21},
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@article {Alon86,
AUTHOR = {Alon, N.},
TITLE = {Eigenvalues, geometric expanders, sorting in rounds, and
{R}amsey theory},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal of the J{\'a}nos Bolyai
Mathematical Society},
VOLUME = {6},
year = {1986},
NUMBER = {3},
PAGES = {207--219},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {05C55 (05B05 68R10)},
MRNUMBER = {88g:05090},
MRREVR = {Pavol Hell},
}
@InProceedings{Nisan96,
title={Extracting Randomness: How and Why: A Survey},
author={Noam Nisan},
pages={44--58},
crossref={SCTC96},
source={http://theory.lcs.mit.edu/~dmjones/hbp/sctc/concur.bib}
}
@Proceedings{SCTC96,
title={Proceedings, Eleventh IEEE Conference on Computational
Complexity},
booktitle={Proceedings, Eleventh IEEE Conference on
Computational Complexity},
address={Philadelphia, Pennsylvania},
month={24--27~} # may,
year=1996,
publisher={IEEE Computer Society Press},
crossrefonly=1,
comment={checked},
source={http://theory.lcs.mit.edu/~dmjones/hbp/sctc/concur.bib}
}
@Article{NisanTa99,
author = {Noam Nisan and Amnon {Ta-Shma}},
title = {Extracting Randomness: A Survey and New Constructions},
journal = {Journal of Computer and System Sciences},
year = {1999},
volume = {58},
number = {1},
pages = {148--173},
month = {February}
}
@Article{AjtaiW89,
author={Miklos Ajtai and Avi Wigderson},
title={Deterministic simulation of
probabilistic constant-depth circuits},
journal={Advances in Computing Research -
Randomness and Computation},
volume={5},
pages={199-223},
year={1989}
}
@InCollection{AjtaiKoStSz89,
author = {Mikl{\'o}s Ajtai and J{\'a}nos Koml{\'o}s and William Steiger and Endre Szemer{\'e}di},
title = {Almost Sorting in One Round},
booktitle = {Randomness and Computation},
pages = {117--125},
publisher = {JAI Press Inc.},
year = {1989},
editor = {Silvio Micali},
volume = {5},
series = {Advances in Computing Research}
}
@Article{Pippenger87,
title={Sorting and Selecting in Rounds},
author={Nicholas Pippenger},
pages={1032--1038},
journal=sicomp,
year=1987,
month=dec,
volume=16,
number=6,
source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}
}
@Book{AlonSpEr92,
author = {Noga Alon and Joel H. Spencer and Paul Erd{\H{o}}s},
title = {The Probabilistic Method},
publisher = {John Wiley and Sons, Inc.},
year = {1992},
series = {Wiley-Interscience Series in Discrete Mathematics and Optimization}
}
@book {Gol01,
AUTHOR = {Goldreich, Oded},
TITLE = {Foundations of Cryptography: Volume 1, Basic Tools},
PUBLISHER = {Cambridge University Press},
year = {2001},
PAGES = {xx+372},
ISBN = {0-521-79172-3},
MRCLASS = {94A60 (68-01 68P25 94-01)},
MRNUMBER = {2004a:94042},
}
@Book{MotwaniRa95,
author = {Rajeev Motwani and Prabhakar Raghavan},
title = {Randomized Algorithms},
publisher = {Cambridge University Press},
year = {1995}
}
@Book{AssmusKe92,
author = "E.F. Assmus and J.D. Key",
title = "Designs and their codes",
publisher = "Cambridge University Press",
year = "1992",
number = "103",
series = "Cambridge Tracts in Mathematics"
}
@Misc{TaShma98b,
author = "Amnon Ta-Shma",
howpublished = "Personal communication",
year = "1998",
month = "August"
}
@InProceedings{Imp95,
title={Hard-core distributions for somewhat hard problems},
author={Russell Impagliazzo},
pages={538--545},
crossref={FOCS36},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Proceedings{FOCS36,
title={36th Symposium on Foundations of Computer Science},
booktitle={36th Symposium on Foundations of Computer
Science},
year=1995,
organization={IEEE},
crossrefonly=1
}
@InProceedings{ImW97,
title={{$\mathit{P} = \mathit{BPP}$} if {$E$} Requires Exponential
Circuits: Derandomizing the {XOR} Lemma},
author={Russell Impagliazzo and Avi Wigderson},
pages={220--229},
booktitle={29th } # stoc,
year=1997,
publisher={ACM}
}
@Proceedings{STOC29,
title={29th ACM Symposium on
Theory of Computing},
booktitle={29th ACM Symposium on
Theory of Computing},
month={4--6 } # may,
year=1997,
address={El Paso, Texas},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@inproceedings{ACR97,
author = {Andreev, Alexander and Clementi, Andrea and Rolim, Jos{\'e}},
title = {Worst-case hardness suffices for
derandomization: a new method for hardness-randomness trade-offs},
booktitle = {Proceedings of ICALP'97},
year = 1997,
pages = {177-187},
publisher = {LNC 1256S, Springer-Verlag}
}
@article {BFMT00,
title = {Using autoreducibility to separate complexity classes},
author = {H. Buhrman and L. Fortnow and D. van Milkebeek
and L. Torenvliet},
journal = sicomp,
volume = 29,
year = 2000,
pages = {1497--1520}}
@Article{BFNW93,
title={{BPP} Has Subexponential Time Simulations Unless {EXPTIME} has
Publishable Proofs},
author={L{\'a}szl{\'o} Babai and Lance Fortnow and Noam Nisan and Avi
Wigderson},
journal=cc,
pages={307--318},
year=1993,
volume=3,
number=4,
source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/cc/cc.bib}
}
@book{CoverThomas06,
author = {Thomas Cover and Joy Thomas},
title = {Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)},
year = {2006},
isbn = {0471241954},
publisher = {Wiley-Interscience},
}
@article {ImW01,
AUTHOR = {Impagliazzo, Russell and Wigderson, Avi},
TITLE = {Randomness vs time: derandomization under a uniform
assumption},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {63},
year = {2001},
NUMBER = {4},
PAGES = {672--688},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15 (68Q10)},
MRNUMBER = {MR1894528 (2003e:68039)},
MRREVIEWER = {Johan H{\aa}stad},
}
@inproceedings{GuS00,
author = {Venkatesan Guruswami and Madhu Sudan},
title = {List decoding algorithms for certain concatenated codes},
crossref = {STOC32},
pages = {181--190}
}
@TechReport{GuruswamiSu98,
author = {Venkatesan Guruswami and Madhu Sudan},
title = {Improved Decoding of {R}eed-{S}olomon and
Algebraic-Geometric codes},
institution = {Electronic Colloquium on Computational Complexity},
year = {1998},
number = {98--043}
}
@techreport{Goldreich-candidate2000,
author = {Goldreich, Oded},
title = {Candidate One-Way Functions Based on Expander Graphs},
howpublished = {TR00-090},
institution = {Electronic Colloquium on Computational Complexity},
year = {2000}
}
@InProceedings{GoL89,
title={A Hard-Core Predicate for all One-Way Functions},
author={Goldreich, Oded and Levin, Leonid},
pages={25--32},
booktitle={21st ACM } # stoc,
year=1989
}
@Proceedings{STOC21,
title={Twenty First ACM Symposium on Theory
of Computing},
booktitle={21st ACM } # stoc,
month={15--17 } # may,
year=1989,
address={Seattle, Washington},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@InProceedings{BeaverFe90,
title={Hiding Instances in Multioracle Queries},
author={Donald Beaver and Joan Feigenbaum},
crossref={STACS90},
pages={37--48},
source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/stacs/stacs.bib}
}
@Proceedings{STACS90,
title={7th Symposium on Theoretical Aspects of Computer
Science},
booktitle={7th Symposium on Theoretical Aspects of Computer
Science},
year=1990,
series=lncs,
volume=415,
publisher={Springer},
comment={ISBN 3-540-52282-4},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/bibs/ley/stacs/stacs.bib}
}
@InProceedings{GemmellLiRuSuWi91,
title={Self-Testing/Correcting for Polynomials and for Approximate
Functions},
author={Gemmell, Peter and Lipton, Richard and Rubinfeld, Ronitt and
Sudan, Madhu and Wigderson, Avi},
pages={32--42},
crossref={STOC23},
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@Proceedings{STOC23,
title={Twenty Third ACM Symposium on Theory
of Computing},
booktitle={Twenty Third ACM Symposium on
Theory of Computing},
month={6--8 } # may,
year=1991,
address={New Orleans, Louisiana},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@string{jcomp = {Journal of Complexity}}
@Article{Sudan97,
title={Decoding of {Reed} {Solomon} Codes beyond the Error-Correction
Bound},
author={Madhu Sudan},
pages={180--193},
journal=jcomp,
year=1997,
month=mar,
volume=13,
number=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcomp/jcomp.bib}
}
@InProceedings{ArLiRuSu92,
title={Reconstructing Algebraic Functions from Mixed Data},
author={Ar, Sigal and Lipton, Richard J. and Rubinfeld, Ronitt and
Sudan, Madhu},
pages={503--512},
crossref={FOCS33},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Unpublished{Goldreich97-xor,
author = {Oded Goldreich},
title = {Three {XOR} Lemmas --- An Exposition},
note = {Available from http://www.wisdom.weizmann.ac.il/oded/},
year = {1997},
}
@InProceedings{AroraSu97,
title={Improved Low Degree Testing and its Applications},
author={Sanjeev Arora and Madhu Sudan},
pages={485--495},
crossref={STOC29},
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@string{jcomp = {Journal of Complexity}}
@Article{ChG89,
title={On the Power of Two-Point Based Sampling},
author={Benny Chor and Oded Goldreich},
pages={96--106},
journal=jcomp,
year=1989,
volume=5,
number=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcomp/jcomp.bib}
}
@Unpublished{Goldreich97-samp,
author = {Oded Goldreich},
title = {A Computational Perspective on Sampling (survey)},
note = {Available from http://www.wisdom.weizmann.ac.il/oded/},
year = {1997},
month = {May}
}
@Article{GemmellSu92,
title={Highly resilient correctors for polynomials},
author={Peter Gemmell and Madhu Sudan},
pages={169--174},
journal=ipl,
year=1992,
month={28~} # sep,
volume=43,
number=4,
source={http://theory.lcs.mit.edu/~dmjones/hbp/ipl/ipl.bib}
}
@InProceedings{Lipton91,
author = {Richard Lipton},
title = {New Directions in Testing},
booktitle = {Proceedings of DIMACS Workshop on Distributed Computing and Cryptography},
pages = {191--202},
volume = {2},
year = {1991},
publisher = {ACM/AMS}
}
@InProceedings{ChorGoHaFrRuSm85,
title={The Bit Extraction Problem or {t}-Resilient Functions
(Preliminary Version)},
author={Chor, Benny and Goldreich, Oded and H{\r{a}}stad, Johan and
Friedman, Joel and Rudich, Steven and Smolensky, Roman},
pages={396--407},
crossref={FOCS26},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@InProceedings{Friedman92,
title={On the Bit Extraction Problem},
author={Friedman, Joel},
pages={314--319},
crossref={FOCS33},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Proceedings{FOCS33,
title={33rd Symposium on Foundations of Computer Science},
booktitle={33rd Symposium on Foundations of Computer Science},
month={24--27 } # oct,
year=1992,
address={Pittsburgh, Pennsylvania},
organization={IEEE},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@InProceedings{Vazirani85,
title={Towards a Strong Communication Complexity Theory or Generating
Quasi-Random Sequences from Two Communicating Slightly-random Sources},
author={Vazirani, Umesh V.},
pages={366--378},
crossref={STOC17},
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@Proceedings{STOC16,
publisher = "{ACM}",
booktitle = "16th" # stoc,
year = "1984"
}
@Proceedings{STOC17,
title={Seventeenth ACM Symposium on Theory
of Computing},
booktitle={Seventeenth ACM Symposium on
Theory of Computing},
month={6--8 } # may,
year=1985,
address={Providence, Rhode Island},
c-organization={ACM},
key={ACM},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/STOC/stoc.bib}
}
@InProceedings{ReT85,
title={Efficient Parallel Pseudo-Random Number Generation},
author={John H. Reif and J. D. Tygar},
pages={433--446},
crossref={CRYPTO85},
source={http://theory.lcs.mit.edu/~dmjones/hbp/crypto/crypto.bib}
}
@InProceedings{BennettBrRo85,
title={How to Reduce Your Enemy's Information},
author={Charles H. Bennett and Gilles Brassard and Jean-Marc Robert},
pages={468--476},
crossref={CRYPTO85},
source={http://theory.lcs.mit.edu/~dmjones/hbp/crypto/crypto.bib}
}
@Proceedings{CRYPTO85,
title={Advances in Cryptology---CRYPTO~'85},
booktitle={Advances in Cryptology---CRYPTO~'85},
editor={Hugh C. Williams},
series=lncs,
volume=218,
year=1985,
month={18--22~} # aug,
c-address={University of California, Santa Barbara},
publisher={Springer-Verlag, 1986},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/crypto/crypto.bib}
}
@TechReport{GoldreichRuSu98,
author = {Oded Goldreich and Ronitt Rubinfeld and Madhu Sudan},
title = {Learning Polynomials with Queries --- the Highly Noisy Case},
institution = {Electronic Colloquium on Computational Complexity},
year = {1998},
number = {TR98-060},
note = {Preliminary version in FOCS `95}
}
@article{Cai89,
author = {Cai, Jin-Yi},
title = {With Probability One, a Random Oracle Separates PSPACE from
the Polynomial-Time Hierarchy},
journal = {J. Comput. Syst. Sci.},
volume = {38},
number = {1},
year = {1989},
pages = {68-85},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@InProceedings{CaiPaSi99,
author = {Jin-Yi Cai and A. Pavan and D. Sivakumar},
title = {On the Hardness of the Permanent},
booktitle = {16th Symposium on Theoretical Aspects of Computer Science},
pages = {90--99},
year = {1999},
series = {Lecture Notes in Computer Science, Volume 1563},
publisher = {Springer-Verlag},
}
@Misc{Wigderson98,
author = {Avi Wigderson},
title = {Personal communication},
month = {October},
year = {1998}
}
@Misc{KumarSi98,
author = {{S. Ravi} Kumar and D. Sivakumar},
title = {Personal communication},
month = {October},
year = {1998}
}
@Article{GGM86,
title={How to Construct Random Functions},
author={Oded Goldreich and Shafi Goldwasser and Silvio Micali},
area={Theory of Computation},
pages={792--807},
journal=jacm,
month=oct,
year=1986,
volume=33,
number=4,
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@Article{RaR97,
title={Natural Proofs},
author={Alexander Razborov and Steven Rudich},
pages={24--35},
journal=jcss,
year=1997,
month=aug,
volume=55,
number=1,
preliminary={STOC::RazborovR1994},
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}
@Article{Valiant84,
author = {Leslie G. Valiant},
title = {A Theory of the Learnable},
journal = {Communications of the ACM},
year = {1984},
volume = {27},
number = {11},
pages = {1134--1142}
}
@string{tcs = {Theoretical Computer Science}}
@Article{JerrumVaVa86,
title={Random Generation of Combinatorial Structures from a Uniform
Distribution},
author={Marc R. Jerrum and Leslie G. Valiant and Vijay V. Vazirani},
pages={169--188},
journal=tcs,
year=1986,
volume=43,
number={2--3},
source={http://theory.lcs.mit.edu/~dmjones/hbp/tcs/tcs.bib}
}
@TechReport{BellareGoPe98,
author = {Mihir Bellare and Oded Goldreich and Erez Petrank},
title = {Uniform Generation of {NP}-witnesses using an {NP}-oracle},
institution = {Electronic Colloquium on Computational Complexity},
year = {1998},
number = {TR98-032},
month = {June},
note = {To appear in {\it Information and Computation}.}
}
@Book{Pap94,
author = {Christos H. Papadimitriou},
title = {Computational Complexity},
publisher = {Addison--Wesley},
year = {1994},
}
@InProceedings{BellareRo94,
title={Randomness-Efficient Oblivious Sampling},
author={Mihir Bellare and John Rompel},
pages={276--287},
crossref={FOCS35},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Proceedings{FOCS35,
title={35th Symposium on Foundations of Computer Science},
booktitle={35th Symposium on Foundations of Computer
Science},
month={20--22 } # nov,
year=1994,
address={Santa Fe, New Mexico},
organization={IEEE},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Proceedings{FOCS25,
title={25th Symposium on Foundations of Computer Science},
booktitle={25th Symposium on Foundations of Computer Science},
month={24--26 } # oct,
year=1984,
address={Singer Island, Florida},
organization={IEEE},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@article {Rabin80,
AUTHOR = {Rabin, Michael O.},
TITLE = {Probabilistic algorithm for testing primality},
JOURNAL = {J. Number Theory},
FJOURNAL = {Journal of Number Theory},
VOLUME = {12},
year = {1980},
NUMBER = {1},
PAGES = {128--138},
ISSN = {0022-314X},
CODEN = {JNUTA9},
MRCLASS = {10-04 (10A25)},
MRNUMBER = {81f:10003},
MRREVR = {D. H. Lehmer},
}
@article {SolovaySt77,
AUTHOR = {Solovay, R. and Strassen, V.},
TITLE = {A fast {M}onte-{C}arlo test for primality},
JOURNAL = {SIAM J. Comput.},
VOLUME = {6},
year = {1977},
NUMBER = {1},
PAGES = {84--85},
MRCLASS = {10A25 (10-04)},
MRNUMBER = {55 #2732},
MRREVR = {George Marsaglia},
}
@article {KarpLuMa89,
AUTHOR = {Karp, Richard M. and Luby, Michael and Madras, Neal},
TITLE = {Monte Carlo approximation algorithms for enumeration
problems},
JOURNAL = {J. Algorithms},
FJOURNAL = {Journal of Algorithms},
VOLUME = {10},
year = {1989},
NUMBER = {3},
PAGES = {429--448},
ISSN = {0196-6774},
CODEN = {JOALDV},
MRCLASS = {05A15 (03B05 03B35 03D15 68Q25)},
MRNUMBER = {90j:05015},
MRREVR = {D. M. Topkis},
}
@Article{Miller76,
title={Riemann's Hypothesis and Tests for Primality},
author={Gary L. Miller},
pages={300--317},
journal=jcss,
year=1976,
month=dec,
volume=13,
number=3,
preliminary={STOC::Miller1975},
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}
@article {JerrumSi89,
AUTHOR = {Jerrum, Mark and Sinclair, Alistair},
TITLE = {Approximating the permanent},
JOURNAL = {SIAM J. Comput.},
FJOURNAL = sicomp,
VOLUME = {18},
year = {1989},
NUMBER = {6},
PAGES = {1149--1178},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {05C70 (15A15 60J20 68Q20)},
MRNUMBER = {91a:05075},
MRREVR = {David J. Aldous},
}
@article {FischerLyPa85,
AUTHOR = {Fischer, Michael J. and Lynch, Nancy A. and Paterson, Michael
S.},
TITLE = {Impossibility of distributed consensus with one faulty process},
JOURNAL = {J. Assoc. Comput. Mach.},
FJOURNAL = {Journal of the Association for Computing Machinery},
VOLUME = {32},
year = {1985},
NUMBER = {2},
PAGES = {374--382},
ISSN = {0004-5411},
CODEN = {JACOAH},
MRCLASS = {68M10 (68Q10)},
MRNUMBER = {87e:68002},
}
@incollection {Ben-OrLiSa88,
AUTHOR = {{Ben-O}r, M. and Linial, N. and Saks, M.},
TITLE = {Collective coin flipping and other models of imperfect
randomness},
BOOKTITLE = {Combinatorics (Eger, 1987)},
PAGES = {75--112},
PUBLISHER = {North-Holland},
ADDRESS = {Amsterdam},
year = {1988},
MRCLASS = {68Q05 (90D40)},
MRNUMBER = {94f:68076},
MRREVR = {Mark R. Jerrum},
}
@InProceedings{Ben-OrLi85,
title={Collective Coin Flipping, Robust Voting Schemes and Minima of
{Banzhaf} Values},
author={{Ben-O}r, Michael and Linial, Nathan},
pages={408--416},
crossref={FOCS26},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Proceedings{FOCS26,
title={26th Symposium on Foundations of Computer Science},
booktitle={26th Symposium on Foundations of Computer
Science},
month={21--23 } # oct,
year=1985,
address={Portland, Oregon},
organization={IEEE},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@article {LinialLiSa89,
AUTHOR = {Lichtenstein, D. and Linial, N. and Saks, M.},
TITLE = {Some extremal problems arising from discrete control processes},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal on Combinatorics and
the Theory of Computing},
VOLUME = {9},
year = {1989},
NUMBER = {3},
PAGES = {269--287},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {68R10},
MRNUMBER = {91k:68163},
}
@InProceedings{KGY89,
title={Lower Bounds for Pseudorandom Number Generators},
author={Kharitonov, Michael and Goldberg, Andrew V. and Yung, Moti},
pages={242--247},
crossref={FOCS30}
}
@InProceedings{CoW89,
title={Dispersers, Deterministic Amplification, and Weak Random
Sources},
author={Cohen, Aviad and Wigderson, Avi},
pages={14--19},
crossref={FOCS30},
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Proceedings{FOCS30,
title={30th Symposium on Foundations of Computer Science},
booktitle={30th Symposium on Foundations of Computer Science},
month={30 } # oct # {--1 } # nov,
year=1989,
address={Research Triangle Park, North Carolina},
organization={IEEE},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/FOCS/focs.bib}
}
@Article{BennettBrRo88,
title={Privacy Amplification by Public Discussion},
author={Charles H. Bennett and Gilles Brassard and {Jean-Marc}
Robert},
pages={210--229},
journal=sicomp,
year=1988,
month=apr,
volume=17,
number=2,
source={http://theory.lcs.mit.edu/~dmjones/hbp/sicomp/sicomp.bib}
}
@InProceedings{KahnKL88,
title={The Influence of Variables on {Boolean} Functions},
author={Kahn, Jeff and Kalai, Gil and Linial, Nathan},
pages={68--80},
booktitle = {29th } # focs,
year = {1988}
}
@Proceedings{FOCS45,
title={45th Symposium on Foundations of Computer Science},
booktitle={45th Symposium on Foundations of Computer Science},
month={17--19 } # oct,
year=2004,
address={Rome, ITALY},
organization={IEEE},
crossrefonly=1,
}
@Proceedings{FOCS44,
title={44th Symposium on Foundations of Computer Science},
booktitle={44th Symposium on Foundations of Computer Science},
year=2003,
organization={IEEE},
crossrefonly=1,
}
@Unpublished{Dodis00,
author = {Yevgeniy Dodis},
title = {Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping},
note = {ECCC TR039},
month = {April},
year = {2000}
}
@InProceedings{CanettiDoHaKuSa00,
title={Exposure-Resilient Functions and All-Or-Nothing Transforms},
author={Ran Canetti and Yevgeniy Dodis and Shai Halevi and Eyal Kushilevitz and Amit Sahai},
crossref={EUROCRYPT00},
source={http://theory.lcs.mit.edu/~dmjones/hbp/eurocrypt/eurocrypt.bib}
}
@Proceedings{EUROCRYPT00,
title={Advances in Cryptology---EUROCRYPT~00},
booktitle={Advances in Cryptology---EUROCRYPT~00},
editor = {Bart Preneel},
year=2000,
month={14--18~} # may,
c-address={Bruges, Belgium},
series=lncs,
publisher={Springer-Verlag},
crossrefonly=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/eurocrypt/eurocrypt.bib}
}
@article {Blum86,
AUTHOR = {Manuel Blum},
TITLE = {Independent unbiased coin flips from a correlated biased
source---a finite state {M}arkov chain},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An Journal of the J{\'a}nos Bolyai
Mathematical Society},
VOLUME = {6},
year = {1986},
NUMBER = {2},
PAGES = {97--108},
ISSN = {0209-9683},
CODEN = {COMBDI},
MRCLASS = {60J10 (68Q20 90D99)},
MRNUMBER = {88e:60079},
MRREVR = {Luc P. Devroye},
}
@InCollection{Ben-OrLi90,
author = {Michael {Ben-O}r and Nathan Linial},
title = {Collective Coin-Flipping},
booktitle = {Randomness and Computation},
pages = {91--115},
publisher = {Academic Press},
year = {1990},
editor = {Silvio Micali},
address = {New York}
}
@InProceedings{Saks96,
title={Randomization and Derandomization in Space-Bounded
Computation},
author={Michael Saks},
pages={128--149},
crossref={SCTC96},
source={http://theory.lcs.mit.edu/~dmjones/hbp/sctc/concur.bib}
}
@Unpublished{DodisSaSm00,
author = {Yevgeniy Dodis and Amit Sahai and Adam Smith},
title = {Optimal Lower Bound for Perfect All-or-Nothing Transforms},
note = {In preparation},
month = {April},
year = {2000}
}
@article {Sho90,
AUTHOR = {Shoup, Victor},
TITLE = {New algorithms for finding irreducible polynomials over finite
fields},
JOURNAL = {Math. Comp.},
FJOURNAL = {Mathematics of Computation},
VOLUME = {54},
year = {1990},
NUMBER = {189},
PAGES = {435--447},
ISSN = {0025-5718},
CODEN = {MCMPAF},
MRCLASS = {11T06 (11Y16)},
MRNUMBER = {90j:11135},
MRREVR = {Melvin M. Sweet},
}
@article {ACRT99,
AUTHOR = {Andreev, Alexander E. and Clementi, Andrea E. F. and Rolim,
Jos{\'e} D. P. and Trevisan, Luca},
TITLE = {Weak random sources, hitting sets, and {B}{P}{P} simulations},
JOURNAL = sicomp,
VOLUME = {28},
year = {1999},
NUMBER = {6},
PAGES = {2103--2116},
ISSN = {1095-7111},
MRCLASS = {68Q15 (65C99 68Q17 94A17)},
MRNUMBER = {2000h:68076},
MRREVIEWER = {Hsien-Kuei Hwang},
}
@article{Valiant84-Majority,
author = {Leslie G. Valiant},
title = {Short Monotone Formulae for the Majority Function},
journal = {J. Algorithms},
volume = {5},
number = {3},
year = {1984},
pages = {363-366},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{HMP06,
author = {Shlomo Hoory and
Avner Magen and
Toniann Pitassi},
title = {Monotone Circuits for the Majority Function},
booktitle = {10th Workshop on
Randomization and Computation, RANDOM},
year = {2006},
pages = {410-425},
publisher = {Springer},
series = lncs,
volume = {4110},
}
@inproceedings{Valiant83,
author = {Valiant, L. G.},
title = {Exponential lower bounds for restricted monotone circuits},
booktitle = {15th ACM } # stoc,
year = {1983},
pages = {110--117},
publisher = {ACM}
}
@article {Valiant79,
AUTHOR = {Valiant, L. G.},
TITLE = {The complexity of computing the permanent},
JOURNAL = {Theoretical Computer Science},
VOLUME = {8},
year = {1979},
NUMBER = {2},
PAGES = {189--201},
ISSN = {0304-3975},
CODEN = {TCSDI},
MRCLASS = {68C25 (15A15)},
MRNUMBER = {80f:68054},
}
@article {Toda91,
AUTHOR = {Toda, Seinosuke},
TITLE = {P{P} is as hard as the polynomial-time hierarchy},
JOURNAL = sicomp,
FJOURNAL = sicomp,
VOLUME = {20},
year = {1991},
NUMBER = {5},
PAGES = {865--877},
ISSN = {0097-5397},
CODEN = {SMJCAT},
MRCLASS = {68Q15},
MRNUMBER = {93a:68047},
MRREVIEWER = {Lane Hemaspaandra},
}
@InProceedings{ImpagliazzoKaWi01,
author = {Russell Impagliazzo and Valentine Kabanets and Avi Wigderson},
title = {In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time},
crossref = {CCC01}
}
@Proceedings{RANDOM2000,
title = {Fourth Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)},
booktitle = {Fourth Workshop on Randomization and Approximation Techniques in Computer Science},
year = {2000},
c-address = {Geneva, Switzerland},
month = {July 14},
crossrefonly = 1
}
@Proceedings{RANDOM2001,
title = {Fifth Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)},
booktitle = {Fifth Workshop on Randomization and Approximation Techniques in Computer Science},
year = {2001},
c-address = {Berkeley, California},
month = {August 18--20},
crossrefonly = 1
}
@Proceedings{CCC01,
booktitle = {16th } # ccc,
year = {2001},
organization = {IEEE},
crossrefonly = 1
}
@Article{SudanTrVa01,
author = {Madhu Sudan and Luca Trevisan and Salil Vadhan},
title = {Pseudorandom Generators without the {XOR} Lemma},
journal = {Journal of Computer and System Sciences},
year = {2001},
volume = {62},
pages = {236--266},
}
@InProceedings{ISW00,
author = {Russell Impagliazzo and Ronen Shaltiel and Avi Wigderson},
title = {Extractors and Pseudo-Random Generators with Optimal Seed Length},
crossref = {STOC32},
pages = {1--10},
month = {May},
c-organization = {ACM},
note = {See also ECCC TR00-009},
}
@Proceedings{STOC32,
title={32th ACM Symposium on Theory of
Computing},
booktitle={32th ACM Symposium on
Theory of Computing},
month={21--23 } # may,
year=2000,
c-address={Portland, Oregon},
c-organization={ACM},
key={ACM},
crossrefonly=1
}
@article{ShU05,
author = {Ronen Shaltiel and Christopher Umans},
title = {Simple extractors for all min-entropies and a new pseudorandom generator},
journal = {J. ACM},
volume = {52},
number = {2},
year = {2005},
issn = {0004-5411},
pages = {172--216},
publisher = {ACM},
OPTnote = {Preliminary version in FOCS42},
}
@InProceedings{ShU01,
author = {Ronen Shaltiel and Christopher Umans},
title = {Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator},
crossref = {FOCS42},
}
@Proceedings{FOCS42,
title={42nd Symposium on Foundations of Computer Science},
booktitle={42nd Symposium on Foundations of Computer
Science},
month={14--17 } # oct,
year=2001,
c-address={Las Vegas, Nevada},
organization={IEEE},
crossrefonly=1,
}
@Article{LundFoKaNi92,
title={Algebraic Methods for Interactive Proof Systems},
author={Carsten Lund and Lance Fortnow and Howard Karloff and Noam
Nisan},
area={Complexity Theory},
pages={859--868},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4,
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@Article{Shamir92,
title={{IP} = {PSPACE}},
author={Adi Shamir},
area={Complexity Theory},
pages={869--877},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4,
preliminary={FOCS::Shamir1990:11},
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@article{ALMSS92,
Author = "S. Arora and C. Lund and R. Motwani and M. Sudan and M. Szegedy",
Title = "Proof verification and hardness of approximation problems",
journal = jacm,
Pages = "501-555",
volume = 45,
number =3,
Year = 1998
}
@Article{AS92,
title={Probabilistic Checking of Proofs: A New Characterization
of~{NP}},
author={S. Arora and S. Safra},
journal=jacm,
pages={70--122},
year=1998,
volume=45,
number=1,
}
@Article{AroraLuMoSuSz98,
title={Proof Verification and the Hardness of Approximation Problems},
author={Sanjeev Arora and Carsten Lund and Rajeev Motwani and Madhu
Sudan and Mario Szegedy},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={501--555},
month=may,
year=1998,
volume=45,
number=3,
keywords={NP-completeness, optimization, proof verification,
randomness},
general-terms={Algorithms, Theory},
cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1},
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@Article{AroraSa98,
title={Probabilistic Checking of Proofs: A New Characterization
of~{NP}},
author={Sanjeev Arora and Shmuel Safra},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={70--122},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Approximation algorithms, complexity hierarchies,
computations on polynomials and finite fields, error-correcting codes,
hardness of approximations, interactive computation, NP-completeness,
probabilistic computation, proof checking, reducibility and
completeness, trade-offs/relations among complexity measures},
general-terms={Algorithms, Theory, Verification},
cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1},
preliminary={focs::AroraS1992},
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}
@incollection {MiltersenViWa99,
AUTHOR = {Miltersen, Peter Bro and Vinodchandran, N. V. and Watanabe,
Osamu},
TITLE = {Super-polynomial versus half-exponential circuit size in the
exponential hierarchy},
BOOKTITLE = {Computing and combinatorics (Tokyo, 1999)},
PAGES = {210--220},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
year = {1999},
MRCLASS = {68Q17},
MRNUMBER = {2000h:68084},
}
@article {KarpLi82,
AUTHOR = {Karp, Richard M. and Lipton, Richard J.},
TITLE = {Turing machines that take advice},
JOURNAL = {L'Enseignement Math{\'e}matique. Revue Internationale. IIe
S{\'e}rie},
VOLUME = {28},
year = {1982},
NUMBER = {3-4},
PAGES = {191--209},
ISSN = {0013-8584},
CODEN = {ENMAAR},
MRCLASS = {68C40 (03D10 94C10)},
MRNUMBER = {84k:68036a},
}
@Book{Sipser97,
author = {Michael Sipser},
title = {Introduction to the Theory of Computation},
publisher = {PWS Publishing},
year = {1997}
}
@article {Babai87,
AUTHOR = {Babai, L{\'a}szl{\'o}},
TITLE = {Random oracles separate {${\rm PSPACE}$} from the
polynomial-time hierarchy},
JOURNAL = ipl,
FJOURNAL = ipl,
VOLUME = {26},
year = {1987},
NUMBER = {1},
PAGES = {51--53}
}
@article {BabaiFoLu91,
AUTHOR = {Babai, L{\'a}szl{\'o} and Fortnow, Lance and Lund, Carsten},
TITLE = {Nondeterministic exponential time has two-prover interactive
protocols},
JOURNAL = {Comput. Complexity},
FJOURNAL = compcomp,
VOLUME = {1},
year = {1991},
NUMBER = {1},
PAGES = {3--40},
MRREVIEWER = {Marius Zimand}
}
@article {FeigeGoLoSaSz96,
AUTHOR = {Feige, Uriel and Goldwasser, Shafi and Lov{\'a}sz, Laszlo and
Safra, Shmuel and Szegedy, Mario},
TITLE = {Interactive proofs and the hardness of approximating cliques},
JOURNAL = jacm,
FJOURNAL = jacm,
VOLUME = {43},
year = {1996},
NUMBER = {2},
PAGES = {268--292},
ISSN = {0004-5411},
MRCLASS = {68Q15 (68Q10 68Q25)},
MRNUMBER = {97h:68037},
MRREVIEWER = {Juraj Hromkovi{\v{c}}},
}
@incollection {Lu00,
AUTHOR = {Lu, Chi-Jen},
TITLE = {Derandomizing {A}rthur-{M}erlin games under uniform
assumptions},
BOOKTITLE = {Algorithms and computation (Taipei, 2000)},
PAGES = {302--312},
PUBLISHER = {Springer},
ADDRESS = {Berlin},
year = {2000},
MRCLASS = {68Q15 (68Q10)},
MRNUMBER = {1 858 372},
}
@article {Kabanets01,
AUTHOR = {Kabanets, Valentine},
TITLE = {Easiness assumptions and hardness tests: trading time for zero
error},
OPTNOTE = {Special issue: Complexity 2000 (Florence)},
JOURNAL = {J. Comput. System Sci.},
FJOURNAL = {Journal of Computer and System Sciences},
VOLUME = {63},
year = {2001},
NUMBER = {2},
PAGES = {236--252},
ISSN = {0022-0000},
CODEN = {JCSSBM},
MRCLASS = {68Q15},
MRNUMBER = {1 867 124},
}
@misc{Barvinok-Measure2005,
author = {Alexander Barvinok},
title = {Measure Concentration},
year = {2005},
note = {Lecture notes. Available at www.math.lsa.umich.edu/~barvinok/total710.pdf}
}
@misc{ODonnell-boolean2007,
author = {Ryan O'Donnell},
title = {Analysis of Boolean Functions},
year = {2007},
note = {Lecture notes. Available at http://www.cs.cmu.edu/~odonnell/boolean-analysis/}
}
@article{Razborov09,
author = {Alexander A. Razborov},
title = {A Simple Proof of {B}azzi's Theorem},
journal = {ACM Transactions on Computation Theory (TOCT)},
volume = {1},
number = {1},
year = {2009},
ee = {http://doi.acm.org/10.1145/1490270.1490273},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Harper64,
author = {L. H. Harper},
title = {Optimal Assignments of Numbers to Vertices},
publisher = {SIAM},
year = {1964},
journal = {SIAM Journal on Applied Mathematics},
volume = {12},
number = {1},
pages = {131-135}
}
@article{Hart76,
author = {Sergiu Hart},
title = {A note on the edges of the $n$-cube},
journal = {Discrete Mathematics},
volume = {14},
number = {2},
pages = {157--163},
year = {1976}
}
@inproceedings{DubrovI06,
author = {Bella Dubrov and
Yuval Ishai},
title = {On the randomness complexity of efficient sampling},
booktitle = {38th ACM Symposium on Theory of
Computing (STOC)},
year = {2006},
pages = {711-720}
}
@incollection {Adleman78,
AUTHOR = {Adleman, Leonard},
TITLE = {Two theorems on random polynomial time},
BOOKTITLE = {19th } # focs,
PAGES = {75--83},
PUBLISHER = {IEEE},
year = {1978}
}
@inproceedings{Amano09,
author = {Kazuyuki Amano},
title = {Bounds on the Size of Small Depth Circuits for Approximating
Majority},
booktitle = {36th } # icalp,
year = {2009},
publisher = {Springer},
pages = {59-70}
}
@inproceedings{BrodyV10,
author = {Joshua Brody and Elad Verbin},
title = {The Coin Problem, and Pseudorandomness for Branching Programs},
booktitle = {51th } # focs,
published = {IEEE},
year = {2010}
}
@article {Lu02,
AUTHOR = {Lu, Chi-Jen},
TITLE = {Improved pseudorandom generators for combinatorial rectangles},
JOURNAL = {Combinatorica},
VOLUME = {22},
year = {2002},
NUMBER = {3},
PAGES = {417--433}
}
@inproceedings{Aaronson10,
author = {Scott Aaronson},
title = {{BQP} and the polynomial hierarchy},
booktitle = {42nd } # stoc,
year = {2010},
publisher = {ACM},
pages = {141-150}
}
@inproceedings{DodisPT10,
author = {Yevgeniy Dodis and
Mihai P{\v a}tra{\c s}cu and
Mikkel Thorup},
title = {Changing base without losing space},
booktitle = {42nd } # stoc,
year = {2010},
pages = {593-602},
publisher = {ACM}
}
@inproceedings{Stockmeyer83,
author = {Larry J. Stockmeyer},
title = {The Complexity of Approximate Counting},
booktitle = {15th Symposium on Theory
of Computing (STOC)},
year = {1983},
pages = {118-126},
publisher = {ACM}
}
@inproceedings{MekaZ10,
author = {Raghu Meka and
David Zuckerman},
title = {Pseudorandom generators for polynomial threshold functions},
booktitle = {42nd ACM } # stoc,
year = {2010},
pages = {427-436},
publisher = {ACM}
}
@inproceedings{MekaZ09,
author = {Raghu Meka and
David Zuckerman},
title = {Small-Bias Spaces for Group Products},
booktitle = {13th } # random,
year = {2009},
pages = {658-672},
publisher = {Springer},
series = lncs,
volume = {5687}
}
@inproceedings{LovettRTV09,
author = {Shachar Lovett and
Omer Reingold and
Luca Trevisan and
Salil P. Vadhan},
title = {Pseudorandom Bit Generators That Fool Modular Sums},
booktitle = {13th } # random,
year = {2009},
pages = {615-630},
publisher = {Springer},
series = lncs,
volume = {5687}
}
@inproceedings{LovettMS10,
author = {Shachar Lovett, Partha Mukhopadhyay and Amir Shpilka},
title = {Pseudorandom generators for {$CC^0[p]$} and the {F}ourier spectrum of low-degree polynomials over finite fields},
booktitle = {51th } # focs,
publisher = {IEEE},
year = {2010}
}
@inproceedings{DiakonikolasKN10,
title={Bounded Independence Fools Degree-2 Threshold Functions},
author = {Ilias Diakonikolas and Daniel Kane and Jelani Nelson},
booktitle = {51th } # focs,
publisher = {IEEE},
year = {2010}
}
@inproceedings{GopalanOWZ10,
author = {Parikshit Gopalan and
Ryan O'Donnell and
Yi Wu and
David Zuckerman},
title = {Fooling Functions of Halfspaces under Product Distributions},
booktitle = {25th } # ccc,
year = {2010},
pages = {223-234},
publisher = {IEEE}
}
@article{GopalanKS10,
author = {Parikshit Gopalan and
Subhash Khot and
Rishi Saket},
title = {Hardness of Reconstructing Multivariate Polynomials over
Finite Fields},
journal = {SIAM J. Comput.},
volume = {39},
number = {6},
year = {2010},
pages = {2598-2621},
ee = {http://dx.doi.org/10.1137/070705258},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book{HasanhodzicL09-book1,
author = {Andrew Lo and Jasmina Hasanhodzic},
title = {The Heretics of Finance: Conversations with Leading Practitioners of Technical Analysis},
publisher = {Bloomberg},
year = {2009}
}
@book{HasanhodzicL10-book2,
author = {Andrew Lo and Jasmina Hasanhodzic},
title = {The Evolution of Technical Analysis: Financial Prediction from Babylonian Tablets to Bloomberg Terminals},
publisher = {Wiley},
year = {2010}
}
@InProceedings{Zim98,
author = {Marius Zimand},
title = {Efficient Privatization of Random Bits},
booktitle = {``Randomized Algorithms'' satellite workshop of the
23rd Symposium on Mathematical
Foundations of Computer Science},
year = {1998},
note = {Available at http://triton.towson.edu/$\sim$mzimand/pub/rand-privat.ps}
}
@inproceedings{HaitnerRV10,
author = {Iftach Haitner and
Omer Reingold and
Salil P. Vadhan},
title = {Efficiency improvements in constructing pseudorandom generators
from one-way functions},
booktitle = {42nd ACM } # stoc,
year = {2010},
pages = {437-446}
}
@unpublished{Impagliazzo96,
author = {Russell Impagliazzo},
title = {Very strong one-way functions and pseudo-random generators exist relative to a random oracle},
NOTE = {Manuscript},
year = {1996}
}
@article{AlonFWZ95,
author = {Noga Alon and
Uriel Feige and
Avi Wigderson and
David Zuckerman},
title = {Derandomized Graph Products},
journal = compcomp,
volume = {5},
number = {1},
year = {1995},
pages = {60-75},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{RagdeW91,
author = {Prabhakar Ragde and
Avi Wigderson},
title = {Linear-Size Constant-Depth Polylog-Treshold Circuits},
journal = {Inf. Process. Lett.},
volume = {39},
number = {3},
year = {1991},
pages = {143-146},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{GoldwasserS86,
author = {Shafi Goldwasser and
Michael Sipser},
title = {Private Coins versus Public Coins in Interactive Proof Systems},
booktitle = {18th ACM Symposium on Theory
of Computing (STOC)},
year = {1986},
pages = {59-68}
}
@inproceedings{ArmoniSWZ96,
author = {Roy Armoni and
Michael E. Saks and
Avi Wigderson and
Shiyu Zhou},
title = {Discrepancy Sets and Pseudorandom Generators for Combinatorial
Rectangles},
booktitle = {37th } # focs,
publisher = {IEEE},
year = {1996},
pages = {412-421}
}
@inproceedings{Smolensky93,
author = {Roman Smolensky},
title = {On Representations by Low-Degree Polynomials},
booktitle = {34th IEEE } # focs,
year = {1993},
pages = {130-138}
}
@inproceedings{IshaiK02,
author = {Yuval Ishai and
Eyal Kushilevitz},
title = {Perfect Constant-Round Secure Computation via Perfect Randomizing
Polynomials},
booktitle = {Automata, Languages and Programming, 29th Colloquium (ICALP)},
year = {2002},
pages = {244-256},
publisher = {Springer},
series = lncs,
volume = {2380}
}
@inproceedings{IshaiK00,
author = {Yuval Ishai and
Eyal Kushilevitz},
title = {Randomizing Polynomials: A New Representation with Applications
to Round-Efficient Secure Computation},
booktitle = {41st IEEE } # focs,
year = {2000},
pages = {294-304}
}
@inproceedings{GoldwasserGHKR08,
author = {Shafi Goldwasser and
Dan Gutfreund and
Alexander Healy and
Tali Kaufman and
Guy Rothblum},
title = {A (de)constructive approach to program checking},
booktitle = {40th ACM Symposium on Theory of
Computing (STOC)},
year = {2008},
pages = {143-152}
}
@inproceedings{BarakSW03,
author = {Boaz Barak and
Ronen Shaltiel and
Avi Wigderson},
title = {Computational Analogues of Entropy},
booktitle = {7th } # random,
year = {2003},
pages = {200-215}
}
@inproceedings{BernsteinV93,
author = {Ethan Bernstein and
Umesh Vazirani},
title = {Quantum complexity theory},
booktitle = {25th ACM Symposium on Theory
of Computing (STOC)},
year = {1993},
pages = {11-20}
}
@article{BernsteinV97,
author = {Ethan Bernstein and
Umesh V. Vazirani},
title = {Quantum Complexity Theory},
journal = {SIAM J. Comput.},
volume = {26},
number = {5},
year = {1997},
pages = {1411-1473},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{RazR99,
author = {Ran Raz and
Omer Reingold},
title = {On Recycling the Randomness of States in Space Bounded Computation},
booktitle = {31st ACM } # stoc,
year = {1999},
pages = {159-168}
}
@inproceedings{Watrous00,
author = {John Watrous},
title = {Succinct quantum proofs for properties of finite groups},
booktitle = {41st IEEE } # focs,
year = {2000},
pages = {537-546}
}
@inproceedings{KinneMS09,
author = {Jeff Kinne and
Dieter van Melkebeek and
Ronen Shaltiel},
title = {Pseudorandom Generators and Typically-Correct Derandomization},
booktitle = {12th Workshop on Approximation, Randomization, and Combinatorial Optimization (RANDOM)},
pages = {574-587},
publisher = {Springer},
series = lncs,
volume = {5687},
year = {2009},
}
@inproceedings{Williams10,
author = {Ryan Williams},
title = {Improving exhaustive search implies superpolynomial lower
bounds},
booktitle = {42nd ACM } # stoc,
year = {2010},
pages = {231-240}
}
@inproceedings{Williams10acc,
author = {Ryan Williams},
title = {Non-uniform {ACC} lower bounds},
booktitle = ccc,
year = {2011}
}
@article{GoldreichGN10,
author = {Oded Goldreich and
Shafi Goldwasser and
Asaf Nussboim},
title = {On the Implementation of Huge Random Objects},
journal = {SIAM J. Comput.},
volume = {39},
number = {7},
year = {2010},
pages = {2761-2822},
ee = {http://dx.doi.org/10.1137/080722771},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{AmbainisSTVW03,
author = {Andris Ambainis and
Leonard J. Schulman and
Amnon Ta-Shma and
Umesh V. Vazirani and
Avi Wigderson},
title = {The Quantum Communication Complexity of Sampling},
journal = {SIAM J. Comput.},
volume = {32},
number = {6},
year = {2003},
pages = {1570-1585},
ee = {http://epubs.siam.org/sam-bin/dbq/article/35476},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book{Goldreich08Complexity,
title ={Computational Complexity: A Conceptual Perspective},
author = {Oded Goldreich},
year = {2008},
publisher ={Cambridge University Press}
}
@misc{McEliece78,
author={Robert McEliece},
title={A Public-Key Cryptosystem Based On Algebraic Coding Theory},
note = {DSN Progress Report 42-44},
year={1978}
}
@misc{GalHKPV10,
author ={Anna G\'al and Kristoffer Arnsfelt Hansen and
Michal Kouck\'{y} and Pavel Pudl\'{a}k and Emanuele Viola},
title = {New codes},
year = {2010},
note = {Work in progress}
}
@misc{Aaronson2010-counter,
author = "S. Aaronson",
title = "A counterexample to the {Generalized Linial-Nisan Conjecture}",
howpublished = "Electronic Colloquium on Computational Complexity, Technical Report 109",
year = "2010"
}
@book{DaemenR02,
author = {Joan Daemen and Vincent Rijmen},
publisher = {Springer Verlag},
title = {The Design of Rijndael: {AES} - The Advanced Encryption Standard},
year = 2002
}
@article{LubyR88,
author = {Michael Luby and
Charles Rackoff},
title = {How to Construct Pseudorandom Permutations from Pseudorandom
Functions},
journal = {SIAM J. Comput.},
volume = {17},
number = {2},
year = {1988},
pages = {373-386}
}
@InCollection{ZimmerJ2004,
author = "Heiko Zimmer and Axel Jantsch",
title = "Error-tolerant interconnect schemes",
booktitle = "{Interconnect-Centric Design for Advanced SoC and
NoC}",
editor = "J. Nurmi and H. Tenhunen and J. Isoaho and A.
Jantsch",
ISBN = "1-4020-7835-8",
publisher = "Kluwer Academic Publishers",
year = "2004",
pages = "155--170"
}
@inproceedings{Lu06,
author = {Chi-Jen Lu},
title = {On the Complexity of Parallel Hardness Amplification for One-Way Functions},
booktitle = {3rd Theory of Cryptography Conference (TCC)},
year = {2006},
pages = {462-481}
}
@inproceedings{BronsonJP11,
author = {Josh Bronson and Ali Juma and Periklis A. Papakonstantinou},
title = {Limits on the Stretch of Non-Adaptive Constructions of Pseudo-Random Generators},
booktitle = {8th Theory of Cryptography Conference (TCC)},
year = {2011}
}
I stop putting the conference number, just the year.
@inproceedings{GuruswamiI01,
author = {Venkatesan Guruswami and
Piotr Indyk},
title = {Expander-Based Constructions of Efficiently Decodable Codes},
booktitle = focs,
year = {2001},
pages = {658-667},
publisher = {IEEE}
}
@article{Pudlak94,
author = {Pavel Pudl{\'a}k},
title = {Communication in Bounded Depth Circuits},
journal = {Combinatorica},
volume = {14},
number = {2},
year = {1994},
pages = {203-216}
}
@article{PudlakR94,
author = {Pavel Pudl{\'a}k and
Vojtech R{\"o}dl},
title = {Some combinatorial-algebraic problems from complexity theory},
journal = {Discrete Mathematics},
volume = {136},
number = {1-3},
year = {1994},
pages = {253-279}
}
@article{EvenGLNV98,
author = {Guy Even and
Oded Goldreich and
Michael Luby and
Noam Nisan and
Boban Velickovic},
title = {Efficient approximation of product distributions},
journal = {Random Struct. Algorithms},
volume = {13},
number = {1},
year = {1998},
pages = {1-16},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{GoldreichILVZ90,
author = {Oded Goldreich and
Russell Impagliazzo and
Leonid A. Levin and
Ramarathnam Venkatesan and
David Zuckerman},
title = {Security Preserving Amplification of Hardness},
booktitle = {31st IEEE Symposium on Foundations of Computer Science (FOCS)},
year = {1990},
pages = {318-326}
}
@book{Goldreich10,
AUTHOR = {Goldreich, Oded},
TITLE = {Pseudorandom Generators: A Primer},
SERIES = {University Lecture Series},
VOLUME = {55},
PUBLISHER = {AMS},
year = {2010}
}
@misc{Radziszowski-SmallRamseyNumbers,
author={Stanislaw Radziszowski},
title={Small Ramsey Numbers},
journal={The Electronic Journal of Combinatorics},
year={2009},
note={Dynamic Survey}
}
@misc{BosKaihara10,
author={Joppe Bos and Marcelo Kaihara},
year={2010},
title={PlayStation $3$ computing breaks $2^{60}$ barrier: $112$-bit prime {ECDLP} solved},
misc={EPFL Laboratory for cryptologic algorithms - LACAL, http://lacal.epfl.ch/112bit$\_$prime}
}
@PhdThesis{Williams07,
author = {Ryan Williams},
title = {Algorithms and Resource Requirements for Fundamental Problems},
school = {Carnegie Mellon University},
year = {2007}
}
@inproceedings{Rao09,
author = {Anup Rao},
title = {Extractors for Low-Weight Affine Sources},
booktitle = ccc,
year = {2009},
publisher = {IEEE},
pages = {95-101}
}
@inproceedings{ImpagliazzoK10,
author = {Russell Impagliazzo and
Valentine Kabanets},
title = {Constructive Proofs of Concentration Bounds},
booktitle = random,
year = {2010},
pages = {617-631},
publisher = {Springer}
}
@article{PanconesiS97,
author = {Alessandro Panconesi and
Aravind Srinivasan},
title = {Randomized Distributed Edge Coloring via an Extension of
the Chernoff-Hoeffding Bounds},
journal = {SIAM J. Comput.},
volume = {26},
number = {2},
year = {1997},
pages = {350-368},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{ODonnellSS05,
author = {Ryan O'Donnell and
Michael E. Saks and
Oded Schramm and
Rocco A. Servedio},
title = {Every decision tree has an influential variable},
booktitle = focs,
year = {2005},
pages = {31-39},
publisher = {IEEE}
}
@article{Lee10,
author = {Homin K. Lee},
title = {Decision Trees and Influence: an Inductive Proof of the OSSS Inequality},
year = {2010},
pages = {81-84},
publisher = {Theory of Computing},
journal = {Theory of Computing},
volume = {6},
number = {1}
}
@inproceedings{TrevisanV00,
author = {Luca Trevisan and
Salil Vadhan},
title = {Extracting Randomness from Samplable Distributions},
booktitle = focs,
year = {2000},
pages = {32-42}
}
@article{RazRV02,
author = {Ran Raz and
Omer Reingold and
Salil P. Vadhan},
title = {Extracting all the Randomness and Reducing the Error in
{T}revisan's Extractors},
journal = {J. Comput. Syst. Sci.},
volume = {65},
number = {1},
year = {2002},
pages = {97-128},
ee = {http://dx.doi.org/10.1006/jcss.2002.1824},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@PhDThesis{Dodis00,
author = {Yevgeniy Dodis},
title = {Exposure-Resilient Cryptography},
year = {2000},
school = {Massachusetts Institute of Technology}
}
@article{KampRVZ11,
author = {Jesse Kamp and
Anup Rao and
Salil P. Vadhan and
David Zuckerman},
title = {Deterministic extractors for small-space sources},
journal = {J. Comput. Syst. Sci.},
volume = {77},
number = {1},
year = {2011},
pages = {191-220},
ee = {http://dx.doi.org/10.1016/j.jcss.2010.06.014},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{KampZ07,
author = {Jesse Kamp and
David Zuckerman},
title = {Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient
Cryptography},
journal = {SIAM J. Comput.},
volume = {36},
number = {5},
year = {2007},
pages = {1231-1247},
ee = {http://dx.doi.org/10.1137/S0097539705446846},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{BarakKSSW10,
author = {Boaz Barak and
Guy Kindler and
Ronen Shaltiel and
Benny Sudakov and
Avi Wigderson},
title = {Simulating independence: New constructions of condensers,
ramsey graphs, dispersers, and extractors},
journal = {J. ACM},
volume = {57},
number = {4},
year = {2010},
ee = {http://doi.acm.org/10.1145/1734213.1734214},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Bourgain07,
author = {Bourgain, Jean},
affiliation = {Institute for Advanced Study Princeton NJ 08540 USA Princeton NJ 08540 USA},
title = {On the Construction of Affine Extractors},
journal = {Geometric And Functional Analysis},
publisher = {Birkh\"auser Basel},
issn = {1016-443X},
keyword = {Mathematics and Statistics},
pages = {33-57},
volume = {17},
issue = {1},
year = {2007}
}
@inproceedings{Ben-SassonK09,
author = {Eli Ben-Sasson and
Swastik Kopparty},
title = {Affine dispersers from subspace polynomials},
booktitle = stoc,
year = {2009},
pages = {65-74},
ee = {http://doi.acm.org/10.1145/1536414.1536426},
crossref = {DBLP:conf/stoc/2009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@unpublished{Yehudayoff10,
author = {Amir Yehudayoff},
year = {2010},
note={Unpublished manuscript},
title = {Affine extractors over prime fields}
}
@inproceedings{Li11,
title = {A New Approach to Affine Extractors and Dispersers},
booktitle = ccc,
year = {2011},
author ={Xin Li}
}
@inproceedings{Li11b,
title = {Improved Constructions of Three Source Extractors},
booktitle = ccc,
year = {2011},
author ={Xin Li}
}
@article{GabizonRS06,
author = {Ariel Gabizon and
Ran Raz and
Ronen Shaltiel},
title = {Deterministic Extractors for Bit-Fixing Sources by Obtaining
an Independent Seed},
journal = {SIAM J. Comput.},
volume = {36},
number = {4},
year = {2006},
pages = {1072-1094},
ee = {http://dx.doi.org/10.1137/S0097539705447049},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{RothS85,
author = {Ron M. Roth and Gadiel Seroussi},
title = {On generator matrices of {MDS} codes},
journal = {IEEE Transactions on Information Theory},
volume = {31},
issue = {6},
year = {1985},
pages = {826-830}
}
@article{Gerasoulis88,
author = {A. Gerasoulis},
title = {A fast algorithm for the multiplication of generalized {H}ilbert matrices with vectors},
journal = {Mathematics of Computation},
volume = {50},
issue = {181},
year = {1988},
pages = {179-188}
}
@book{vzGG03,
author = {Joachim von zur Gathen and J\"{u}rgen Gerhard},
title = {Modern Computer Algebra},
publisher = {Cambridge University Press},
year = {2003}
}
@article{JakobsenK01,
author = {T. Jakobsen and L.R. Knudsen},
title = {Attacks on Block Ciphers of Low Algebraic Degree},
journal = {Journal of Cryptology},
volume = {14},
pages = {197-210},
year = {2001}
}
@article{BeameBL92,
author = {Beame, Paul and Brisson, Erik and Ladner, Richard},
title = {The complexity of computing symmetric functions using threshold circuits},
journal = {Theor. Comput. Sci.},
volume = {100},
issue = {1},
month = {June},
year = {1992},
issn = {0304-3975},
pages = {253--265},
numpages = {13},
url = {http://portal.acm.org/citation.cfm?id=136251.136262},
doi = {10.1016/0304-3975(92)90372-M},
acmid = {136262},
publisher = {Elsevier Science Publishers Ltd.},
address = {Essex, UK},
}
@article{NaorRR02,
author = {Moni Naor and
Omer Reingold and
Alon Rosen},
title = {Pseudorandom Functions and Factoring},
journal = {SIAM J. Comput.},
volume = {31},
number = {5},
year = {2002},
pages = {1383-1404}
}
@inproceedings{BuLP93,
author = {Joe Buhler and Hendrik Lenstra and Carl Pomerance},
title = {Factoring integers with the number field sieve},
booktitle = {The Development of the Number Field Sieve},
editor = {Arjen Lenstra and Hendrik Lenstra},
series = {Lecture Notes in Mathematics},
publisher = {Springer-Verlag},
volume = {1554},
year = {1993},
pages = {50-94}
}
@article{Dixon81,
author = {John D. Dixon},
title = {Asymptotically fast factorization of integers},
journal = {Mathematics of Computation},
volume = {36},
number = {153},
pages = {255-260},
year = {1981},
publisher = {American Mathematical Society}
}
@inproceedings{SchWD96,
author = {Oliver Schirokauer and Damian Weber and Thomas Denny},
title = {Discrete logarithms: the effectiveness of the index calculus method},
booktitle = {Algorithmic Number Theory},
editor = {Henri Cohen},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
volume = {1122},
year = {1996},
pages = {337-361}
}
@article{BihamS91,
author = {E. Biham and A. Shamir},
title = {Differential cryptanalysis of {D}{E}{S}-like cryptosystems},
journal = {Journal of Cryptology},
volume = {4},
number = {1},
pages = {3-72},
year = {1991}
}
@inproceedings{Matsui94,
author = {M. Matsui},
title = {Linear cryptanalysis method for {D}{E}{S} cipher},
booktitle = {Advances in Cryptology, Proc. Eurocrypt'93},
editor = {T. Helleseth},
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag},
volume = {765},
pages = {386-397},
year = {1994}
}
@book{Rijndael,
AUTHOR = {Joan Daemen and Vincent Rijmen},
TITLE = {The Design of Rijndael},
PUBLISHER = {Springer-Verlag},
year = {2002}
}
@inproceedings{Ny93,
author = {Kaisa Nyberg},
title = {Differentially Uniform Mappings for Cryptography},
booktitle = {EUROCRYPT},
year = {1993},
pages = {55-64}
}
@PhdThesis{DaemenThesis,
author = {Joan Daemen},
title = {Cipher and hash function design strategies based on linear and differential cryptanalysis},
school = {K.U.Leuven},
year = {1995}
}
@inproceedings{Kopparty11,
title = {On the Complexity of Powering in Finite Fields},
author = {Swastik Kopparty},
booktitle = stoc,
year = {2011}
}
@inproceedings{HaitnerHR06,
author = {Iftach Haitner and
Danny Harnik and
Omer Reingold},
title = {Efficient Pseudorandom Generators from Exponentially Hard
One-Way Functions},
booktitle = icalp,
year = {2006},
pages = {228-239}
}
@article{ImpagliazzoPS97,
author = {Russell Impagliazzo and
Ramamohan Paturi and
Michael E. Saks},
title = {Size-Depth Tradeoffs for Threshold Circuits},
journal = {SIAM J. Comput.},
volume = {26},
number = {3},
year = {1997},
pages = {693-707},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{AlonGM03,
author = {Noga Alon and
Oded Goldreich and
Yishay Mansour},
title = {Almost k-wise independence versus k-wise independence},
journal = {Inf. Process. Lett.},
volume = {88},
number = {3},
year = {2003},
pages = {107-110},
ee = {http://dx.doi.org/10.1016/S0020-0190(03)00359-4},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{GaoGPS00,
author = {Shuhong Gao and
Joachim von zur Gathen and
Daniel Panario and
Victor Shoup},
title = {Algorithms for Exponentiation in Finite Fields},
journal = {J. Symb. Comput.},
volume = {29},
number = {6},
year = {2000},
pages = {879-889},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Miltersen98,
author = {Peter Bro Miltersen},
title = {Error Correcting Codes, Perfect Hashing Circuits, and Deterministic
Dynamic Dictionaries},
booktitle = soda,
year = {1998},
pages = {556-563},
ee = {http://doi.acm.org/10.1145/314613.314845},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{GelfandDP73,
author = {S. Gelfand and R. Dobrushin and M. Pinsker},
title = {On the complexity of coding},
booktitle = {2nd International Symposium on Information Theory},
pages = {177-184},
published = {Akademiai Kiado},
year = {1973}
}
@INPROCEEDINGS{KahaleU98,
author={Kahale, N. and Urbanke, R.},
booktitle={International Symposium on Information Theory},
title={On the minimum distance of parallel and serially concatenated codes },
year={1998},
pages={31}
}
@article{BazziMS09,
author = {Louay Bazzi and
Mohammad Mahdian and
Daniel A. Spielman},
title = {The Minimum Distance of Turbo-Like Codes},
journal = {IEEE Transactions on Information Theory},
volume = {55},
number = {1},
year = {2009},
pages = {6-15},
ee = {http://dx.doi.org/10.1109/TIT.2008.2008114},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{BazziM05,
author = {Louay Bazzi and
Sanjoy K. Mitter},
title = {Encoding complexity versus minimum distance},
journal = {IEEE Transactions on Information Theory},
volume = {51},
number = {6},
year = {2005},
pages = {2103-2112},
ee = {http://dx.doi.org/10.1109/TIT.2005.847727},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Spielman96,
author = {Daniel A. Spielman},
title = {Linear-time encodable and decodable error-correcting codes},
journal = {IEEE Transactions on Information Theory},
volume = {42},
number = {6},
year = {1996},
pages = {1723-1731},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{ApplebaumCPS09,
author = {Benny Applebaum and
David Cash and
Chris Peikert and
Amit Sahai},
title = {Fast Cryptographic Primitives and Circular-Secure Encryption
Based on Hard Learning Problems},
booktitle = {CRYPTO},
year = {2009},
pages = {595-618},
ee = {http://dx.doi.org/10.1007/978-3-642-03356-8_35},
crossref = {DBLP:conf/crypto/2009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{ApplebaumBW10,
author = {Benny Applebaum and
Boaz Barak and
Avi Wigderson},
title = {Public-key cryptography from different assumptions},
booktitle = stoc,
year = {2010},
pages = {171-180},
ee = {http://doi.acm.org/10.1145/1806689.1806714},
crossref = {DBLP:conf/stoc/2010},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Peikert09,
author = {Chris Peikert},
title = {Public-key cryptosystems from the worst-case shortest vector
problem: extended abstract},
booktitle = stoc,
year = {2009},
pages = {333-342},
ee = {http://doi.acm.org/10.1145/1536414.1536461},
crossref = {DBLP:conf/stoc/2009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{BellareCK96,
author = {Mihir Bellare and
Ran Canetti and
Hugo Krawczyk},
title = {Pseudorandom Functions Revisited: The Cascade Construction
and Its Concrete Security},
booktitle = focs,
year = {1996},
pages = {514-523},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book{CidMR06,
AUTHOR = {Carlos Cid and Sean Murphy and Matthew Robshaw},
TITLE = {Algebraic Aspects of the Advanced Encryption Standard},
PUBLISHER = {Springer},
year = {2006}
}
@article{Heys02,
author = {Howard M. Heys},
title = {A Tutorial on Linear and Differential Cryptanalysis},
journal = {Cryptologia},
volume = {26},
number = {3},
year = {2002},
pages = {189-221},
}
@article{Applebaum11,
author = {Benny Applebaum},
title = {Pseudorandom Generators with Long Stretch and Low locality
from Random Local One-Way Functions},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
volume = {18},
year = {2011},
pages = {7},
ee = {http://eccc.hpi-web.de/report/2011/007},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Patrascu10,
author = {Mihai P{\v a}tra{\c s}cu},
title = {Towards polynomial lower bounds for dynamic problems},
booktitle = stoc,
year = {2010},
pages = {603-610},
ee = {http://doi.acm.org/10.1145/1806689.1806772},
crossref = {DBLP:conf/stoc/2010},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{BaranDP08,
author = {Ilya Baran and
Erik D. Demaine and
Mihai P{\v a}tra{\c s}cu},
title = {Subquadratic Algorithms for 3SUM},
journal = {Algorithmica},
volume = {50},
number = {4},
year = {2008},
pages = {584-596},
ee = {http://dx.doi.org/10.1007/s00453-007-9036-3},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Pieprzyk91,
author = {Josef Pieprzyk},
title = {On bent permutations},
booktitle = {Proceedings of the International Conference on Finite Fields, Coding Theory, and Advances in Communications and Computing, Las Vegas},
month = {August},
year = {1991}
}
@book{MitzU05,
AUTHOR = {Michael Mitzenmacher and Eli Upfal},
TITLE = {Probability and Computing: Randomized Algorithms and Probabilistic Analysis},
PUBLISHER = {Cambridge University Press},
year = {2005}
}
@inproceedings{PatrascuW10,
author = {Mihai P{\v a}tra{\c s}cu and
Ryan Williams},
title = {On the Possibility of Faster {SAT} Algorithms},
booktitle = SODA,
year = {2010},
pages = {1065-1075},
ee = {http://www.siam.org/proceedings/soda/2010/SODA10_086_patrascum.pdf},
crossref = {DBLP:conf/soda/2010},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{VassilevskaW09,
author = {Virginia Vassilevska and
Ryan Williams},
title = {Finding, minimizing, and counting weighted subgraphs},
booktitle = STOC,
year = {2009},
pages = {455-464},
ee = {http://doi.acm.org/10.1145/1536414.1536477},
crossref = {DBLP:conf/stoc/2009},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@incollection {MaslenR97,
AUTHOR = {Maslen, David K. and Rockmore, Daniel N.},
TITLE = {Generalized {FFT}s---a survey of some recent results},
BOOKTITLE = {Groups and computation, {II} ({N}ew {B}runswick, {NJ}, 1995)},
SERIES = {DIMACS Ser. Discrete Math. Theoret. Comput. Sci.},
VOLUME = {28},
PAGES = {183--237},
PUBLISHER = {Amer. Math. Soc.},
ADDRESS = {Providence, RI},
year = {1997},
MRCLASS = {20C40 (42C10 65T20)},
MRNUMBER = {1444138 (98k:20020)},
MRREVIEWER = {D. F. Holt},
}
@article{GajentaanO95,
author = {Anka Gajentaan and
Mark H. Overmars},
title = {On a Class of ${O}(n^2)$ Problems in Computational Geometry},
journal = {Comput. Geom.},
volume = {5},
year = {1995},
pages = {165-185},
ee = {http://dx.doi.org/10.1016/0925-7721(95)00022-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article {Erickson99,
AUTHOR = {Erickson, Jeff},
TITLE = {Lower bounds for linear satisfiability problems},
JOURNAL = {Chicago J. Theoret. Comput. Sci.},
FJOURNAL = {Chicago Journal of Theoretical Computer Science},
year = {1999},
number = {8}
}
@article {AilonC05,
AUTHOR = {Ailon, Nir and Chazelle, Bernard},
TITLE = {Lower bounds for linear degeneracy testing},
JOURNAL = {J. ACM},
FJOURNAL = {Journal of the ACM},
VOLUME = {52},
year = {2005},
NUMBER = {2},
PAGES = {157--171},
ISSN = {0004-5411},
MRCLASS = {68Q17 (68U05 68W40)},
MRNUMBER = {2147991 (2006d:68061)},
MRREVIEWER = {Stefan Nickel},
DOI = {10.1145/1059513.1059515},
URL = {http://dx.doi.org/10.1145/1059513.1059515},
}
@inproceedings{Shaltiel11,
author = {Ronen Shaltiel},
title = {Dispersers for affine sources with sub-polynomial entropy},
booktitle = focs,
publisher = {IEEE},
year = {2011}
}
@inproceedings{DeW11,
author = {Anindya De and
Thomas Watson},
title = {Extractors and Lower Bounds for Locally Samplable Sources},
booktitle = random,
year = {2011}
}
@article{PaleyZ32,
author = {Paley,R. E. A. C. and Zygmund,A.},
title = {A note on analytic functions in the unit circle},
journal = {Mathematical Proceedings of the Cambridge Philosophical Society},
volume = {28},
number = {03},
pages = {266-272},
year = {1932},
doi = {10.1017/S0305004100010112},
URL = {http://dx.doi.org/10.1017/S0305004100010112},
eprint = {http://journals.cambridge.org/article_S0305004100010112},
}
@inproceedings{GopalanS10,
author = {Parikshit Gopalan and
Rocco A. Servedio},
title = {Learning and Lower Bounds for {AC}$^{\mbox{0}}$ with Threshold
Gates},
booktitle = random,
year = {2010},
pages = {588-601}
}
@inproceedings{Nisan93,
author = {Noam Nisan},
title = {The communication complexity of threshold gates},
booktitle = {Combinatorics, Paul Erd{\H{o}}s is Eighty, number 1 in Bolyai Society Mathematical Studies},
pages = {301-315},
year = {1993}
}
@inproceedings{Dietzfelbinger96,
author = {Martin Dietzfelbinger},
title = {Universal Hashing and $k$-Wise Independent Random Variables
via Integer Arithmetic without Primes},
booktitle = stacs,
year = {1996},
pages = {569-580}
}
@article{DietzfelbingerHKP97,
author = {Martin Dietzfelbinger and
Torben Hagerup and
Jyrki Katajainen and
Martti Penttonen},
title = {A Reliable Randomized Algorithm for the Closest-Pair Problem},
journal = {J. Algorithms},
volume = {25},
number = {1},
year = {1997},
pages = {19-51},
ee = {http://dx.doi.org/10.1006/jagm.1997.0873},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{Valiant75,
author = {Valiant},
title = {On Non-linear Lower Bounds in Computational Complexity},
booktitle = stoc,
year = {1975},
pages = {45-53}
}
@article{Rao07,
author = {Anup Rao},
title = {An Exposition of {B}ourgain's $2$-Source Extractor},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
volume = {14},
number = {034},
year = {2007}
}
@inproceedings{GopalanMRZ11,
author = {Parikshit Gopalan and
Raghu Meka and
Omer Reingold and
David Zuckerman},
title = {Pseudorandom generators for combinatorial shapes},
booktitle = stoc,
year = {2011},
pages = {253-262}
}
@article{FeigeRPU94,
author = {Uriel Feige and
Prabhakar Raghavan and
David Peleg and
Eli Upfal},
title = {Computing with Noisy Information},
journal = {SIAM J. Comput.},
volume = {23},
number = {5},
year = {1994},
pages = {1001-1018},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book {Muroga71,
AUTHOR = {Muroga, Saburo},
TITLE = {Threshold logic and its applications},
PUBLISHER = {Wiley-Interscience},
ADDRESS = {New York},
year = {1971},
PAGES = {xiv+478},
MRCLASS = {94A20},
MRNUMBER = {0439441 (55 \#12334)},
MRREVIEWER = {Jaroslav Moravek},
}
@article {MurogaTT61,
AUTHOR = {Muroga, Saburo and Toda, Iwao and Takasu, Satoru},
TITLE = {Theory of majority decision elements},
JOURNAL = {J. Franklin Inst.},
FJOURNAL = {Journal of the Franklin Institute},
VOLUME = {271},
year = {1961},
PAGES = {376--418},
ISSN = {0016-0032},
MRCLASS = {94.30},
MRNUMBER = {0129520 (23 \#B2556)},
MRREVIEWER = {A. D. Booth},
}
@article {Hastad94,
AUTHOR = {H{\aa}stad, Johan},
TITLE = {On the size of weights for threshold gates},
JOURNAL = {SIAM J. Discrete Math.},
FJOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {7},
year = {1994},
NUMBER = {3},
PAGES = {484--492},
ISSN = {0895-4801},
CODEN = {SJDMEC},
MRCLASS = {68Q25 (68R05 92B20)},
MRNUMBER = {1285585 (95f:68106)},
DOI = {10.1137/S0895480192235878},
URL = {http://dx.doi.org/10.1137/S0895480192235878},
}
@preamble{
"\def\cprime{$'$} "
}
@article {Podolskii09,
AUTHOR = {Podol{\cprime}ski{\u\i}, Vladimir},
TITLE = {Perceptrons of large weight},
JOURNAL = {Problems of Information Transmission},
VOLUME = {45},
year = {2009},
NUMBER = {1},
PAGES = {46--53}
}
@inproceedings{Ben-OrH08,
author = {Michael Ben-Or and
Avinatan Hassidim},
title = {The Bayesian Learner is Optimal for Noisy Binary Search
(and Pretty Good for Quantum as Well)},
booktitle = focs,
year = {2008},
pages = {221-230}
}
@article{MiltersenNSW98,
title = "On Data Structures and Asymmetric Communication Complexity",
journal = jcss,
volume = "57",
number = "1",
pages = "37 - 49",
year = "1998",
issn = "0022-0000",
doi = "10.1006/jcss.1998.1577",
url = "http://www.sciencedirect.com/science/article/pii/S002200009891577X",
author = "Peter Bro Miltersen and Noam Nisan and Shmuel Safra and Avi Wigderson"
}
@MastersThesis{Smirnov88,
author = {D.V. Smirnov},
title = {Shannon's information methods for lower bounds for probabilistic communication complexity},
school = {Moscow University},
year = {1988},
}
@BOOK{Achieser56,
author = {N.I. Achieser},
title = {Theory of Approximation},
publisher = {Frederik Ungar Publishing Co},
year = {1956},
address = {New York}
}
@BOOK{Rivlin74,
author = {Theodore J. Rivlin},
title = {The Chebyshev Polynomials},
publisher = {John Wiley and Sons},
year = {1974}
}
@book{Jukna01,
author = {Stasys Jukna},
title = {Extremal combinatorics - with applications in computer science},
publisher = {Springer},
series = {Texts in theoretical computer science},
year = {2001}
}
@book{HopcroftMU06,
author = {Hopcroft, John E. and Motwani, Rajeev and Ullman, Jeffrey D.},
title = {Introduction to Automata Theory, Languages, and Computation (3rd Edition)},
year = {2006},
isbn = {0321462254},
publisher = {Addison-Wesley Longman Publishing Co., Inc.},
address = {Boston, MA, USA}
}
@misc{Filmus2010,
title = {Smolensky's polynomial method},
author = {Yuval Filmus},
year = {2010},
note = {http://www.cs.toronto.edu/~yuvalf/Smolensky.pdf}
}
@book{Jones97,
author = {Neil D. Jones},
title = {Computability and complexity - from a programming perspective},
publisher = {MIT Press},
series = {Foundations of computing series},
year = {1997},
isbn = {978-0-262-10064-9},
pages = {I-XVI, 1-466}
}
@article{PatrascuD06,
author = {Mihai Patrascu and
Erik D. Demaine},
title = {Logarithmic Lower Bounds in the Cell-Probe Model},
journal = {SIAM J. Comput.},
volume = {35},
number = {4},
year = {2006},
pages = {932-963},
ee = {http://dx.doi.org/10.1137/S0097539705447256},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@book{Sipser-tocBook,
author = {Michael Sipser},
title = {Introduction to the theory of computation},
publisher = {PWS Publishing Company},
year = {1997},
isbn = {978-0-534-94728-6},
pages = {I-XV, 1-396},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{WilliamsW10,
author = {Virginia Vassilevska Williams and
Ryan Williams},
title = {Subcubic Equivalences between Path, Matrix and Triangle
Problems},
booktitle = focs,
year = {2010},
pages = {645-654},
}
@article{PippengerF79,
author = {Nicholas Pippenger and
Michael J. Fischer},
title = {Relations Among Complexity Measures},
journal = jacm,
volume = {26},
number = {2},
year = {1979},
pages = {361-381},
ee = {http://doi.acm.org/10.1145/322123.322138},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{HennieS66,
author = {Fred Hennie and Richard Stearns},
title = {Two-Tape Simulation of Multitape Turing Machines},
journal = jacm,
volume = {13},
issue = {4},
month = {October},
year = {1966},
issn = {0004-5411},
pages = {533--546},
numpages = {14},
url = {http://doi.acm.org/10.1145/321356.321362},
doi = {http://doi.acm.org/10.1145/321356.321362},
acmid = {321362},
publisher = {ACM},
address = {New York, NY, USA},
}
@inproceedings{GurevichS89,
author = {Yuri Gurevich and
Saharon Shelah},
title = {Nearly Linear Time},
booktitle = {Logic at Botik, Symposium on Logical Foundations of
Computer Science},
year = {1989},
pages = {108-118},
ee = {http://dx.doi.org/10.1007/3-540-51237-3_10},
crossref = {DBLP:conf/ershov/1989},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Schnorr78,
author = {Claus-Peter Schnorr},
title = {Satisfiability Is Quasilinear Complete in {NQL}},
journal = jacm,
volume = {25},
number = {1},
year = {1978},
pages = {136-145},
ee = {http://doi.acm.org/10.1145/322047.322060},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{Ben-SassonG11,
author = {Eli Ben-Sasson and
Ariel Gabizon},
title = {Extractors for Polynomials Sources over Constant-Size Fields
of Small Characteristic},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
volume = {18},
year = {2011},
pages = {129},
ee = {http://eccc.hpi-web.de/report/2011/129},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@misc{TaylorC11,
author = {Greg Taylor and George Cox},
title = {Behind Intel's New Random-Number Generator},
year = {2011},
howpublished={http://spectrum.ieee.org/computing/hardware/behind-intels-new-randomnumber-generator}
}
@misc{Brown-dieharder,
author = {Robert G. Brown},
title = {Dieharder},
howpublished={http://www.phy.duke.edu/$~$rgb/General/dieharder.php},
year = {2011}
}
@misc{Marsaglia-diehard,
author = {George Marsaglia},
title = {Diehard},
howpublished={http://www.stat.fsu.edu/pub/diehard/},
year={1995}
}
@inproceedings{Shaltiel11intro,
author = {Ronen Shaltiel},
title = {An Introduction to Randomness Extractors},
booktitle = icalp,
year = {2011},
pages = {21-41},
ee = {http://dx.doi.org/10.1007/978-3-642-22012-8_2},
crossref = {DBLP:conf/icalp/2011-2},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{BarakST03,
author = {Boaz Barak and
Ronen Shaltiel and
Eran Tromer},
title = {True Random Number Generators Secure in a Changing Environment},
booktitle = ches,
year = {2003},
pages = {166-180},
}
@article{Braverman10,
author = {Mark Braverman},
title = {Polylogarithmic independence fools {AC}$^{\mbox{0}}$ circuits},
journal = {J. ACM},
volume = {57},
number = {5},
year = {2010},
ee = {http://doi.acm.org/10.1145/1754399.1754401},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@inproceedings{FredmanS89,
author = {Michael L. Fredman and Michael E. Saks},
title = {The Cell Probe Complexity of Dynamic Data Structures},
booktitle = stoc,
year = {1989},
pages = {345-354}
}
@article{Hsueh-IC08,
author = {Lu, Hsueh-I and Yeh, Chia-Chi},
title = {Balanced parentheses strike back},
journal = talg,
volume = {4},
issue = {3},
month = {July},
year = {2008},
issn = {1549-6325},
pages = {28:1--28:13},
articleno = {28},
numpages = {13},
url = {http://doi.acm.org/10.1145/1367064.1367068},
doi = {http://doi.acm.org/10.1145/1367064.1367068},
acmid = {1367068},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {Succinct data structures, XML document representation},
}
@inproceedings{Jacobson89,
author = {Guy Jacobson},
title = {Space-efficient Static Trees and Graphs},
booktitle = focs,
year = {1989},
pages = {549-554},
ee = {http://doi.ieeecomputersociety.org/10.1109/SFCS.1989.63533},
crossref = {DBLP:conf/focs/FOCS30},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{RadhakrishnanT00,
author = {Jaikumar Radhakrishnan and Amnon Ta-Shma},
title = {Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators},
journal = {SIAM J. Discrete Math.},
volume = {13},
number = {1},
year = {2000},
pages = {2-24},
ee = {http://dx.doi.org/10.1137/S0895480197329508},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{MosselPe05,
AUTHOR = {Mossel, E. and Peres, Y.},
TITLE = {New coins from old: computing with unknown bias},
NOTE = {With an appendix by C. Hillar},
JOURNAL = {Combinatorica},
FJOURNAL = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
VOLUME = {25},
YEAR = {2005},
NUMBER = {6},
PAGES = {707--724},
TITLE_AR = {New coins from old: computing with unknown bias},
TITLE_HT = {New coins from old -- computing with unknown bias},
URL = {http://front.math.ucdavis.edu/0304.5143},
ID_AR = {math.PR/0304143},
catId={papers},
SUBJECTS={comp},
}
@inproceedings{MontanariM08,
AUTHOR = {A. Montanari and E. Mossel},
TITLE = "Smooth Compression, Gallager Bound and Nonlinear Sparse Graph Codes",
booktitle={IEEE International Symposium on Information Theory (ISIT)},
year = {2008},
}
@inproceedings{HarveyHPR07,
author = {N. Harvey and A. E. Holroyd and Y. Peres and D. Romik},
title={Universal Finitary Codes with Exponential Tails},
booktitle = {Proceedings of the London Mathematical Society},
year = {2007},
volume={94},
number={2},
pages={475-496}
}
@article{KhotN06,
author = {Subhash Khot and Assaf Naor},
title = {Nonembeddability theorems via Fourier analysis},
journal={Mathematische Annalen},
volume = {334},
number = {4},
pages = {821-852},
year = {2006}
}
@misc{JunK99,
author={B. Jun and P. Kocher},
title={The {I}ntel random number generator},
year={1999},
howpublished={http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf}
}
@ARTICLE{KangHLYPL01,
author = {Ju-Sung Kang and Seokhie Hong and Sangjin Lee and Okyeon Yi and Choonsik Park and Jongin Lim},
title = {Practical and Provable Security against Differential And Linear Cryptanalysis for Substitution-Permutation Networks},
journal = {ETRI Journal},
year = {2001},
volume = {23},
number = {4},
pages = {158--167}
}
@article{EvenM97,
author = {Shimon Even and Yishay Mansour},
title = {A Construction of a Cipher from a Single Pseudorandom Permutation},
journal = {J. Cryptology},
volume = {10},
number = {3},
year = {1997},
pages = {151-162},
ee = {http://dx.doi.org/10.1007/s001459900025},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
@article{NaorR99-LubyRackoff,
author = {Moni Naor and Omer Reingold},
title = {On the Construction of Pseudorandom Permutations:
{L}uby-{R}ackoff Revisited},
journal = {J. Cryptology},
volume = {12},
number = {1},
year = {1999},
pages = {29-66}
}
@inproceedings{GentryR04,
author = {Craig Gentry and
Zulfikar Ramzan},
title = {Eliminating Random Permutation Oracles in the {E}ven-{M}ansour
Cipher},
booktitle = {ASIACRYPT},
year = {2004},
pages = {32-47}
}
@inproceedings{RamzanR00,
author = {Zulfikar Ramzan and
Leonid Reyzin},
title = {On the Round Security of Symmetric-Key Cryptographic Primitives},
booktitle = {CRYPTO},
year = {2000},
pages = {376-393}
}
@inproceedings{KeliherMT01,
author = {Liam Keliher and
Henk Meijer and
Stafford E. Tavares},
title = {New Method for Upper Bounding the Maximum Average Linear
Hull Probability for {SPN}s},
booktitle = {EUROCRYPT},
year = {2001},
pages = {420-436},
}
@inproceedings{ChoSKLSL04,
author = {Hong-Su Cho and
Soo Hak Sung and
Daesung Kwon and
Jung-Keun Lee and
Jung Hwan Song and
Jongin Lim},
title = {New Method for Bounding the Maximum Differential Probability
for {SPN}s and {ARIA}},
booktitle = {ICISC},
year = {2004},
pages = {21-32},
}
@article{VadhanZ11,
author = {Salil P. Vadhan and Colin Jia Zheng},
title = {Characterizing Pseudoentropy and Simplifying Pseudorandom
Generator Constructions},
journal = {Electronic Colloquium on Computational Complexity (ECCC)},
year = {2011},
number = {TR11--141},
}
@misc{EastlakeSC94,
author = {D. Eastlake and J. Schiller and S. Crocker},
howpublished = {RFC 4086 (Best Current Practice)},
organization = {Internet Engineering Task Force},
publisher = {IETF},
series = {Request for Comments},
title = {{Randomness Requirements for Security}},
url = {http://www.ietf.org/rfc/rfc4086.txt},
year = 2005
}
@book{ChalletMZ04,
author={Challet, D. and Marsili, M. and Zhang, Y.-C.},
title={Minority Games: Interacting Agents in Financial Markets},
publisher={Oxford University press},
year=2004
}
@article{SilvermanSSL00,
journal = {Phys. Rev. A},
numpages = {10},
month = {Mar},
doi = {10.1103/PhysRevA.61.042106},
issue = {4},
author = {Silverman, M. P. and Strange, Wayne and Silverman, Chris and Lipscombe, T. C.},
title = {Tests for randomness of spontaneous quantum decay},
year = {2000},
url = {http://link.aps.org/doi/10.1103/PhysRevA.61.042106},
publisher = {American Physical Society},
pages = {042106},
volume = {61}
}
@article{AndersonSpangler73,
author={Anderson, J. L. and G. W. Spangler},
year=1973,
title="Serial statistics: Is radioactive decay random?"
journal={Physical Chemistry Journal}
volume=77,
pages={3114--3121}
}
@article{TuF03,
journal = {Phys. Rev. E},
numpages = {7},
month = {Jan},
doi = {10.1103/PhysRevE.67.016113},
issue = {1},
author = {Tu, Shu-Ju and Fischbach, Ephraim},
title = {Geometric random inner products: A family of tests for random number generators},
year = {2003},
url = {http://link.aps.org/doi/10.1103/PhysRevE.67.016113},
publisher = {American Physical Society},
pages = {016113},
volume = {67}
}
@article{KhatibCTetal11,
abstract = {{Foldit is a multiplayer online game in which players collaborate and compete to create accurate protein structure models. For specific hard problems, Foldit player solutions can in some cases outperform state-of-the-art computational methods. However, very little is known about how collaborative gameplay produces these results and whether Foldit player strategies can be formalized and structured so that they can be used by computers. To determine whether high performing player strategies could be collectively codified, we augmented the Foldit gameplay mechanics with tools for players to encode their folding strategies as ” recipes” and to share their recipes with other players, who are able to further modify and redistribute them. Here we describe the rapid social evolution of player-developed folding algorithms that took place in the year following the introduction of these tools. Players developed over 5,400 different recipes, both by creating new algorithms and by modifying and recombining successful recipes developed by other players. The most successful recipes rapidly spread through the Foldit player population, and two of the recipes became particularly dominant. Examination of the algorithms encoded in these two recipes revealed a striking similarity to an unpublished algorithm developed by scientists over the same period. Benchmark calculations show that the new algorithm independently discovered by scientists and by Foldit players outperforms previously published methods. Thus, online scientific game frameworks have the potential not only to solve hard scientific problems, but also to discover and formalize effective new strategies and algorithms.}},
author = {Khatib, Firas and Cooper, Seth and Tyka, Michael D. and Xu, Kefan and Makedon, Ilya and Popovi\'{c}, Zoran and Baker, David and Players, Foldit},
doi = {10.1073/pnas.1115898108},
issn = {1091-6490},
journal = {Proceedings of the National Academy of Sciences},
keywords = {collaboration, evolution, fixme, problem-solving},
month = nov,
number = {47},
pages = {18949--18953},
pmid = {22065763},
posted-at = {2011-12-02 15:50:58},
priority = {2},
publisher = {National Academy of Sciences},
title = {{Algorithm discovery by protein folding game players}},
url = {http://dx.doi.org/10.1073/pnas.1115898108},
volume = {108},
year = {2011}
}