부산대학교 도서관

\{STOC'14 has been reviewed [MR3238924].\}\tpar{\bf Papers in this collection include the following:}\tparShiri Chechik, ``Approximate distance oracles with improved bounds'',\nbp{1--10}. 3388177\tpar Jakub Łącki,Jakub Oćwieja, Marcin Pilipczuk, Piotr Sankowski and Anna Zych,``The power of dynamic distance oracles: efficient dynamic algorithmsfor the Steiner tree'', \nbp{11--20}. 3388178\tparMonika Henzinger, Sebastian Krinninger, Danupon Nanongkai andThatchaphol Saranurak, ``Unifying and strengthening hardness fordynamic problems via the online matrix-vector multiplicationconjecture'', \nbp{21--30}. 3388179\tpar Timothy M.\Chan and Moshe Lewenstein, ``Clustered integer 3SUM via additivecombinatorics'', \nbp{31--40}. 3388180\tpar Amir\Abboud, Virginia Vassilevska Williams and Huacheng Yu, ``Matchingtriangles and basing hardness on an extremely popular conjecture'',\nbp{41--50}. 3388181\tpar Arturs Backurs and Piotr\Indyk, ``Edit distance cannot be computed in strongly subquadratictime (unless SETH is false)'', \nbp{51--58}. 3388182\tpar Jian Ding, Allan Sly and Nike Sun, ``Proofof the satisfiability conjecture for large $k$ [extended abstract]'',\nbp{59--68}. 3388183\tpar Elchanan Mossel, Joe\Neeman and Allan Sly, ``Consistency thresholds for the plantedbisection model [extended abstract]'', \nbp{69--75}. 3388184\tpar Vitaly Feldman, Will Perkins and Santosh\Vempala, ``On the complexity of random satisfiability problems withplanted solutions [extended abstract]'', \nbp{77--86}. 3388185\tpar Raghu Meka, Aaron Potechin and Avi\Wigderson, ``Sum-of-squares lower bounds for planted clique [extendedabstract]'', \nbp{87--96}. 3388186\tpar Boaz Barak,Siu On Chan and Pravesh K. Kothari, ``Sum of squares lower boundsfrom pairwise independence [extended abstract]'',\nbp{97--106}. 3388187\tpar Gábor Braun, Sebastian\Pokutta and Daniel Zink, ``Inapproximability of combinatorialproblems via small LPs and SDPs'', \nbp{107--116}. 3388188\tpar Cynthia Dwork, Vitaly Feldman, Moritz Hardt,Toniann Pitassi, Omer Reingold and Aaron Roth, ``Preservingstatistical validity in adaptive data analysis [extended abstract]'',\nbp{117--126}. 3388189\tpar Raef Bassily and Adam\Smith, ``Local, private, efficient protocols for succincthistograms'', \nbp{127--135}. 3388190\tpar Shachar\Lovett and Jiapeng Zhang, ``Improved noisy population recovery, andreverse Bonami-Beckner inequality for sparse functions'',\nbp{137--142}. 3388191\tpar Boaz Barak, Jonathan\A. Kelner and David Steurer, ``Dictionary learning and tensordecomposition via the sum-of-squares method [extended abstract]'',\nbp{143--151}. 3388192\tpar Vahab Mirrokni andMorteza Zadimoghaddam, ``Randomized composable core-sets fordistributed submodular maximization'', \nbp{153--162}. 3388193\tpar Michael B. Cohen, Sam Elder, Cameron Musco,Christopher Musco and Mădălina Persu, ``Dimensionalityreduction for k-means clustering and low rank approximation'',\nbp{163--172}. 3388194\tpar Sayan Bhattacharya,Monika Henzinger, Danupon Nanongkai and Charalampos E.\Tsourakakis, ``Space- and time-efficient algorithm for maintainingdense subgraphs on one-pass dynamic streams'', \nbp{173--182}. 3388195\tpar Michael B. Cohen and Richard Peng,``$\ell_p$ row sampling by Lewis weights'', \nbp{183--192}. 3388196\tpar Nikhil Bansal, Anupam Gupta and Guru\Guruganesh, ``On the Lovász theta function for independent sets insparse graphs'', \nbp{193--200}. 3388197\tpar John\Fearnley and Rahul Savani, ``The complexity of the simplex method'',\nbp{201--208}. 3388198\tpar Thomas Dueholm Hansen\and Uri Zwick, ``An improved version of the random-facet pivotingrule for the simplex algorithm'', \nbp{209--218}. 3388199\tpar Shuchi Chawla, Konstantin Makarychev, Tselil\Schramm and Grigory Yaroslavtsev, ``Near optimal LP roundingalgorithm for correlation clustering on complete and completek-partite graphs'', \nbp{219--228}. 3388200\tparZeyuan Allen-Zhu and Lorenzo Orecchia, ``Nearly-linear timepositive LP solver with faster convergence rate [extended abstract]'',\nbp{229--236}. 3388201\tpar Zeyuan Allen-Zhu,Zhenyu Liao and Lorenzo Orecchia, ``Spectral sparsification andregret minimization beyond matrix multiplicative updates [extendedabstract]'', \nbp{237--245}. 3388202\tpar Pravesh K.\Kothari and Raghu Meka, ``Almost optimal pseudorandom generators forspherical caps [extended abstract]'', \nbp{247--256}. 3388203\tpar Mika Göös, Shachar Lovett, Raghu Meka,Thomas Watson and David Zuckerman, ``Rectangles are nonnegativejuntas [extended abstract]'', \nbp{257--266}. 3388204\tpar Irit Dinur, Prahladh Harsha and Guy Kindler,``Polynomially low error PCPs with polyloglog n queries via modularcomposition'', \nbp{267--276}. 3388205\tpar Abhishek\Bhowmick and Shachar Lovett, ``The list decoding radius ofReed-Muller codes over small fields'', \nbp{277--285}. 3388206\tpar Zitan Chen, Sidharth Jaggi and Michael\Langberg, ``A characterization of the capacity of online (causal)binary channels'', \nbp{287--296}. 3388207\tparEmmanuel Abbe, Amir Shpilka and Avi Wigderson, ``Reed-Muller codesfor random erasures and errors [extended abstract]'',\nbp{297--306}. 3388208\tpar Scott Aaronson andAndris Ambainis, ``Forrelation: a problem that optimally separatesquantum from classical computing'', \nbp{307--316}. 3388209\tpar Dave Touchette, ``Quantum informationcomplexity [extended abstract]'', \nbp{317--326}. 3388210\tpar Dave Bacon, Steven T. Flammia, Aram W.\Harrow and Jonathan Shi, ``Sparse quantum codes from quantumcircuits'', \nbp{327--334}. 3388211\tpar Mark\Braverman and Ankit Garg, ``Small value parallel repetition forgeneral games'', \nbp{335--340}. 3388212\tpar Mark\Braverman and Omri Weinstein, ``An interactive information odometerand applications'', \nbp{341--350}. 3388213\tpar W.\T. Gowers and Emanuele Viola, ``The communication complexity ofinterleaved group products'', \nbp{351--360}. 3388214\tpar Siddharth Barman, ``Approximating Nashequilibria and dense bipartite subgraphs via an approximate version ofCarathéodory's theorem'', \nbp{361--369}. 3388215\tpar Richard Cole and Vasilis Gkatzelis,``Approximating the Nash social welfare with indivisible items'',\nbp{371--380}. 3388216\tpar Xi Chen, David Durfee\and Anthi Orfanou, ``On the complexity of Nash equilibria inanonymous games'', \nbp{381--390}. 3388217\tparEuiwoong Lee, ``Hardness of graph pricing through GeneralizedMax-Dicut'', \nbp{391--399}. 3388218\tpar Amit\Daniely, Michael Schapira and Gal Shahaf, ``Inapproximability oftruthful mechanisms via generalizations of the VC dimension'',\nbp{401--408}. 3388219\tpar Aviad Rubinstein,``Inapproximability of Nash equilibrium'', \nbp{409--418}. 3388220\tpar Venkata Koppula, Allison Bishop Lewko andBrent Waters, ``Indistinguishability obfuscation for Turing machineswith unbounded memory [extended abstract]'', \nbp{419--428}. 3388221\tpar Ran Canetti, Justin Holmgren, Abhishek Jain\and Vinod Vaikuntanathan, ``Succinct garbling andindistinguishability obfuscation for RAM programs'',\nbp{429--437}. 3388222\tpar Nir Bitansky, Sanjam\Garg, Huijia Lin, Rafael Pass and Sidharth Telang, ``Succinctrandomized encodings and their applications'', \nbp{439--448}. 3388223\tpar Sanjam Garg, Steve Lu, Rafail Ostrovsky andAlessandra Scafuro, ``Garbled RAM from one-way functions'',\nbp{449--458}. 3388224\tpar Divesh Aggarwal,Yevgeniy Dodis, Tomasz Kazana and Maciej Obremski, ``Non-malleablereductions and applications'', \nbp{459--468}. 3388225\tpar Sergey Gorbunov, Vinod Vaikuntanathan andDaniel Wichs, ``Leveled fully homomorphic signatures from standardlattices'', \nbp{469--477}. 3388226\tpar Alexandr\Andoni, Robert Krauthgamer and Ilya Razenshteyn, ``Sketching andembedding are equivalent for norms'', \nbp{479--488}. 3388227\tpar Michael Elkin, Arnold Filtser and Ofer\Neiman, ``Prioritized metric structures and embedding [extendedabstract]'', \nbp{489--498}. 3388228\tpar Jean\Bourgain, Sjoerd Dirksen and Jelani Nelson, ``Toward a unifiedtheory of sparse dimensionality reduction in Euclidean space'',\nbp{499--508}. 3388229\tpar Amirali Abdullah andSuresh Venkatasubramanian, ``A directed isoperimetric inequality withapplication to Bregman near neighbor lower bounds'',\nbp{509--517}. 3388230\tpar Xi Chen, Anindya De,Rocco A. Servedio and Li-Yang Tan, ``Boolean function monotonicitytesting requires (almost) $\rm n^{1/2}$ non-adaptive queries'',\nbp{519--528}. 3388231\tpar Ryan O'Donnell andJohn Wright, ``Quantum spectrum testing'', \nbp{529--538}. 3388232\tpar Ben Cousins and Santosh Vempala, ``BypassingKLS: Gaussian cooling and an $\rm O^*(n^3)$ volume algorithm'',\nbp{539--548}. 3388233\tpar Jingcheng Liu andPinyan Lu, ``FPTAS for \#BIS with degree bounds on one side'',\nbp{549--556}. 3388234\tpar Anat Ganor, Gillat Kol\and Ran Raz, ``Exponential separation of information andcommunication for Boolean functions [extended abstract]'',\nbp{557--566}. 3388235\tpar James R. Lee, Prasad\Raghavendra and David Steurer, ``Lower bounds on the size ofsemidefinite programming relaxations'', \nbp{567--576}. 3388236\tpar Zeev Dvir and Sivakanth Gopi, ``2-server PIRwith sub-polynomial communication'', \nbp{577--584}. 3388237\tpar Andris Ambainis, Yuval Filmus and François Le Gall, ``Fast matrix multiplication: limitations of theCoppersmith-Winograd method (extended abstract)'',\nbp{585--593}. 3388238\tpar Joël Alwen andVladimir Serbinenko, ``High parallel complexity graphs andmemory-hard functions'', \nbp{595--603}. 3388239\tparIttai Abraham and Danny Dolev, ``Byzantine agreement with optimalearly stopping, optimal resilience and polynomial complexity'',\nbp{605--614}. 3388240\tpar George Giakkoupis,Maryam Helmi, Lisa Higham and Philipp Woelfel, ``Test-and-set inoptimal space'', \nbp{615--623}. 3388241\tpar Stephen\Alstrup, Haim Kaplan, Mikkel Thorup and Uri Zwick, ``Adjacencylabeling schemes and induced-universal graphs'',\nbp{625--634}. 3388242\tpar Magnús M.\Halldórsson and Tigran Tonoyan, ``How well can graphs representwireless interference? [extended abstract]'', \nbp{635--644}. 3388243\tpar Julia Chuzhoy, ``Excluded grid theorem:improved and simplified'', \nbp{645--654}. 3388244\tpar Ken-ichi Kawarabayashi and Stephan Kreutzer,``The directed grid theorem'', \nbp{655--664}. 3388245\tpar Ken-ichi Kawarabayashi and Mikkel Thorup,``Deterministic global minimum cut of a simple graph in near-lineartime'', \nbp{665--674}. 3388246\tpar Ken-ichi\Kawarabayashi and Anastasios Sidiropoulos, ``Beyond the Eulercharacteristic: approximating the genus of general graphs [extendedabstract]'', \nbp{675--682}. 3388247\tpar Martin\Grohe and Pascal Schweitzer, ``Computing with tangles'',\nbp{683--692}. 3388248\tpar Xiaorui Sun and John\Wilmes, ``Faster canonical forms for primitive coherent configurations(extended abstract)'', \nbp{693--702}. 3388249\tparArtur Czumaj, ``Random permutations using switching networks'',\nbp{703--712}. 3388250\tpar Anand Louis,``Hypergraph Markov operators, eigenvalues and approximationalgorithms'', \nbp{713--722}. 3388251\tpar Artur\Czumaj, Pan Peng and Christian Sohler, ``Testing cluster structureof graphs'', \nbp{723--732}. 3388252\tpar Divesh\Aggarwal, Daniel Dadush, Oded Regev and Noah Stephens-Davidowitz,``Solving the shortest vector problem in $2^n$ time via discreteGaussian sampling (extended abstract)'', \nbp{733--742}. 3388253\tpar Jian Li, Yuval Rabani, Leonard J. Schulman\and Chaitanya Swamy, ``Learning arbitrary statistical mixtures ofdiscrete distributions'', \nbp{743--752}. 3388254\tpar Moritz Hardt and Eric Price, ``Tight boundsfor learning a mixture of two Gaussians [extended abstract]'',\nbp{753--760}. 3388255\tpar Rong Ge, Qingqing\Huang and Sham M. Kakade, ``Learning mixtures of Gaussians in highdimensions [extended abstract]'', \nbp{761--770}. 3388256\tpar Guy Bresler, ``Efficiently learning Isingmodels on arbitrary graphs [extended abstract]'',\nbp{771--782}. 3388257\tpar Wolfgang Mulzer, Huy\L. Nguyễn, Paul Seiferth and Yannik Stein, ``Approximate$k$-flat nearest neighbor search'', \nbp{783--792}. 3388258\tpar Alexandr Andoni and Ilya Razenshteyn,``Optimal data-dependent hashing for approximate near neighbors'',\nbp{793--801}. 3388259\tpar Kasper Green Larsen,Jelani Nelson and Huy L. Nguyễn, ``Time lower bounds fornonadaptive turnstile streaming algorithms'', \nbp{803--812}. 3388260\tpar Tobias Christiani, Rasmus Pagh and Mikkel\Thorup, ``From independence to expansion and back again'',\nbp{813--820}. 3388261\tpar Ankur Moitra,``Super-resolution, extremal functions and the condition number ofVandermonde matrices'', \nbp{821--830}. 3388262\tparLeonard J. Schulman and Alistair Sinclair, ``Analysis of aclassical matrix preconditioning algorithm'', \nbp{831--840}. 3388263\tpar Kyle Fox, Philip N. Klein and Shay Mozes,``A polynomial-time bicriteria approximation scheme for planarbisection'', \nbp{841--850}. 3388264\tpar Nikhil\Bansal and Janardhan Kulkarni, ``Minimizing flow-time on unrelatedmachines'', \nbp{851--860}. 3388265\tpar Aleksandar\Nikolov, ``Randomized rounding for the largest simplex problem[extended abstract]'', \nbp{861--870}. 3388266\tparAnupam Gupta and Amit Kumar, ``Greedy algorithms for Steinerforest'', \nbp{871--878}. 3388267\tpar Thomas\Kesselheim, Robert Kleinberg and Rad Niazadeh, ``Secretary problemswith non-uniform arrival order'', \nbp{879--888}. 3388268\tpar Nitish Korula, Vahab Mirrokni and Morteza\Zadimoghaddam, ``Online submodular welfare maximization: greedy beats1/2 in random order'', \nbp{889--898}. 3388269\tpar