부산대학교 도서관

{\bf Papers in this collection include the following:}\tpar\{For the 57th Symposium see [MR3630959].\} \tparMark Bun\and Justin Thaler, ``A nearly optimal lower bound on the approximatedegree of ${\rm AC}^0$'', \nbp{1--12}. 3734213\tparHuck Bennett, Noah Stephens-Davidowitz and Alexander Golovnev, ``Onthe quantitative hardness of CVP'', \nbp{13--24}. 3734214\tparAmir Abboud, Aviad Rubinstein and Ryan Williams, ``Distributed PCPtheorems for hardness of approximation in P (extended abstract)'',\nbp{25--36}. 3734215\tparDanny Nguyen and Igor Pak, ``Short Presburger arithmetic is hard'',\nbp{37--48}. 3734216\tparVincent Cohen-Addad and Chris Schwiegelshohn, ``On the localstructure of stable clustering instances'', \nbp{49--60}. 3734217\tparSara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson and Justin Ward,``Better guarantees for $k$-means and Euclidean $k$-median byprimal-dual algorithms'', \nbp{61--72}. 3734218\tparIlias Diakonikolas, Daniel M. Kane and Alistair Stewart,``Statistical query lower bounds for robust estimation ofhigh-dimensional Gaussians and Gaussian mixtures (extended abstract)'',\nbp{73--84}. 3734219\tparOded Regev and Aravindan Vijayaraghavan, ``On learning mixtures ofwell-separated Gaussians'', \nbp{85--96}. 3734220\tparJohan Håstad, ``On small-depth Frege proofs for Tseitin forgrids'', \nbp{97--108}. 3734221\tparNoah Fleming, Denis Pankratov, Toniann Pitassi and Robert Robere,``Random $\Theta(\log n)$-CNFs are hard for cutting planes'',\nbp{109--120}. 3734222\tparPavel Hrubeš and Pavel Pudlák, ``Random formulas, monotonecircuits, and interpolation'', \nbp{121--131}. 3734223\tparMika Göös, Toniann Pitassi and Thomas Watson,``Query-to-communication lifting for $\ssf{BPP}$'', \nbp{132--143}.3734224\tparMark Braverman and Rotem Oshman, ``A rounds vs. communicationtradeoff for multi-party set disjointness'', \nbp{144--155}. 3734225\tparYi-Jun Chang and Seth Pettie, ``A time hierarchy theorem for theLOCAL model'', \nbp{156--167}. 3734226\tparChien-Chung Huang, Danupon Nanongkai and Thatchaphol Saranurak,``Distributed exact weighted all-pairs shortest paths in $\tildeO(n^{5/4})$ rounds'', \nbp{168--179}. 3734227\tparManuela Fischer, Mohsen Ghaffari and Fabian Kuhn, ``Deterministicdistributed edge-coloring via hypergraph maximal matching'',\nbp{180--191}. 3734228\tparAmir Abboud, Arturs Backurs, Karl Bringmann and Marvin\Künnemann, ``Fine-grained complexity of analyzing compressed data:quantifying improvements over decompress-and-solve'', \nbp{192--203}.3734229\tparBrett Hemenway, Noga Ron-Zewi and Mary Wootters, ``Local listrecovery of high-rate tensor codes \& applications'', \nbp{204--215}.3734230\tparItzhak Tamo, Min Ye and Alexander Barg, ``Optimal repair ofReed-Solomon codes: achieving the cut-set bound'', \nbp{216--227}.3734231\tparYuval Peres and Alex Zhai, ``Average-case reconstruction for thedeletion channel: subpolynomially many traces suffice'',\nbp{228--239}. 3734232\tparAlexander A. Sherstov and Pei Wu, ``Optimal interactive coding forinsertions, deletions, and substitutions'', \nbp{240--251}. 3734233\tparDaniel Kane, Shachar Lovett and Sankeerth Rao, ``The independencenumber of the Birkhoff polytope graph, and applications to maximallyrecoverable codes'', \nbp{252--259}. 3734234\tparWaldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore\Ingala, Arindam Khan and Andreas Wiese, ``Approximating geometricknapsack via L-packings'', \nbp{260--271}. 3734235\tparMark de Berg, ``Removing depth-order cycles among triangles: anefficient algorithm generating triangular fragments'', \nbp{272--282}.3734236\tparShi Li, ``Scheduling to minimize total weighted completion time viatime-indexed linear programming relaxations'', \nbp{283--294}. 3734237\tparBarna Saha, ``Fast \& space-efficient approximations of language editdistance and RNA folding: an amnesic dynamic programming approach'',\nbp{295--306}. 3734238\tparKarl Bringmann, Allan Grønlund and Kasper Green Larsen, ``Adichotomy for regular expression membership testing'', \nbp{307--318}.3734239\tparAndrei A. Bulatov, ``A dichotomy theorem for nonuniform CSPs'',\nbp{319--330}. 3734240\tparDmitriy Zhuk, ``A proof of CSP dichotomy conjecture'', \nbp{331--342}.3734241\tparAdam R. Klivans and Raghu Meka, ``Learning graphical models usingmultiplicative weights'', \nbp{343--354}. 3734242\tparDaniel M. Kane, Shachar Lovett, Shay Moran and Jiapeng Zhang,``Active classification with comparison queries'', \nbp{355--366}.3734243\tparLeslie G. Valiant, ``Capacity of neural networks for lifelonglearning of composable tasks'', \nbp{367--378}. 3734244\tparSamuel B. Hopkins and David Steurer, ``Efficient Bayesianestimation from few samples: community detection and relatedproblems'', \nbp{379--390}. 3734245\tparDaniel Kane, Sushrut Karmalkar and Eric Price, ``Robust polynomialregression up to the information theoretic limit'', \nbp{391--402}.3734246\tparJoran van Apeldoorn, András Gilyén, Sander Gribling and Ronald\de Wolf, ``Quantum SDP-solvers: better upper and lower bounds'',\nbp{403--414}. 3734247\tparFernando G. S. L. Brandao and Krysta M. Svore, ``Quantum speed-upsfor solving semidefinite programs'', \nbp{415--426}. 3734248\tparLior Eldar and Aram W. Harrow, ``Local Hamiltonians whose groundstates are hard to approximate'', \nbp{427--438}. 3734249\tparAndrás Gilyén and Or Sattath, ``On preparing ground states ofgapped Hamiltonians: an efficient quantum Lovász local lemma'',\nbp{439--450}. 3734250\tparKun He, Liang Li, Xingwu Liu, Yuyi Wang and Mingji Xia,``Variable-version Lovász local lemma: beyond Shearer's bound'',\nbp{451--462}. 3734251\tparYinan Li and Youming Qiao, ``Linear algebraic analogues of the graphisomorphism problem and the Erdős-Rényi model (extendedabstract)'', \nbp{463--474}. 3734252\tparMichael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang,David P. Woodruff and Mobin Yahyazadeh, ``Optimal lower bounds foruniversal relation, and for samplers and finding duplicates instreams'', \nbp{475--486}. 3734253\tparZeyuan Allen-Zhu and Yuanzhi Li, ``First efficient convergence forstreaming $k$-PCA: a global, gap-free, and near-optimal rate'',\nbp{487--492}. 3734254\tparNikhil Bansal, Marek Eliáš and Grigorios Koumoutsos,``Weighted $k$-server bounds via combinatorial dichotomies'',\nbp{493--504}. 3734255\tparKrati Nayyar and Sharath Raghvendra, ``An input sensitive onlinealgorithm for the metric bipartite matching problem'', \nbp{505--515}.3734256\tparYang Cai and Constantinos Daskalakis, ``Learning multi-item auctionswith (or without) samples'', \nbp{516--527}. 3734257\tparMiroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E.\Schapire, Vasilis Syrgkanis and Jennifer Wortman Vaughan,``Oracle-efficient online learning and auction design'',\nbp{528--539}. 3734258\tparPaul Dütting, Michal Feldman, Thomas Kesselheim and Brendan\Lucier, ``Prophet inequalities made easy: stochastic optimization bypricing non-stochastic inputs'', \nbp{540--551}. 3734259\tparThomas Steinke and Jonathan Ullman, ``Tight lower bounds fordifferentially private selection'', \nbp{552--563}. 3734260\tparDakshita Khurana and Amit Sahai, ``How to achieve non-malleabilityin one or two rounds'', \nbp{564--575}. 3734261\tparHuijia Lin, Rafael Pass and Pratik Soni, ``Two-round andnon-interactive concurrent non-malleable commitments from time-lockpuzzles'', \nbp{576--587}. 3734262\tparSanjam Garg and Akshayaram Srinivasan, ``Garbled protocols andtwo-round MPC from bilinear maps'', \nbp{588--599}. 3734263\tparDaniel Wichs and Giorgos Zirdelis, ``Obfuscating compute-and-compareprograms under LWE'', \nbp{600--611}. 3734264\tparRishab Goyal, Venkata Koppula and Brent Waters, ``Lockableobfuscation'', \nbp{612--621}. 3734265\tparIlan Komargodski, Moni Naor and Eylon Yogev, ``White-box vs.black-box complexity of search problems: Ramsey and graph propertytesting'', \nbp{622--632}. 3734266\tparKasper Green Larsen and Jelani Nelson, ``Optimality of theJohnson-Lindenstrauss lemma'', \nbp{633--638}. 3734267\tparNoga Alon and Bo'az Klartag, ``Optimal compression of approximateinner products and dimension reduction'', \nbp{639--650}. 3734268\tparMichael Kapralov, ``Sample efficient estimation and recovery in sparseFFT via isolation on average'', \nbp{651--662}. 3734269\tparSøren Dahlgaard, Mathias Bæk Tejs Knudsen and Mikkel Thorup,``Fast similarity sketching'', \nbp{663--671}. 3734270\tparCameron Musco and David P. Woodruff, ``Sublinear time low-rankapproximation of positive semidefinite matrices'', \nbp{672--683}.3734271\tparRasmus Kyng and Peng Zhang, ``Hardness results for structured linearsystems'', \nbp{684--695}. 3734272\tparOla Svensson and Jakub Tarnawski, ``The matching problem in generalgraphs is in quasi-NC'', \nbp{696--707}. 3734273\tparAdam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler andPrashant Nalini Vasudevan, ``On the power of statistical zeroknowledge'', \nbp{708--719}. 3734274\tparSamuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad\Raghavendra, Tselil Schramm and David Steurer, ``The power ofsum-of-squares for detecting hidden structures'', \nbp{720--731}.3734275\tparRan Raz, ``A time-space lower bound for a large class of learningproblems'', \nbp{732--742}. 3734276\tparParinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit,Pasin Manurangsi, Danupon Nanongkai and Luca Trevisan, ``Fromgap-ETH to FPT-inapproximability: clique, dominating set, and more'',\nbp{743--754}. 3734277\tparDavid R. Karger, ``Faster (and still pretty simple) unbiasedestimators for network (un)reliability'', \nbp{755--766}. 3734278\tparGlencora Borradaile, Hung Le and Christian Wulff-Nilsen,``Minor-free graphs have light spanners'', \nbp{767--778}. 3734279\tparKen-ichi Kawarabayashi and Anastasios Sidiropoulos,``Polylogarithmic approximation for minimum planarization (almost)'',\nbp{779--788}. 3734280\tparChandra Chekuri and Kent Quanrud, ``Approximating the Held-Karpbound for metric TSP in nearly-linear time'', \nbp{789--800}. 3734281\tparJack Murtagh, Omer Reingold, Aaron Sidford and Salil Vadhan,``Derandomization beyond connectivity: undirected Laplacian systems innearly logarithmic space'', \nbp{801--812}. 3734282\tparRocco A. Servedio and Li-Yang Tan, ``Deterministic search for CNFsatisfying assignments in almost polynomial time'', \nbp{813--823}.3734283\tparRocco A. Servedio and Li-Yang Tan, ``Fooling intersections oflow-weight halfspaces'', \nbp{824--835}. 3734284\tparBenny Applebaum, ``Exponentially-hard gap-CSP and local PRG via localhardcore functions'', \nbp{836--847}. 3734285\tparNoga Alon, Omri Ben-Eliezer and Eldar Fischer, ``Testing hereditaryproperties of ordered graphs and matrices'', \nbp{848--858}. 3734286\tparFelix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus, ``Acharacterization of testable hypergraph properties (extendedabstract)'', \nbp{859--867}. 3734287\tparXi Chen, Erik Waingarten and Jinyu Xie, ``Boolean unateness testingwith $\widetilde O(n^{3/4})$ adaptive queries'', \nbp{868--879}. 3734288\tparTuğkan Batu and Clément L. Canonne, ``Generalized uniformitytesting'', \nbp{880--889}. 3734289\tparZeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira and Avi Wigderson,``Much faster algorithms for matrix scaling'', \nbp{890--901}. 3734290\tparMichael B. Cohen, Aleksander Mądry, Dimitris Tsipras andAdrian Vladu, ``Matrix scaling and balancing via box constrainedNewton's method and interior point methods'', \nbp{902--913}. 3734291\tparNima Anari, Leonid Gurvits, Shayan Oveis Gharan and Amin Saberi,``Simply exponential approximation of the permanent of positivesemidefinite matrices'', \nbp{914--925}. 3734292\tparDavid Durfee, John Peebles, Richard Peng and Anup B. Rao,``Determinant-preserving sparsification of SDDM matrices withapplications to counting and sampling spanning trees'', \nbp{926--937}.3734293\tparThomas D. Ahle, ``Optimal Las Vegas locality sensitive datastructures'', \nbp{938--949}. 3734294\tparDanupon Nanongkai, Thatchaphol Saranurak and Christian\Wulff-Nilsen, ``Dynamic minimum spanning forest with subpolynomialworst-case update time'', \nbp{950--961}. 3734295\tparVincent Cohen-Addad, Søren Dahlgaard and Christian Wulff-Nilsen,``Fast and compact exact distance oracle for planar graphs'',\nbp{962--973}. 3734296\tparIrit Dinur and Tali Kaufman, ``High dimensional expanders implyagreement expanders'', \nbp{974--985}. 3734297\tparJingcheng Liu, Alistair Sinclair and Piyush Srivastava, ``The Isingpartition function: zeros and deterministic approximation'',\nbp{986--997}. 3734298\tparYin Tat Lee and Santosh S. Vempala, ``Eldan's stochasticlocalization and the KLS hyperplane conjecture: an improved lower boundfor expansion'', \nbp{998--1007}. 3734299\tparVijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Mrinalkanti\Ghosh and Madhur Tulsiani, ``Weak decoupling, polynomial folds, andapproximate optimization over the sphere'', \nbp{1008--1019}. 3734300\tparJavad B. Ebrahimi, Damian Straszak and Nisheeth K. Vishnoi,``Subdeterminant maximization via nonconvex relaxations andanti-concentration (extended abstract)'', \nbp{1020--1031}. 3734301\tparMoses Charikar and Paris Siminelakis, ``Hashing-based-estimators forkernel density in high dimensions'', \nbp{1032--1043}. 3734302\tpar