부산대학교 도서관

\{The 21st Symposium has been reviewed [ 2797147 ].\}\parContents: T. S. Jayram and David Woodruff [David P. Woodruff],Optimal bounds for Johnson-Lindenstrauss transforms and streamingproblems with sub-constant error (1--10) 2857105 ;Elad Verbin and Wei Yu, The streaming complexity of cycle counting,sorting by reversals, and other problems (11--25) 2857106 ; Vladimir Braverman, Adam Meyerson, Rafail\Ostrovsky, Alan Roytman, Michael Shindler and Brian Tagiku,Streaming $k$-means on well-clusterable data (26--40) 2857107 ; Eric Price, Efficient sketches for the set queryproblem (41--56) 2857108 ; Guy Feigenblat, Ely\Porat and Ariel Shiftan, Exponential time improvement for {\it min-wise} based algorithms (57--66) 2857109 ;Gautier Stauffer, Guillaume Massonnet, Christophe Rapine andJean-Philippe Gayon, A simple and fast 2-approximation algorithm forthe one-warehouse multi-retailers problem (67--79) 2857110 ; Jian Li [Jian Li\asup{8}] and Samir Khuller,Generalized machine activation problems (80--94) 2857111 ; Sungjin Im and Benjamin Moseley, An onlinescalable algorithm for minimizing $\ell_k$-norms of weighted flow timeon unrelated machines (95--108) 2857112 ; Jeff\Edmonds [Jeff A. Edmonds], Sungjin Im and Benjamin Moseley,Online scalable scheduling for the $\ell_k$-norms of flow time withoutconservation of work (109--119) 2857113 ; Kyle Fox\and Benjamin Moseley, Online scheduling on identical machines usingSRPT (120--128) 2857114 ; Jennifer Debroni, John\D. Eblen, Michael A. Langston, Wendy Myrvold [Wendy J. Myrvold],Peter Shor and Dinesh Weerapurage, A complete resolution of theKeller maximum clique problem (129--135) 2857115 ;Amin Coja-Oghlan and Charilaos Efthymiou, On independent sets inrandom graphs (136--144) 2857116 . \parTorsten Mütze,Thomas Rast and Reto Spöhel, Coloring random graphs onlinewithout creating monochromatic subgraphs (145--158) 2857117 ; Yoshiharu Kohayakawa, Sangjune Lee and Vojtěch Rödl, The maximum size of a Sidon set contained in a sparserandom set of integers (159--171) 2857118 ; Philippe\Flajolet, Maryse Pelletier and Michèle Soria, On Buffon machinesand numbers (172--183) 2857119 ; Bruce Reed, Graphcoloring via the probabilistic method (184); Nir Ailon and Edo\Liberty, An almost optimal unrestricted fast Johnson-Lindenstrausstransform (185--191) 2857120 ; Umang Bhaskar, Lisa\Fleischer [Lisa K. Fleischer] and Elliot Anshelevich, AStackelberg strategy for routing flow over time (192--201) 2857121 ; Oliver Friedmann, Thomas Dueholm Hansen andUri Zwick, A subexponential lower bound for the random facetalgorithm for parity games (202--216) 2857122 ; Yang\Cai [Yang Cai\asup{1}] and Constantinos Daskalakis, On minmaxtheorems for multiplayer games (217--234) 2857123 ;Constantinos Daskalakis, Alan Deckelbaum and Anthony Kim,Near-optimal no-regret algorithms for zero-sum games (235--254) 2857124 ; Tim Roughgarden and Florian Schoppmann,Local smoothness and the price of anarchy in atomic splittablecongestion games (255--267) 2857125 ; Pankaj K.\Agarwal [Pankaj Kumar Agarwal], Thomas Mølhave and Bardia\Sadri, I/O-efficient contour queries on terrains (268--284) 2857126 ; Mark de Berg [Mark T. de Berg], Herman\Haverkort [Herman J. Haverkort] and Constantinos Tsirogiannis[Constantinos P. Tsirogiannis], Implicit flow routing on terrainswith applications to surface networks and drainage structures(285--296) 2857127 . \parJeff Erickson and Amir\Nayyeri, Shortest non-crossing walks in the plane (297--308) 2857128 ; Danny Z. Chen and Haitao Wang [Hai TaoWang\asup{1}], Computing shortest paths amid pseudodisks (309--326) 2857129 ; Luca Foschini, John Hershberger [John\E. Hershberger] and Subhash Suri, On the complexity oftime-dependent shortest paths (327--341) 2857130 ;Michael Drmota and Wojciech Szpankowski, A master theorem fordiscrete divide and conquer recurrences (342--361) 2857131 ; Paweł Gawrychowski, Optimal pattern matching inLZW compressed strings (362--372) 2857132 ; Philip\Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa\Rao Satti [Satti Srinivasa Rao] and Oren Weimann, Random accessto grammar-compressed strings (373--389) 2857133 ;Peyman Afshani, Gerth Stølting Brodal and Norbert Zeh, Orderedand unordered top-$K$ range reporting in large data sets (390--400) 2857134 ; Marek Karpinski and Yakov Nekrich,Top-$K$ color queries for document retrieval (401--411) 2857135 ; Yuval Peres, Alistair Sinclair, Perla Sousi andAlexandre Stauffer [Alexandre O. Stauffer], Mobile geometricgraphs: detection, coverage and percolation (412--428) 2857136 ; Petra Berenbrink, Colin Cooper, Tom Friedetzky,Tobias Friedrich and Thomas Sauerwald, Randomized diffusion forindivisible loads (429--439) 2857137 ; Keren\Censor-Hillel and Hadas Shachnai, Fast information spreading ingraphs with large weak conductance (440--448) 2857138 ; George Giakkoupis and Philipp Woelfel, On therandomness requirements of rumor spreading (449--461) 2857139 . \parThomas Sauerwald and Alexandre Stauffer[Alexandre O. Stauffer], Rumor spreading and vertex expansion onregular graphs (462--475) 2857140 ; Friedrich\Eisenbrand, Dömötör Pálvölgyi and Thomas Rothvoß, Binpacking via discrepancy of permutations (476--481) 2857141 ; Amit Deshpande, Madhur Tulsiani and Nisheeth\K. Vishnoi, Algorithms and hardness for subspace approximation(482--496) 2857142 ; Aditya Bhaskara and Aravindan\Vijayaraghavan, Approximating matrix $p$-norms (497--511) 2857143 ; Boaz Barak, Moritz Hardt, Thomas Holenstein andDavid Steurer, Subsampling mathematical relaxations and average-casecomplexity (512--531) 2857144 ; Lorenzo Orecchia\and Nisheeth K. Vishnoi, Towards an SDP-based approach to spectralmethods: a nearly-linear-time algorithm for graph partitioning anddecomposition (532--545) 2857145 ; Ben W.\Reichardt, Faster quantum algorithm for evaluating game trees(546--559) 2857146 ; Ben W. Reichardt, Reflectionsfor quantum query algorithms (560--569) 2857147 ;Matthew Cook, Yunhui Fu and Robert Schweller, Temperature 1self-assembly: deterministic assembly in 3D and probabilistic assemblyin 2D (570--589) 2857148 ; Nathaniel Bryans, Ehsan\Chiniforooshan, David Doty, Lila Kari and Shinnosuke Seki, Thepower of nondeterminism in self-assembly (590--602) 2857149 ; Günter Rote and Uri Zwick, Collapse (603--613) 2857150 ; Karthekeyan Chandrasekaran, Richard Karp,Erick Moreno-Centeno and Santosh Vempala, Algorithms for implicithitting set problems (614--629) 2857151 . \parYuri\Faenza, Gianpaolo Oriolo and Gautier Stauffer, An algorithmicdecomposition of claw-free graphs leading to an $O(n^3)$-algorithm forthe weighted stable set problem (630--646) 2857152 ;Kevin P. Costello, Asaf Shapira and Prasad Tetali, Randomizedgreedy: new variants of some classic approximation algorithms(647--655) 2857153 ; Matthias Poloczek and Georg\Schnitger, Randomized variants of Johnson's algorithm for MAX SAT(656--663) 2857154 ; H. Gebauer [Heidi Gebauer],T. Szabó [Tibor Szabó] and G. Tardos [Gábor Tardos], Thelocal lemma is tight for SAT (664--674) 2857155 ;Fabrizio Grandoni [Fabrizio Grandoni\asup{2}] and Thomas Rothvoß,Pricing on paths: a PTAS for the highway problem (675--684) 2857156 ; Ning Chen [Ning Chen\asup{5}], Nick Gravin [N.\V. Gravin] and Pinyan Lu, On the approximability of budget feasiblemechanisms (685--699) 2857157 ; Kshipra Bhawalkar\and Tim Roughgarden, Welfare guarantees for combinatorial auctionswith item bidding (700--709) 2857158 ; Qiqi Yan,Mechanism design via correlation gap (710--719) 2857159 ; Xiaohui Bei and Zhiyi Huang [Zhiyi Huang\asup{1}], Bayesian incentive compatibility via fractional assignments(720--733) 2857160 ; Jason D. Hartline, Robert\Kleinberg [Robert D. Kleinberg] and Azarakhsh Malekian, Bayesianincentive compatibility via matchings (734--747) 2857161 ; Fedor V. Fomin, Daniel Lokshtanov, Venkatesh\Raman and Saket Saurabh, Bidimensionality and EPTAS (748--759) 2857162 . \parDaniel Lokshtanov, Dániel Marx andSaket Saurabh, Slightly superexponential parameterized problems(760--776) 2857163 ; Daniel Lokshtanov, Dániel\Marx and Saket Saurabh, Known algorithms on graphs of boundedtreewidth are probably optimal (777--789) 2857164 ;Constantinos Daskalakis and Christos Papadimitriou [Christos H.\Papadimitriou], Continuous local search (790--804) 2857165 ; Allan Grønlund Jørgensen and Kasper Green\Larsen, Range selection and median: tight cell probe lower bounds andadaptive data structures (805--813) 2857166 ;William T. Freeman, Where computer vision needs help from computerscience (814--819) 2857167 ; Shay Solomon, Anoptimal-time construction of sparse Euclidean spanners with tinydiameter (820--839) 2857168 ; Yair Bartal, Lee-Ad\Gottlieb [Lee-Ad J. Gottlieb], Tsvi Kopelowitz, Moshe Lewenstein\and Liam Roditty, Fast, precise and dynamic distance queries(840--853) 2857169 ; Sariel Har-Peled and Nirman\Kumar, Approximate nearest neighbor search for low dimensional queries(854--867) 2857170 ; Yair Bartal, Ben Recht[Benjamin Recht] and Leonard J. Schulman, Dimensionalityreduction: beyond the Johnson-Lindenstrauss bound (868--887) 2857171 ; Lee-Ad Gottlieb [Lee-Ad J. Gottlieb] andRobert Krauthgamer, A nonlinear approach to dimension reduction(888--899) 2857172 ; Sonny Ben-Shimon, Asaf Ferber,Dan Hefetz and Michael Krivelevich, Hitting time results formaker-breaker games: extended abstract (900--912) 2857173 . \parAlan Frieze [Alan M. Frieze], Michael\Krivelevich and Po-Shen Loh, Packing tight Hamilton cycles in3-uniform hypergraphs (913--932) 2857174 ; Colin\Cooper, Martin Dyer and Andrew J. Handley, Networks of randomcycles (933--944) 2857175 ; Ricardo Restrepo[Ricardo Restrepo López], Daniel Stefankovic [Daniel Štefankovič], Juan C. Vera [Juan Carlos Vera], Eric Vigoda\and Linji Yang, Phase transition for Glauber dynamics for independentsets on regular trees (945--956) 2857176 ; Amin\Coja-Oghlan, On belief propagation guided decimation for random$k$-SAT (957--966) 2857177 ; Shayan Oveis Gharan andAmin Saberi, The asymmetric traveling salesman problem on graphs withbounded genus (967--975) 2857178 ; Matthew Andrews[Daniel Matthew Andrews], Mohammad Taghi Hajiaghayi, Howard\Karloff [Howard J. Karloff] and Ankur Moitra, Capacitated metriclabeling (976--995) 2857179 ; Laura J. Poplawski\and Rajmohan Rajaraman, Multicommodity facility location under groupSteiner access cost (996--1013) 2857180 ; Debmalya\Panigrahi, Survivable network design problems in wireless networks(1014--1027) 2857181 ; M. Bateni [MohammadHossein\Bateni], C. Chekuri [Chandra Chekuri], A. Ene [Alina Ene], M. T.\Hajiaghayi [Mohammad Taghi Hajiaghayi], N. Korula [Nitish Korula]\and D. Marx [Dániel Marx], Prize-collecting Steiner problems onplanar graphs (1028--1049) 2857182 ; Julia Chuzhoy,Yury Makarychev and Anastasios Sidiropoulos, On graph crossingnumber and edge planarization (1050--1069) 2857183 ;Yossi Azar and Iftah Gamzu, Ranking with submodular valuations(1070--1079) 2857184 . \parChandra Chekuri, Jan\Vondrák and Rico Zenklusen, Multi-budgeted matchings and matroidintersection via dependent rounding (1080--1097) 2857185 ; Shayan Oveis Gharan and Jan Vondrák, Submodularmaximization by simulated annealing (1098--1116) 2857186 ; Ravishankar Krishnaswamy, Amit Kumar [Amit\Kumar\asup{2}], Viswanath Nagarajan, Yogish Sabharwal and Barna\Saha, The matroid median problem (1117--1130) 2857187 ; Timothy M. Chan [Timothy M. Y. Chan], Persistentpredecessor search and orthogonal point location on the word RAM(1131--1145) 2857188 ; Ankan Saha, S.\V. N. Vishwanathan and Xinhua Zhang, New approximation algorithmsfor minimum enclosing convex shapes (1146--1160) 2857189 ; Jacob Fox and János Pach, Computing theindependence number of intersection graphs (1161--1165) 2857190 ; Jeff Erickson and Amir Nayyeri, Minimum cuts andshortest non-separating cycles via homology covers (1166--1176) 2857191 ; Erik D. Demaine and André Schulz,Embedding stacked polytopes on a polynomial-size grid (1177--1187) 2857192 ; Jacob Fox, Mikhail Gromov, Vincent\Lafforgue, Assaf Naor and János Pach, Overlap properties ofgeometric expanders: extended abstract (1188--1197); Konstantinos\Panagiotou and Angelika Steger, On the degree distribution of randomplanar graphs (1198--1210) 2858393 ; Colin Cooper\and Alan Frieze [Alan M. Frieze], Component structure of the vacantset induced by a random walk on a random graph (1211--1221) 2858394 . \parNikolaos Fountoulakis, Megha Khosla andKonstantinos Panagiotou, The multiple-orientability thresholds forrandom hypergraphs (1222--1236) 2858395 ; Shiva\Prasad Kasiviswanathan, Cristopher Moore and Louis Theran, Therigidity transition in random graphs (1237--1252) 2858396 ; Gagan Aggarwal, Gagan Goel, Chinmay Karande andAranyak Mehta, Online vertex-weighted bipartite matching andsingle-bid budgeted allocations (1253--1264) 2858397 ; Sungjin Im and Yajun Wang [Ya Jun Wang\asup{1}],Secretary problems: laminar matroid and interval scheduling(1265--1274) 2858398 ; José A. Soto [JoséAntonio Soto], Matroid secretary problem in the random assignmentmodel (1275--1284) 2858399 ; Vahideh H. Manshadi,Shayan Oveis Gharan and Amin Saberi, Online stochastic matching:online actions based on offline statistics (1285--1294) 2858400 ; Marcin Bienkowski, An optimal lower bound forbuffer management in multi-queue switches (1295--1305) 2858401 ; George B. Mertzios, An intersection model formultitolerance graphs: efficient algorithms and hierarchy (1306--1317) 2858402 ; Krishnendu Chatterjee and Monika\Henzinger [Monika Rauch Henzinger], Faster and dynamic algorithmsfor maximal end-component decomposition and related graph problems inprobabilistic verification (1318--1336) 2858403 ;Virginia Vassilevska Williams, Faster replacement paths (1337--1346) 2858404 ; Jeff Erickson and Amir Nayyeri,Computing replacement paths in surface embedded graphs (1347--1354) 2858405 . \parAaron Bernstein and Liam Roditty,Improved dynamic algorithms for maintaining approximate shortest pathsunder deletions (1355--1365) 2858406 ; Ho Yee\Cheung, Lap Chi Lau and Kai Man Leung, Algebraic algorithms forlinear matroid parity problems (1366--1382) 2858407 ;Nader H. Bshouty and Hanna Mazzawi, On parity check $(0,1)$-matrixover $\Bbb Z_p$ (1383--1394) 2858408 ; László\Babai, Paolo Codenotti, Joshua A. Grochow and Youming Qiao, Codeequivalence and group isomorphism (1395--1408) 2858409 ; Neeraj Kayal, Efficient algorithms for somespecial cases of the polynomial equivalence problem (1409--1421) 2858410 ; Avner Magen and Anastasios Zouzias, Lowrank matrix-valued Chernoff bounds and approximate matrixmultiplication (1422--1436) 2858411 ; Timothy Chan,Computational geometry for non-geometers: recent developments on someclassical problems (1437); Jakub Łącki, Improveddeterministic algorithms for decremental transitive closure andstrongly connected components (1438--1445) 2858412 ;Liam Roditty and Roei Tov, Approximating the girth (1446--1454) 2858413 ; Yuval Emek, Amos Korman and Yuval\Shavitt, Approximating the statistics of various properties inrandomly weighted graphs (1455--1467) 2858414 ;Mirosław Kowaluk, Andrzej Lingas and Eva-Marta Lundell, Countingand detecting small subgraph via equations and matrix multiplication(1468--1476) 2858415 . \parXin He [Xin He\asup{1}] andHuaming Zhang, On succinct convex greedy drawing of 3-connected planegraphs (1477--1486) 2858416 ; Petra Berenbrink,Martin Hoefer and Thomas Sauerwald, Distributed selfish loadbalancing on networks (1487--1497) 2858417 ;Constantinos Daskalakis, On the complexity of approximating a Nashequilibrium (1498--1517) 2858418 ; Yashodhan\Kanoria, Mohsen Bayati, Christian Borgs, Jennifer Chayes andAndrea Montanari, Fast convergence of natural bargaining dynamics inexchange networks (1518--1537) 2858419 ; Magnús\M. Halldórsson and Pradipta Mitra [Pradipta Prometheus Mitra],Wireless capacity with oblivious power in general metrics (1538--1548) 2858420 ; Thomas Kesselheim, A constant-factorapproximation for wireless capacity maximization with power control inthe SINR model (1549--1559) 2858421 ; Amit Kumar[Amit Kumar\asup{2}], Rajsekar Manokaran, Madhur Tulsiani andNisheeth K. Vishnoi, On LP-based approximability for strict CSPs(1560--1573) 2858422 ; Venkatesan Guruswami andYuan Zhou [Yuan Zhou\asup{5}], Tight bounds on the approximability ofalmost-satisfiable Horn SAT and exact hitting set (1574--1589) 2858423 ; Ilias Diakonikolas, Ryan O'Donnell, Rocco A.\Servedio and Yi Wu [Yi Wu\asup{3}], Hardness results foragnostically learning low-degree polynomial threshold functions(1590--1606) 2841301 ; Moses Charikar, Alantha\Newman and Aleksandar Nikolov, Tight hardness results for minimizingdiscrepancy (1607--1614) 2858424 ; Venkatesan\Guruswami and Ali Kemal Sinop, The complexity of findingindependent sets in bounded degree (hyper)graphs of low chromaticnumber (1615--1626) 2858425 . \parChaitanya Swamy,Risk-averse stochastic optimization: probabilistically-constrainedmodels and algorithms for black-box distributions (extended abstract)(1627--1646); Anand Bhalgat, Ashish Goel and Sanjeev Khanna,Improved approximation results for stochastic knapsack problems(1647--1665) 2858426 ; Marek Cygan, Marcin\Pilipczuk, Michał Pilipczuk and Jakub Onufry Wojtaszczyk, Thestubborn problem is stubborn no more (a polynomial algorithm for3-compatible colouring and the stubborn list partition problem)(1666--1674) 2858427 ; Gary L. Miller [Gary Lee\Miller], Richard Peng, Russell Schwartz and Charalampos\Tsourakakis [Charalampos E. Tsourakakis], Approximate dynamicprogramming using halfspace queries and multiscale Monge decomposition(1675--1682) 2858428 ; Sourav Chakraborty, David\García-Soriano and Arie Matsliah, Nearly tight bounds fortesting function isomorphism (1683--1702) 2858429 ;Pavol Hell and Arash Rafiey, The dichotomy of list homomorphismsfor digraphs (1703--1713) 2858430 ; Jin-Yi Cai,Pinyan Lu and Mingji Xia, Dichotomy for ${\rm Holant}^*$ problemsof Boolean domain (1714--1728) 2858431 ; Kazuyuki\Amano, Bounding the randomized decision tree complexity of read-onceBoolean functions (1729--1744) 2858432 ; Peyman\Afshani and Norbert Zeh, Improved space bounds for cache-obliviousrange reporting (1745--1758) 2858433 ; Maarten\Löffler and Wolfgang Mulzer, Triangulating the square and squaringthe triangle: quadtrees and Delaunay triangulations are equivalent(1759--1777) 2858434 ; Esther Ezra, Boris Aronov\and Micha Sharir, Improved bound for the union of fat triangles(1778--1785) 2858435 .\par\{Most of the papers are being reviewed individually.\}