@article{Austrin-Hastad/11,
AUTHOR = {Austrin, Per and H{\aa}stad, Johan},
TITLE = {Randomly supported independence and resistance},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {1-27},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {$k$-wise independence, constraint satisfaction, approximation resistance},
URL = {http://dx.doi.org/10.1137/100783534},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Shao-Welch-Pierce-Lee/11,
AUTHOR = {Shao, Cheng and Welch, Jennifer L. and Pierce, Evelyn and Lee, Hyunyoung},
TITLE = {Multiwriter consistency conditions for shared memory registers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {28-62},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {shared memory consistency, regularity, multiwriter registers, quorum systems, mutual exclusion},
URL = {http://dx.doi.org/10.1137/07071158X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gafni-Guerraoui-Pochon/11,
AUTHOR = {Gafni, Eli and Guerraoui, Rachid and Pochon, Bastian},
TITLE = {The complexity of early deciding set agreement},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {63-78},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {distributed algorithm, set agreement, lower bound, message passing system, shared memory system, simulation},
URL = {http://dx.doi.org/10.1137/050640746},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hazan-Krauthgamer/11,
AUTHOR = {Hazan, Elad and Krauthgamer, Robert},
TITLE = {How hard is it to approximate the best Nash equilibrium?},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {79-91},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {game theory, nash equilibrium, hidden clique, logarithmically-restricted np},
URL = {http://dx.doi.org/10.1137/090766991},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ackermann-Goldberg-Mirrokni-Roglin-Vocking/11,
AUTHOR = {Ackermann, Heiner and Goldberg, Paul W. and Mirrokni, Vahab S. and R{\"o}glin, Heiko and V{\"o}cking, Berthold},
TITLE = {Uncoordinated two-sided matching markets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {92-106},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {stable marriage problem, response dynamics, nash equilibrium, convergence},
URL = {http://dx.doi.org/10.1137/090753498},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Urquhart/11,
AUTHOR = {Urquhart, Alasdair},
TITLE = {A near-optimal separation of regular and general resolution},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {107-121},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {resolution, proof complexity, lower bounds},
URL = {http://dx.doi.org/10.1137/090772897},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ishai-Katz-Kushilevitz-Lindell-Petrank/11,
AUTHOR = {Ishai, Yuval and Katz, Jonathan and Kushilevitz, Eyal and Lindell, Yehuda and Petrank, Erez},
TITLE = {On achieving the ``Best of both worlds'' in secure multiparty computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {122-141},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {theory of cryptography, secure computation},
URL = {http://dx.doi.org/10.1137/100783224},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Magniez-Nayak-Roland-Santha/11,
AUTHOR = {Magniez, Fr{\'e}d{\'e}ric and Nayak, Ashwin and Roland, Jeremie and Santha, Miklos},
TITLE = {Search via quantum walk},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {142-164},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {search, markov chain, hitting time, quantum walk, phase estimation, amplitude amplification},
URL = {http://dx.doi.org/10.1137/090745854},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{ODonnell-Servedio/11,
AUTHOR = {O'Donnell, Ryan and Servedio, Rocco A.},
TITLE = {The Chow parameters problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {165-199},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {chow parameters, threshold functions, approximation, learning theory},
URL = {http://dx.doi.org/10.1137/090756466},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Saxena-Seshadhri/11,
AUTHOR = {Saxena, Nitin and Seshadhri, C.},
TITLE = {An almost optimal rank bound for depth-3 identities},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {1},
PAGES = {200-224},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {polynomial identity testing, derandomization, depth-3 circuits},
URL = {http://dx.doi.org/10.1137/090770679},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Haitner-Ishai-Kushilevitz-Lindell-Petrank/11,
AUTHOR = {Haitner, Iftach and Ishai, Yuval and Kushilevitz, Eyal and Lindell, Yehuda and Petrank, Erez},
TITLE = {Black-box constructions of protocols for secure computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {225-266},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {theory of cryptography, secure computation, black-box reductions, oblivious transfer},
URL = {http://dx.doi.org/10.1137/100790537},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ben-Aroya-Ta-Shma/11,
AUTHOR = {Ben-Aroya, Avraham and Ta-Shma, Amnon},
TITLE = {A combinatorial construction of almost-Ramanujan graphs using the zig-zag product},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {267-290},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {expander graphs, zig-zag product, combinatorial construction},
URL = {http://dx.doi.org/10.1137/080732651},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Frieze-Melsted-Mitzenmacher/11,
AUTHOR = {Frieze, Alan and Melsted, P{\'a}ll and Mitzenmacher, Michael},
TITLE = {An analysis of random-walk cuckoo hashing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {291-308},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {hashing, random walk, cuckoo},
URL = {http://dx.doi.org/10.1137/090770928},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Archer-Bateni-Hajiaghayi-Karloff/11,
AUTHOR = {Archer, Aaron and Bateni, MohammadHossein and Hajiaghayi, MohammadTaghi and Karloff, Howard},
TITLE = {Improved approximation algorithms for prize-collecting Steiner tree and TSP},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {309-332},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {approximation algorithms, steiner tree, traveling salesman, prize-collecting},
URL = {http://dx.doi.org/10.1137/090771429},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chan-Patrascu-Roditty/11,
AUTHOR = {Chan, Timothy M. and P{\v{a}}tra{\c{s}}cu, Mihai and Roditty, Liam},
TITLE = {Dynamic connectivity: Connecting to networks and geometry},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {333-349},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {data structures, dynamic graph algorithms, connectivity, computational geometry},
URL = {http://dx.doi.org/10.1137/090751670},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ailon-Chazelle-Clarkson-Liu-Mulzer-Seshadhri/11,
AUTHOR = {Ailon, Nir and Chazelle, Bernard and Clarkson, Kenneth L. and Liu, Ding and Mulzer, Wolfgang and Seshadhri, C.},
TITLE = {Self-improving algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {350-375},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {average case analysis, delaunay triangulation, low entropy, sorting},
URL = {http://dx.doi.org/10.1137/090766437},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldreich-Ron/11,
AUTHOR = {Goldreich, Oded and Ron, Dana},
TITLE = {Algorithmic aspects of property testing in the dense graphs model},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {376-445},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {property testing, adaptivity versus nonadaptivity, graph properties},
URL = {http://dx.doi.org/10.1137/090749621},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gimenez-Godoy-Maneth/11,
AUTHOR = {Gim{\'e}nez, Omer and Godoy, Guillem and Maneth, Sebastian},
TITLE = {Deciding regularity of the set of instances of a set of terms with regular constraints is EXPTIME-complete},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {446-464},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {exptime complexity, regularity, terms with variables, pattern matching, regular constraints},
URL = {http://dx.doi.org/10.1137/090777669},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fischer-Heun/11,
AUTHOR = {Fischer, Johannes and Heun, Volker},
TITLE = {Space-efficient preprocessing schemes for range minimum queries on static arrays},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {465-492},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {range queries, lowest common ancestors, arrays, trees},
URL = {http://dx.doi.org/10.1137/090779759},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cachin-Keidar-Shraer/11,
AUTHOR = {Cachin, Christian and Keidar, Idit and Shraer, Alexander},
TITLE = {Fail-aware untrusted storage},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {493-533},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {cloud storage, integrity, consistency, forking semantics, hashing},
URL = {http://dx.doi.org/10.1137/090751062},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldreich-Ron/11a,
AUTHOR = {Goldreich, Oded and Ron, Dana},
TITLE = {On proximity-oblivious testing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {534-566},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {property testing, graph properties},
URL = {http://dx.doi.org/10.1137/100789646},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ambuhl-Mastrolilli-Svensson/11,
AUTHOR = {Amb{\"u}hl, Christoph and Mastrolilli, Monaldo and Svensson, Ola},
TITLE = {Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {2},
PAGES = {567-596},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {hardness of approximation, graph theory},
URL = {http://dx.doi.org/10.1137/080729256},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Daskalakis-Karp-Mossel-Riesenfeld-Verbin/11,
AUTHOR = {Daskalakis, Constantinos and Karp, Richard M. and Mossel, Elchanan and Riesenfeld, Samantha J. and Verbin, Elad},
TITLE = {Sorting and selection in posets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {597-622},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {chain decomposition, partially ordered sets, query complexity, selection, sorting, transitive relations},
URL = {http://dx.doi.org/10.1137/070697720},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Ghosh-Vassilvitskii/11,
AUTHOR = {Chen, Ning and Ghosh, Arpita and Vassilvitskii, Sergei},
TITLE = {Optimal envy-free pricing with metric substitutability},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {623-645},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {envy-free pricing, algorithm, strong perfect graph theorem},
URL = {http://dx.doi.org/10.1137/080740970},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Niyogi-Smale-Weinberger/11,
AUTHOR = {Niyogi, P. and Smale, S. and Weinberger, S.},
TITLE = {A topological view of unsupervised learning from noisy data},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {646-663},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {topology, data, manifolds},
URL = {http://dx.doi.org/10.1137/090762932},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ta-Shma/11,
AUTHOR = {Ta-Shma, Amnon},
TITLE = {Short seed extractors against quantum storage},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {664-677},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {extractors, quantum storage, random access codes, list-decodable code},
URL = {http://dx.doi.org/10.1137/09076787X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Anshelevich-Karagiozova/11,
AUTHOR = {Anshelevich, Elliot and Karagiozova, Adriana},
TITLE = {Terminal backup, 3D matching, and covering cubic graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {678-708},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {graph packing, simplex matching, cycle cover, network design},
URL = {http://dx.doi.org/10.1137/090752699},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kale-Seshadhri/11,
AUTHOR = {Kale, Satyen and Seshadhri, C.},
TITLE = {An expansion tester for bounded degree graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {709-720},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {sublinear algorithms, random walks, graph expansion},
URL = {http://dx.doi.org/10.1137/100802980},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bodirsky-Fusy-Kang-Vigerske/11,
AUTHOR = {Bodirsky, Manuel and Fusy, {\'E}ric and Kang, Mihyun and Vigerske, Stefan},
TITLE = {Boltzmann samplers, P{\'o}lya theory, and cycle pointing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {721-769},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {unlabeled enumeration, polya theory, boltzmann, random generation, trees, graphs, maps},
URL = {http://dx.doi.org/10.1137/100790082},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Raz/11,
AUTHOR = {Raz, Ran},
TITLE = {A counterexample to strong parallel repetition},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {771-777},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {two-prover games, parallel repetition theorem, odd cycle game},
URL = {http://dx.doi.org/10.1137/090747270},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dvir-Wigderson/11,
AUTHOR = {Dvir, Zeev and Wigderson, Avi},
TITLE = {Kakeya sets, new mergers, and old extractors},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {778-792},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {extractors, kakeya, derandomization},
URL = {http://dx.doi.org/10.1137/090748731},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kasiviswanathan-Lee-Nissim-Raskhodnikova-Smith/11,
AUTHOR = {Kasiviswanathan, Shiva Prasad and Lee, Homin K. and Nissim, Kobbi and Raskhodnikova, Sofya and Smith, Adam},
TITLE = {What can we learn privately?},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {793-826},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {data privacy, probabilistically approximately correct learning, statistical query learning, differential privacy},
URL = {http://dx.doi.org/10.1137/090756090},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Patrascu/11,
AUTHOR = {P{\v{a}}tra{\c{s}}cu, Mihai},
TITLE = {Unifying the landscape of cell-probe lower bounds},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {827-847},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {lower bounds, data structures, cell-probe complexity, range queries},
URL = {http://dx.doi.org/10.1137/09075336X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kempe-Kobayashi-Matsumoto-Toner-Vidick/11,
AUTHOR = {Kempe, Julia and Kobayashi, Hirotada and Matsumoto, Keiji and Toner, Ben and Vidick, Thomas},
TITLE = {Entangled games are hard to approximate},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {848-877},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {interactive proofs, quantum computing, entanglement, almost-commuting matrices},
URL = {http://dx.doi.org/10.1137/090751293},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Guruswami-Hastad-Manokaran-Raghavendra-Charikar/11,
AUTHOR = {Guruswami, Venkatesan and H{\aa}stad, Johan and Manokaran, Rajsekar and Raghavendra, Prasad and Charikar, Moses},
TITLE = {Beating the random ordering is hard: Every ordering CSP is approximation resistant},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {878-914},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {maximum acyclic subgraph, feedback arc set, unique games conjecture, hardness of approximation, integrality gaps},
URL = {http://dx.doi.org/10.1137/090756144},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dhangwatnotai-Dobzinski-Dughmi-Roughgarden/11,
AUTHOR = {Dhangwatnotai, Peerapong and Dobzinski, Shahar and Dughmi, Shaddin and Roughgarden, Tim},
TITLE = {Truthful approximation schemes for single-parameter agents},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {915-933},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {algorithmic mechanism design, algorithm game theory, scheduling},
URL = {http://dx.doi.org/10.1137/080744992},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Friedgut-Kalai-Keller-Nisan/11,
AUTHOR = {Friedgut, Ehud and Kalai, Gil and Keller, Nathan and Nisan, Noam},
TITLE = {A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {3},
PAGES = {934-952},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {gibbardsatterthwaite theorem, arrow theorem, algorithmic game theory},
URL = {http://dx.doi.org/10.1137/090756740},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chan-Fung-Lau-Yung/11,
AUTHOR = {Chan, Yuk Hei and Fung, Wai Shing and Lau, Lap Chi and Yung, Chun Kong},
TITLE = {Degree bounded network design with metric costs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {953-980},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {network design, edge splitting-off, graph connectivity},
URL = {http://dx.doi.org/10.1137/090746495},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Spielman-Teng/11,
AUTHOR = {Spielman, Daniel A. and Teng, Shang-Hua},
TITLE = {Spectral sparsification of graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {981-1025},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {graph laplacian, sparsification, graph partitioning},
URL = {http://dx.doi.org/10.1137/08074489X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dey-Hirani-Krishnamoorthy/11,
AUTHOR = {Dey, Tamal K. and Hirani, Anil N. and Krishnamoorthy, Bala},
TITLE = {Optimal homologous cycles, total unimodularity, and linear programming},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1026-1044},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {computational topology, homology localization, simplicial complex, optimal chain},
URL = {http://dx.doi.org/10.1137/100800245},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sharir-Shaul/11,
AUTHOR = {Sharir, Micha and Shaul, Hayim},
TITLE = {Semialgebraic range reporting and emptiness searching with applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1045-1074},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {range searching, semialgebraic sets, range emptiness, range reporting, random sampling, elementary cell partition, epsilon nets, ray shooting},
URL = {http://dx.doi.org/10.1137/090765092},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gopalan-ODonnell-Servedio-Shpilka-Wimmer/11,
AUTHOR = {Gopalan, Parikshit and O'Donnell, Ryan and Servedio, Rocco A. and Shpilka, Amir and Wimmer, Karl},
TITLE = {Testing Fourier dimensionality and sparsity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1075-1100},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {property testing, fourier spectrum, discrete fourier analysis, local testability},
URL = {http://dx.doi.org/10.1137/100785429},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Lu-Xia/11,
AUTHOR = {Cai, Jin-Yi and Lu, Pinyan and Xia, Mingji},
TITLE = {Computational complexity of Holant problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1101-1132},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {holant problems, holographic reduction, polynomial interpolation, \#p-hardness},
URL = {http://dx.doi.org/10.1137/100814585},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Feige-Mirrokni-Vondrak/11,
AUTHOR = {Feige, Uriel and Mirrokni, Vahab S. and Vondr{\'a}k, Jan},
TITLE = {Maximizing non-monotone submodular functions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1133-1153},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {approximation algorithms, combinatorial optimization, submodular functions, submodular function maximization, local search algorithms, information-theoretic lower bounds},
URL = {http://dx.doi.org/10.1137/090779346},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dvir-Gopalan-Yekhanin/11,
AUTHOR = {Dvir, Zeev and Gopalan, Parikshit and Yekhanin, Sergey},
TITLE = {Matching vector codes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1154-1178},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {locally decodable codes, reedmuller codes, matching vectors},
URL = {http://dx.doi.org/10.1137/100804322},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Burgisser-Landsberg-Manivel-Weyman/11,
AUTHOR = {B{\"u}rgisser, Peter and Landsberg, J.M. and Manivel, Laurent and Weyman, Jerzy},
TITLE = {An overview of mathematical issues arising in the geometric complexity theory approach to $\mathbf{VP}\neq\mathbf{NP}$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {4},
PAGES = {1179-1209},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {geometric complexity theory, $\mathbf{p}$ vs. $\mathbf{np}$, geometric invariant theory, orbit closure, kronecker coefficient, determinant, permanent},
URL = {http://dx.doi.org/10.1137/090765328},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Aland-Dumrauf-Gairing-Monien-Schoppmann/11,
AUTHOR = {Aland, Sebastian and Dumrauf, Dominic and Gairing, Martin and Monien, Burkhard and Schoppmann, Florian},
TITLE = {Exact price of anarchy for polynomial congestion games},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1211-1233},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {atomic unsplittable congestion games, selfish routing, price of anarchy},
URL = {http://dx.doi.org/10.1137/090748986},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mertzios-Sau-Zaks/11,
AUTHOR = {Mertzios, George B. and Sau, Ignasi and Zaks, Shmuel},
TITLE = {The recognition of tolerance and bounded tolerance graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1234-1257},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {tolerance graphs, bounded tolerance graphs, recognition, vertex splitting, np-complete, trapezoid graphs, permutation graphs},
URL = {http://dx.doi.org/10.1137/090780328},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Svensson/11,
AUTHOR = {Svensson, Ola},
TITLE = {Hardness of precedence constrained scheduling on identical machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1258-1274},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {hardness of approximation, scheduling},
URL = {http://dx.doi.org/10.1137/100810502},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ailon-Charikar/11,
AUTHOR = {Ailon, Nir and Charikar, Moses},
TITLE = {Fitting tree metrics: Hierarchical clustering and phylogeny},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1275-1291},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {approximation algorithms, phylogenic reconstructions, hierarchical clustering},
URL = {http://dx.doi.org/10.1137/100806886},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kobler-Kuhnert-Laubner-Verbitsky/11,
AUTHOR = {K{\"o}bler, Johannes and Kuhnert, Sebastian and Laubner, Bastian and Verbitsky, Oleg},
TITLE = {Interval graphs: Canonical representations in logspace},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1292-1315},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {graph isomorphism, graph canonization, logspace, interval graphs, interval hypergraphs, convex graphs, proper interval graphs, unit interval graphs},
URL = {http://dx.doi.org/10.1137/10080395X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{King-Krohn/11,
AUTHOR = {King, James and Krohn, Erik},
TITLE = {Terrain guarding is NP-hard},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1316-1339},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {terrain guarding, guarding monotone chains, np-completeness, art gallery problem, visibility graph},
URL = {http://dx.doi.org/10.1137/100791506},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jiang-Miller-Pritikin/11,
AUTHOR = {Jiang, Tao and Miller, Zevi and Pritikin, Dan},
TITLE = {Near optimal bounds for Steiner trees in the hypercube},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1340-1360},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {steiner trees, hypercube},
URL = {http://dx.doi.org/10.1137/100797473},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gupta-Pal-Ravi-Sinha/11,
AUTHOR = {Gupta, Anupam and P{\'a}l, Martin and Ravi, R. and Sinha, Amitabh},
TITLE = {Sampling and cost-sharing: Approximation algorithms for stochastic optimization problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1361-1401},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {stochastic optimization, approximation algorithms, combinatorial optimization, cost-sharing functions},
URL = {http://dx.doi.org/10.1137/080732250},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cohen-Duffield-Kaplan-Lund-Thorup/11,
AUTHOR = {Cohen, Edith and Duffield, Nick and Kaplan, Haim and Lund, Carsten and Thorup, Mikkel},
TITLE = {Efficient stream sampling for variance-optimal estimation of subset sums},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1402-1431},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {subset sum estimation, weighted sampling, sampling without replacement, reservoir sampling},
URL = {http://dx.doi.org/10.1137/10079817X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gopalan-Guruswami-Raghavendra/11,
AUTHOR = {Gopalan, Parikshit and Guruswami, Venkatesan and Raghavendra, Prasad},
TITLE = {List decoding tensor products and interleaved codes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {5},
PAGES = {1432-1462},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {error-correcting codes, list decoding, johnson bound, tensor product codes, generalized hamming weights},
URL = {http://dx.doi.org/10.1137/090778274},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Haeupler-Sen-Tarjan/11,
AUTHOR = {Haeupler, Bernhard and Sen, Siddhartha and Tarjan, Robert E.},
TITLE = {Rank-pairing heaps},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1463-1485},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {algorithm, data structure, heap, priority queue, amortized analysis},
URL = {http://dx.doi.org/10.1137/100785351},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Haitner-Harnik-Reingold/11,
AUTHOR = {Haitner, Iftach and Harnik, Danny and Reingold, Omer},
TITLE = {On the power of the randomized iterate},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1486-1528},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {cryptography, pseudorandom generator, one-way functions, hardness amplification},
URL = {http://dx.doi.org/10.1137/080721820},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pass-Tseng-Wikstrom/11,
AUTHOR = {Pass, Rafael and Tseng, Wei-Lung Dustin and Wikstr{\"o}m, Douglas},
TITLE = {On the composition of public-coin zero-knowledge protocols},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1529-1553},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {public-coin interactive protocols, zero-knowledge, parallel repetition},
URL = {http://dx.doi.org/10.1137/100811465},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Briest-Krysta/11,
AUTHOR = {Briest, Patrick and Krysta, Piotr},
TITLE = {Buying cheap is expensive: Approximability of combinatorial pricing problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1554-1586},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {combinatorial pricing, approximation algorithms, hardness of approximation},
URL = {http://dx.doi.org/10.1137/090752353},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Briest-Krysta-Vocking/11,
AUTHOR = {Briest, Patrick and Krysta, Piotr and V{\"o}cking, Berthold},
TITLE = {Approximation techniques for utilitarian mechanism design},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1587-1622},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {algorithmic mechanism design, truthful mechanisms, approximation algorithms, combinatorial auctions, unsplittable multicommodity flow routing problem, multiunit auctions},
URL = {http://dx.doi.org/10.1137/090772988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Shalev-Shwartz-Shamir-Sridharan/11,
AUTHOR = {Shalev-Shwartz, Shai and Shamir, Ohad and Sridharan, Karthik},
TITLE = {Learning kernel-based halfspaces with the 0-1 loss},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1623-1646},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {learning halfspaces, kernel methods, learning theory},
URL = {http://dx.doi.org/10.1137/100806126},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kaplan-Katz-Morgenstern-Sharir/11,
AUTHOR = {Kaplan, Haim and Katz, Matthew J. and Morgenstern, Gila and Sharir, Micha},
TITLE = {Optimal cover of points by disks in a simple polygon},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1647-1661},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {geometric covering, minimum disk cover, chordal graphs},
URL = {http://dx.doi.org/10.1137/100808459},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ferns-Panangaden-Precup/11,
AUTHOR = {Ferns, Norm and Panangaden, Prakash and Precup, Doina},
TITLE = {Bisimulation metrics for continuous Markov decision processes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1662-1714},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {bisimulation, metrics, reinforcement learning, continuous, markov decision process},
URL = {http://dx.doi.org/10.1137/10080484X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Svitkina-Fleischer/11,
AUTHOR = {Svitkina, Zoya and Fleischer, Lisa},
TITLE = {Submodular approximation: Sampling-based algorithms and lower bounds},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1715-1737},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {approximation algorithms, information-theoretic lower bounds, submodular functions},
URL = {http://dx.doi.org/10.1137/100783352},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Calinescu-Chekuri-Pal-Vondrak/11,
AUTHOR = {Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
TITLE = {Maximizing a monotone submodular function subject to a matroid constraint},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1740-1766},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {monotone submodular set function, matroid, social welfare, generalized assignment problem, approximation algorithm},
URL = {http://dx.doi.org/10.1137/080733991},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kedlaya-Umans/11,
AUTHOR = {Kedlaya, Kiran S. and Umans, Christopher},
TITLE = {Fast polynomial factorization and modular composition},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1767-1802},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {modular composition, multivariate multipoint evaluation, multimodular reduction, polynomial factorization},
URL = {http://dx.doi.org/10.1137/08073408X},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Peikert-Waters/11,
AUTHOR = {Peikert, Chris and Waters, Brent},
TITLE = {Lossy trapdoor functions and their applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1803-1844},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {trapdoor functions, lossiness, chosen-ciphertext security, lattices},
URL = {http://dx.doi.org/10.1137/080733954},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mironov-Naor-Segev/11,
AUTHOR = {Mironov, Ilya and Naor, Moni and Segev, Gil},
TITLE = {Sketching in adversarial environments},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1845-1870},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {sketch model, data stream model, communication complexity},
URL = {http://dx.doi.org/10.1137/080733772},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rao/11,
AUTHOR = {Rao, Anup},
TITLE = {Parallel repetition in projection games and a concentration bound},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1871-1891},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {parallel repetition, concentration, chsh game},
URL = {http://dx.doi.org/10.1137/080734042},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Levin-Schapira-Zohar/11,
AUTHOR = {Levin, Hagay and Schapira, Michael and Zohar, Aviv},
TITLE = {Interdomain routing and games},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1892-1912},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {interdomain routing, border gateway protocol (bgp), security, distributed algorithmic mechanism design, communication complexity},
URL = {http://dx.doi.org/10.1137/080734017},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Spielman-Srivastava/11,
AUTHOR = {Spielman, Daniel A. and Srivastava, Nikhil},
TITLE = {Graph sparsification by effective resistances},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1913-1926},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {spectral graph theory, electrical flows, sparsification},
URL = {http://dx.doi.org/10.1137/080734029},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Valiant/11a,
AUTHOR = {Valiant, Paul},
TITLE = {Testing symmetric properties of distributions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1927-1968},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {approximation algorithms, statistical properties, $l_1$ distance approximation, entropy approximation, lower bounds, poissonization, vandermonde matrices},
URL = {http://dx.doi.org/10.1137/080734066},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Sherstov/11a,
AUTHOR = {Sherstov, Alexander A.},
TITLE = {The pattern matrix method},
JOURNAL = {SIAM J. Comput.},
VOLUME = {40},
NUMBER = {6},
PAGES = {1969-2000},
YEAR = {2011},
EDITOR = {Sudan, M.},
KEYWORDS = {pattern matrix method, bounded-error communication complexity, quantum communication complexity, discrepancy, degree/discrepancy theorem, approximate rank, approximate trace norm, linear programming duality, approximation and sign-representation of boolean functions by real polynomials},
URL = {http://dx.doi.org/10.1137/080733644},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}