부산대학교 도서관

\{STOC'14 has been reviewed [MR3238924].\} \tpar{\bf Papers in this collection include the following:}\tpar Shiri\ 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 algorithms for the Steiner tree'', \nbp{11--20}. 3388178\tpar Monika\ Henzinger, Sebastian\ Krinninger, Danupon\ Nanongkai\ and Thatchaphol\ Saranurak, ``Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture'', \nbp{21--30}. 3388179\tpar Timothy\ M.\ Chan\ and Moshe\ Lewenstein, ``Clustered integer 3SUM via additive combinatorics'', \nbp{31--40}. 3388180\tpar Amir\ Abboud, Virginia\ Vassilevska Williams\ and Huacheng\ Yu, ``Matching triangles 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 subquadratic time (unless SETH is false)'', \nbp{51--58}. 3388182\tpar Jian\ Ding, Allan\ Sly\ and Nike\ Sun, ``Proof of the satisfiability conjecture for large $k$ [extended abstract]'', \nbp{59--68}. 3388183\tpar Elchanan\ Mossel, Joe\ Neeman\ and Allan\ Sly, ``Consistency thresholds for the planted bisection model [extended abstract]'', \nbp{69--75}. 3388184\tpar Vitaly\ Feldman, Will\ Perkins\ and Santosh\ Vempala, ``On the complexity of random satisfiability problems with planted solutions [extended abstract]'', \nbp{77--86}. 3388185\tpar Raghu\ Meka, Aaron\ Potechin\ and Avi\ Wigderson, ``Sum-of-squares lower bounds for planted clique [extended abstract]'', \nbp{87--96}. 3388186\tpar Boaz\ Barak, Siu\ On\ Chan\ and Pravesh\ K.\ Kothari, ``Sum of squares lower bounds from pairwise independence [extended abstract]'', \nbp{97--106}. 3388187\tpar Gábor\ Braun, Sebastian\ Pokutta\ and Daniel\ Zink, ``Inapproximability of combinatorial problems via small LPs and SDPs'', \nbp{107--116}. 3388188\tpar Cynthia\ Dwork, Vitaly\ Feldman, Moritz\ Hardt, Toniann\ Pitassi, Omer\ Reingold\ and Aaron\ Roth, ``Preserving statistical validity in adaptive data analysis [extended abstract]'', \nbp{117--126}. 3388189\tpar Raef\ Bassily\ and Adam\ Smith, ``Local, private, efficient protocols for succinct histograms'', \nbp{127--135}. 3388190\tpar Shachar\ Lovett\ and Jiapeng\ Zhang, ``Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions'', \nbp{137--142}. 3388191\tpar Boaz\ Barak, Jonathan\ A.\ Kelner\ and David\ Steurer, ``Dictionary learning and tensor decomposition via the sum-of-squares method [extended abstract]'', \nbp{143--151}. 3388192\tpar Vahab\ Mirrokni\ and Morteza\ Zadimoghaddam, ``Randomized composable core-sets for distributed submodular maximization'', \nbp{153--162}. 3388193\tpar Michael\ B.\ Cohen, Sam\ Elder, Cameron\ Musco, Christopher\ Musco\ and Mădălina Persu, ``Dimensionality reduction 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 maintaining dense 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 in sparse 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 pivoting rule for the simplex algorithm'', \nbp{209--218}. 3388199\tpar Shuchi\ Chawla, Konstantin\ Makarychev, Tselil\ Schramm\ and Grigory\ Yaroslavtsev, ``Near optimal LP rounding algorithm for correlation clustering on complete and complete k-partite graphs'', \nbp{219--228}. 3388200\tpar Zeyuan\ Allen-Zhu\ and Lorenzo\ Orecchia, ``Nearly-linear time positive LP solver with faster convergence rate [extended abstract]'', \nbp{229--236}. 3388201\tpar Zeyuan\ Allen-Zhu, Zhenyu\ Liao\ and Lorenzo\ Orecchia, ``Spectral sparsification and regret minimization beyond matrix multiplicative updates [extended abstract]'', \nbp{237--245}. 3388202\tpar Pravesh\ K.\ Kothari\ and Raghu\ Meka, ``Almost optimal pseudorandom generators for spherical caps [extended abstract]'', \nbp{247--256}. 3388203\tpar Mika\ Göös, Shachar\ Lovett, Raghu\ Meka, Thomas\ Watson\ and David\ Zuckerman, ``Rectangles are nonnegative juntas [extended abstract]'', \nbp{257--266}. 3388204\tpar Irit\ Dinur, Prahladh\ Harsha\ and Guy\ Kindler, ``Polynomially low error PCPs with polyloglog n queries via modular composition'', \nbp{267--276}. 3388205\tpar Abhishek\ Bhowmick\ and Shachar\ Lovett, ``The list decoding radius of Reed-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\tpar Emmanuel\ Abbe, Amir\ Shpilka\ and Avi\ Wigderson, ``Reed-Muller codes for random erasures and errors [extended abstract]'', \nbp{297--306}. 3388208\tpar Scott\ Aaronson\ and Andris\ Ambainis, ``Forrelation: a problem that optimally separates quantum from classical computing'', \nbp{307--316}. 3388209\tpar Dave\ Touchette, ``Quantum information complexity [extended abstract]'', \nbp{317--326}. 3388210\tpar Dave\ Bacon, Steven\ T.\ Flammia, Aram\ W.\ Harrow\ and Jonathan\ Shi, ``Sparse quantum codes from quantum circuits'', \nbp{327--334}. 3388211\tpar Mark\ Braverman\ and Ankit\ Garg, ``Small value parallel repetition for general games'', \nbp{335--340}. 3388212\tpar Mark\ Braverman\ and Omri\ Weinstein, ``An interactive information odometer and applications'', \nbp{341--350}. 3388213\tpar W.\ T.\ Gowers\ and Emanuele\ Viola, ``The communication complexity of interleaved group products'', \nbp{351--360}. 3388214\tpar Siddharth\ Barman, ``Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathé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 in anonymous games'', \nbp{381--390}. 3388217\tpar Euiwoong\ Lee, ``Hardness of graph pricing through Generalized Max-Dicut'', \nbp{391--399}. 3388218\tpar Amit\ Daniely, Michael\ Schapira\ and Gal\ Shahaf, ``Inapproximability of truthful 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\ and Brent\ Waters, ``Indistinguishability obfuscation for Turing machines with unbounded memory [extended abstract]'', \nbp{419--428}. 3388221\tpar Ran\ Canetti, Justin\ Holmgren, Abhishek\ Jain\ and Vinod\ Vaikuntanathan, ``Succinct garbling and indistinguishability obfuscation for RAM programs'', \nbp{429--437}. 3388222\tpar Nir\ Bitansky, Sanjam\ Garg, Huijia\ Lin, Rafael\ Pass\ and Sidharth\ Telang, ``Succinct randomized encodings and their applications'', \nbp{439--448}. 3388223\tpar Sanjam\ Garg, Steve\ Lu, Rafail\ Ostrovsky\ and Alessandra\ Scafuro, ``Garbled RAM from one-way functions'', \nbp{449--458}. 3388224\tpar Divesh\ Aggarwal, Yevgeniy\ Dodis, Tomasz\ Kazana\ and Maciej\ Obremski, ``Non-malleable reductions and applications'', \nbp{459--468}. 3388225\tpar Sergey\ Gorbunov, Vinod\ Vaikuntanathan\ and Daniel\ Wichs, ``Leveled fully homomorphic signatures from standard lattices'', \nbp{469--477}. 3388226\tpar Alexandr\ Andoni, Robert\ Krauthgamer\ and Ilya\ Razenshteyn, ``Sketching and embedding are equivalent for norms'', \nbp{479--488}. 3388227\tpar Michael\ Elkin, Arnold\ Filtser\ and Ofer\ Neiman, ``Prioritized metric structures and embedding [extended abstract]'', \nbp{489--498}. 3388228\tpar Jean\ Bourgain, Sjoerd\ Dirksen\ and Jelani\ Nelson, ``Toward a unified theory of sparse dimensionality reduction in Euclidean space'', \nbp{499--508}. 3388229\tpar Amirali\ Abdullah\ and Suresh\ Venkatasubramanian, ``A directed isoperimetric inequality with application to Bregman near neighbor lower bounds'', \nbp{509--517}. 3388230\tpar Xi\ Chen, Anindya\ De, Rocco\ A.\ Servedio\ and Li-Yang\ Tan, ``Boolean function monotonicity testing requires (almost) $\rm n^{1/2}$ non-adaptive queries'', \nbp{519--528}. 3388231\tpar Ryan\ O'Donnell\ and John\ Wright, ``Quantum spectrum testing'', \nbp{529--538}. 3388232\tpar Ben\ Cousins\ and Santosh\ Vempala, ``Bypassing KLS: Gaussian cooling and an $\rm O^*(n^3)$ volume algorithm'', \nbp{539--548}. 3388233\tpar Jingcheng\ Liu\ and Pinyan\ 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 and communication for Boolean functions [extended abstract]'', \nbp{557--566}. 3388235\tpar James\ R.\ Lee, Prasad\ Raghavendra\ and David\ Steurer, ``Lower bounds on the size of semidefinite programming relaxations'', \nbp{567--576}. 3388236\tpar Zeev\ Dvir\ and Sivakanth\ Gopi, ``2-server PIR with sub-polynomial communication'', \nbp{577--584}. 3388237\tpar Andris\ Ambainis, Yuval\ Filmus\ and François\ Le Gall, ``Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract)'', \nbp{585--593}. 3388238\tpar Joël\ Alwen\ and Vladimir\ Serbinenko, ``High parallel complexity graphs and memory-hard functions'', \nbp{595--603}. 3388239\tpar Ittai\ Abraham\ and Danny\ Dolev, ``Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity'', \nbp{605--614}. 3388240\tpar George\ Giakkoupis, Maryam\ Helmi, Lisa\ Higham\ and Philipp\ Woelfel, ``Test-and-set in optimal space'', \nbp{615--623}. 3388241\tpar Stephen\ Alstrup, Haim\ Kaplan, Mikkel\ Thorup\ and Uri\ Zwick, ``Adjacency labeling schemes and induced-universal graphs'', \nbp{625--634}. 3388242\tpar Magnús\ M.\ Halldórsson\ and Tigran\ Tonoyan, ``How well can graphs represent wireless 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-linear time'', \nbp{665--674}. 3388246\tpar Ken-ichi\ Kawarabayashi\ and Anastasios\ Sidiropoulos, ``Beyond the Euler characteristic: approximating the genus of general graphs [extended abstract]'', \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\tpar Artur\ Czumaj, ``Random permutations using switching networks'', \nbp{703--712}. 3388250\tpar Anand\ Louis, ``Hypergraph Markov operators, eigenvalues and approximation algorithms'', \nbp{713--722}. 3388251\tpar Artur\ Czumaj, Pan\ Peng\ and Christian\ Sohler, ``Testing cluster structure of 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 discrete Gaussian sampling (extended abstract)'', \nbp{733--742}. 3388253\tpar Jian\ Li, Yuval\ Rabani, Leonard\ J.\ Schulman\ and Chaitanya\ Swamy, ``Learning arbitrary statistical mixtures of discrete distributions'', \nbp{743--752}. 3388254\tpar Moritz\ Hardt\ and Eric\ Price, ``Tight bounds for 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 high dimensions [extended abstract]'', \nbp{761--770}. 3388256\tpar Guy\ Bresler, ``Efficiently learning Ising models 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 for nonadaptive 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 of Vandermonde matrices'', \nbp{821--830}. 3388262\tpar Leonard\ J.\ Schulman\ and Alistair\ Sinclair, ``Analysis of a classical matrix preconditioning algorithm'', \nbp{831--840}. 3388263\tpar Kyle\ Fox, Philip\ N.\ Klein\ and Shay\ Mozes, ``A polynomial-time bicriteria approximation scheme for planar bisection'', \nbp{841--850}. 3388264\tpar Nikhil\ Bansal\ and Janardhan\ Kulkarni, ``Minimizing flow-time on unrelated machines'', \nbp{851--860}. 3388265\tpar Aleksandar\ Nikolov, ``Randomized rounding for the largest simplex problem [extended abstract]'', \nbp{861--870}. 3388266\tpar Anupam\ Gupta\ and Amit\ Kumar, ``Greedy algorithms for Steiner forest'', \nbp{871--878}. 3388267\tpar Thomas\ Kesselheim, Robert\ Kleinberg\ and Rad\ Niazadeh, ``Secretary problems with non-uniform arrival order'', \nbp{879--888}. 3388268\tpar Nitish\ Korula, Vahab\ Mirrokni\ and Morteza\ Zadimoghaddam, ``Online submodular welfare maximization: greedy beats 1/2 in random order'', \nbp{889--898}. 3388269\tpar