부산대학교 도서관

\{The 21st Symposium has been reviewed [ 2797147 ].\} \par Contents: T.\ S.\ Jayram\ and David\ Woodruff [David\ P.\ Woodruff], Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems 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 query problem (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\ and Jean-Philippe\ Gayon, A simple and fast 2-approximation algorithm for the 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 online scalable algorithm for minimizing $\ell_k$-norms of weighted flow time on 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 without conservation of work (109--119) 2857113 ; Kyle\ Fox\ and Benjamin\ Moseley, Online scheduling on identical machines using SRPT (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 the Keller maximum clique problem (129--135) 2857115 ; Amin\ Coja-Oghlan\ and Charilaos\ Efthymiou, On independent sets in random graphs (136--144) 2857116 . \par Torsten\ Mütze, Thomas\ Rast\ and Reto\ Spöhel, Coloring random graphs online without 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 sparse random set of integers (159--171) 2857118 ; Philippe\ Flajolet, Maryse\ Pelletier\ and Michèle\ Soria, On Buffon machines and numbers (172--183) 2857119 ; Bruce\ Reed, Graph coloring via the probabilistic method (184); Nir\ Ailon\ and Edo\ Liberty, An almost optimal unrestricted fast Johnson-Lindenstrauss transform (185--191) 2857120 ; Umang\ Bhaskar, Lisa\ Fleischer [Lisa\ K.\ Fleischer]\ and Elliot\ Anshelevich, A Stackelberg strategy for routing flow over time (192--201) 2857121 ; Oliver\ Friedmann, Thomas\ Dueholm\ Hansen\ and Uri\ Zwick, A subexponential lower bound for the random facet algorithm for parity games (202--216) 2857122 ; Yang\ Cai [Yang\ Cai\asup 1]\ and Constantinos\ Daskalakis, On minmax theorems 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 splittable congestion 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 terrains with applications to surface networks and drainage structures (285--296) 2857127 . \par Jeff\ Erickson\ and Amir\ Nayyeri, Shortest non-crossing walks in the plane (297--308) 2857128 ; Danny\ Z.\ Chen\ and Haitao\ Wang [Hai\ Tao Wang\asup 1], Computing shortest paths amid pseudodisks (309--326) 2857129 ; Luca\ Foschini, John\ Hershberger [John\ E.\ Hershberger]\ and Subhash\ Suri, On the complexity of time-dependent shortest paths (327--341) 2857130 ; Michael\ Drmota\ and Wojciech\ Szpankowski, A master theorem for discrete divide and conquer recurrences (342--361) 2857131 ; Paweł\ Gawrychowski, Optimal pattern matching in LZW compressed strings (362--372) 2857132 ; Philip\ Bille, Gad\ M.\ Landau, Rajeev\ Raman, Kunihiko\ Sadakane, Srinivasa\ Rao\ Satti [Satti\ Srinivasa\ Rao]\ and Oren\ Weimann, Random access to grammar-compressed strings (373--389) 2857133 ; Peyman\ Afshani, Gerth\ Stølting Brodal\ and Norbert\ Zeh, Ordered and 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\ and Alexandre\ Stauffer [Alexandre\ O.\ Stauffer], Mobile geometric graphs: detection, coverage and percolation (412--428) 2857136 ; Petra\ Berenbrink, Colin\ Cooper, Tom\ Friedetzky, Tobias\ Friedrich\ and Thomas\ Sauerwald, Randomized diffusion for indivisible loads (429--439) 2857137 ; Keren\ Censor-Hillel\ and Hadas\ Shachnai, Fast information spreading in graphs with large weak conductance (440--448) 2857138 ; George\ Giakkoupis\ and Philipp\ Woelfel, On the randomness requirements of rumor spreading (449--461) 2857139 . \par Thomas\ Sauerwald\ and Alexandre\ Stauffer [Alexandre\ O.\ Stauffer], Rumor spreading and vertex expansion on regular graphs (462--475) 2857140 ; Friedrich\ Eisenbrand, Dömötör\ Pálvölgyi\ and Thomas\ Rothvoß, Bin packing 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\ and David\ Steurer, Subsampling mathematical relaxations and average-case complexity (512--531) 2857144 ; Lorenzo\ Orecchia\ and Nisheeth\ K.\ Vishnoi, Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition (532--545) 2857145 ; Ben\ W.\ Reichardt, Faster quantum algorithm for evaluating game trees (546--559) 2857146 ; Ben\ W.\ Reichardt, Reflections for quantum query algorithms (560--569) 2857147 ; Matthew\ Cook, Yunhui\ Fu\ and Robert\ Schweller, Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D (570--589) 2857148 ; Nathaniel\ Bryans, Ehsan\ Chiniforooshan, David\ Doty, Lila\ Kari\ and Shinnosuke\ Seki, The power 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 implicit hitting set problems (614--629) 2857151 . \par Yuri\ Faenza, Gianpaolo\ Oriolo\ and Gautier\ Stauffer, An algorithmic decomposition of claw-free graphs leading to an $O(n^3)$-algorithm for the weighted stable set problem (630--646) 2857152 ; Kevin\ P.\ Costello, Asaf\ Shapira\ and Prasad\ Tetali, Randomized greedy: 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], The local 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 feasible mechanisms (685--699) 2857157 ; Kshipra\ Bhawalkar\ and Tim\ Roughgarden, Welfare guarantees for combinatorial auctions with 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, Bayesian incentive compatibility via matchings (734--747) 2857161 ; Fedor\ V.\ Fomin, Daniel\ Lokshtanov, Venkatesh\ Raman\ and Saket\ Saurabh, Bidimensionality and EPTAS (748--759) 2857162 . \par Daniel\ Lokshtanov, Dániel\ Marx\ and Saket\ Saurabh, Slightly superexponential parameterized problems (760--776) 2857163 ; Daniel\ Lokshtanov, Dániel\ Marx\ and Saket\ Saurabh, Known algorithms on graphs of bounded treewidth 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 and adaptive data structures (805--813) 2857166 ; William\ T.\ Freeman, Where computer vision needs help from computer science (814--819) 2857167 ; Shay\ Solomon, An optimal-time construction of sparse Euclidean spanners with tiny diameter (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, Dimensionality reduction: beyond the Johnson-Lindenstrauss bound (868--887) 2857171 ; Lee-Ad\ Gottlieb [Lee-Ad\ J.\ Gottlieb]\ and Robert\ Krauthgamer, A nonlinear approach to dimension reduction (888--899) 2857172 ; Sonny\ Ben-Shimon, Asaf\ Ferber, Dan\ Hefetz\ and Michael\ Krivelevich, Hitting time results for maker-breaker games: extended abstract (900--912) 2857173 . \par Alan\ Frieze [Alan\ M.\ Frieze], Michael\ Krivelevich\ and Po-Shen\ Loh, Packing tight Hamilton cycles in 3-uniform hypergraphs (913--932) 2857174 ; Colin\ Cooper, Martin\ Dyer\ and Andrew\ J.\ Handley, Networks of random cycles (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 independent sets on regular trees (945--956) 2857176 ; Amin\ Coja-Oghlan, On belief propagation guided decimation for random $k$-SAT (957--966) 2857177 ; Shayan Oveis Gharan\ and Amin\ Saberi, The asymmetric traveling salesman problem on graphs with bounded genus (967--975) 2857178 ; Matthew\ Andrews [Daniel\ Matthew\ Andrews], Mohammad\ Taghi\ Hajiaghayi, Howard\ Karloff [Howard\ J.\ Karloff]\ and Ankur\ Moitra, Capacitated metric labeling (976--995) 2857179 ; Laura\ J.\ Poplawski\ and Rajmohan\ Rajaraman, Multicommodity facility location under group Steiner 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 on planar graphs (1028--1049) 2857182 ; Julia\ Chuzhoy, Yury\ Makarychev\ and Anastasios\ Sidiropoulos, On graph crossing number and edge planarization (1050--1069) 2857183 ; Yossi\ Azar\ and Iftah\ Gamzu, Ranking with submodular valuations (1070--1079) 2857184 . \par Chandra\ Chekuri, Jan\ Vondrák\ and Rico\ Zenklusen, Multi-budgeted matchings and matroid intersection via dependent rounding (1080--1097) 2857185 ; Shayan Oveis Gharan\ and Jan\ Vondrák, Submodular maximization 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], Persistent predecessor search and orthogonal point location on the word RAM (1131--1145) 2857188 ; Ankan\ Saha, S.\ V. N. Vishwanathan\ and Xinhua\ Zhang, New approximation algorithms for minimum enclosing convex shapes (1146--1160) 2857189 ; Jacob\ Fox\ and János\ Pach, Computing the independence number of intersection graphs (1161--1165) 2857190 ; Jeff\ Erickson\ and Amir\ Nayyeri, Minimum cuts and shortest 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 of geometric expanders: extended abstract (1188--1197); Konstantinos\ Panagiotou\ and Angelika\ Steger, On the degree distribution of random planar graphs (1198--1210) 2858393 ; Colin\ Cooper\ and Alan\ Frieze [Alan\ M.\ Frieze], Component structure of the vacant set induced by a random walk on a random graph (1211--1221) 2858394 . \par Nikolaos\ Fountoulakis, Megha\ Khosla\ and Konstantinos\ Panagiotou, The multiple-orientability thresholds for random hypergraphs (1222--1236) 2858395 ; Shiva\ Prasad\ Kasiviswanathan, Cristopher\ Moore\ and Louis\ Theran, The rigidity transition in random graphs (1237--1252) 2858396 ; Gagan\ Aggarwal, Gagan\ Goel, Chinmay\ Karande\ and Aranyak\ Mehta, Online vertex-weighted bipartite matching and single-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 assignment model (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 for buffer management in multi-queue switches (1295--1305) 2858401 ; George\ B.\ Mertzios, An intersection model for multitolerance graphs: efficient algorithms and hierarchy (1306--1317) 2858402 ; Krishnendu\ Chatterjee\ and Monika\ Henzinger [Monika\ Rauch\ Henzinger], Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic 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 . \par Aaron\ Bernstein\ and Liam\ Roditty, Improved dynamic algorithms for maintaining approximate shortest paths under deletions (1355--1365) 2858406 ; Ho\ Yee\ Cheung, Lap\ Chi\ Lau\ and Kai\ Man\ Leung, Algebraic algorithms for linear matroid parity problems (1366--1382) 2858407 ; Nader\ H.\ Bshouty\ and Hanna\ Mazzawi, On parity check $(0,1)$-matrix over $\Bbb Z_p$ (1383--1394) 2858408 ; László\ Babai, Paolo\ Codenotti, Joshua\ A.\ Grochow\ and Youming\ Qiao, Code equivalence and group isomorphism (1395--1408) 2858409 ; Neeraj\ Kayal, Efficient algorithms for some special cases of the polynomial equivalence problem (1409--1421) 2858410 ; Avner\ Magen\ and Anastasios\ Zouzias, Low rank matrix-valued Chernoff bounds and approximate matrix multiplication (1422--1436) 2858411 ; Timothy\ Chan, Computational geometry for non-geometers: recent developments on some classical problems (1437); Jakub\ Łącki, Improved deterministic algorithms for decremental transitive closure and strongly 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 in randomly weighted graphs (1455--1467) 2858414 ; Mirosław\ Kowaluk, Andrzej\ Lingas\ and Eva-Marta\ Lundell, Counting and detecting small subgraph via equations and matrix multiplication (1468--1476) 2858415 . \par Xin\ He [Xin\ He\asup 1]\ and Huaming\ Zhang, On succinct convex greedy drawing of 3-connected plane graphs (1477--1486) 2858416 ; Petra\ Berenbrink, Martin\ Hoefer\ and Thomas\ Sauerwald, Distributed selfish load balancing on networks (1487--1497) 2858417 ; Constantinos\ Daskalakis, On the complexity of approximating a Nash equilibrium (1498--1517) 2858418 ; Yashodhan\ Kanoria, Mohsen\ Bayati, Christian\ Borgs, Jennifer\ Chayes\ and Andrea\ Montanari, Fast convergence of natural bargaining dynamics in exchange 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-factor approximation for wireless capacity maximization with power control in the SINR model (1549--1559) 2858421 ; Amit\ Kumar [Amit\ Kumar\asup 2], Rajsekar\ Manokaran, Madhur\ Tulsiani\ and Nisheeth\ K.\ Vishnoi, On LP-based approximability for strict CSPs (1560--1573) 2858422 ; Venkatesan\ Guruswami\ and Yuan\ Zhou [Yuan\ Zhou\asup 5], Tight bounds on the approximability of almost-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 for agnostically learning low-degree polynomial threshold functions (1590--1606) 2841301 ; Moses\ Charikar, Alantha\ Newman\ and Aleksandar\ Nikolov, Tight hardness results for minimizing discrepancy (1607--1614) 2858424 ; Venkatesan\ Guruswami\ and Ali\ Kemal\ Sinop, The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number (1615--1626) 2858425 . \par Chaitanya\ Swamy, Risk-averse stochastic optimization: probabilistically-constrained models 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, The stubborn problem is stubborn no more (a polynomial algorithm for 3-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 dynamic programming using halfspace queries and multiscale Monge decomposition (1675--1682) 2858428 ; Sourav\ Chakraborty, David\ García-Soriano\ and Arie\ Matsliah, Nearly tight bounds for testing function isomorphism (1683--1702) 2858429 ; Pavol\ Hell\ and Arash\ Rafiey, The dichotomy of list homomorphisms for digraphs (1703--1713) 2858430 ; Jin-Yi\ Cai, Pinyan\ Lu\ and Mingji\ Xia, Dichotomy for ${\rm Holant}^*$ problems of Boolean domain (1714--1728) 2858431 ; Kazuyuki\ Amano, Bounding the randomized decision tree complexity of read-once Boolean functions (1729--1744) 2858432 ; Peyman\ Afshani\ and Norbert\ Zeh, Improved space bounds for cache-oblivious range reporting (1745--1758) 2858433 ; Maarten\ Löffler\ and Wolfgang\ Mulzer, Triangulating the square and squaring the 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.\}