부산대학교 도서관

{\bf Papers in this collection include the following:} \tpar \{For the 57th Symposium see [MR3630959].\} \tpar Mark\ Bun\ and Justin\ Thaler, ``A nearly optimal lower bound on the approximate degree of ${\rm AC}^0$'', \nbp{1--12}. 3734213 \tpar Huck\ Bennett, Noah\ Stephens-Davidowitz\ and Alexander\ Golovnev, ``On the quantitative hardness of CVP'', \nbp{13--24}. 3734214 \tpar Amir\ Abboud, Aviad\ Rubinstein\ and Ryan\ Williams, ``Distributed PCP theorems for hardness of approximation in P (extended abstract)'', \nbp{25--36}. 3734215 \tpar Danny\ Nguyen\ and Igor\ Pak, ``Short Presburger arithmetic is hard'', \nbp{37--48}. 3734216 \tpar Vincent\ Cohen-Addad\ and Chris\ Schwiegelshohn, ``On the local structure of stable clustering instances'', \nbp{49--60}. 3734217 \tpar Sara\ Ahmadian, Ashkan\ Norouzi-Fard, Ola\ Svensson\ and Justin\ Ward, ``Better guarantees for $k$-means and Euclidean $k$-median by primal-dual algorithms'', \nbp{61--72}. 3734218 \tpar Ilias\ Diakonikolas, Daniel\ M.\ Kane\ and Alistair\ Stewart, ``Statistical query lower bounds for robust estimation of high-dimensional Gaussians and Gaussian mixtures (extended abstract)'', \nbp{73--84}. 3734219 \tpar Oded\ Regev\ and Aravindan\ Vijayaraghavan, ``On learning mixtures of well-separated Gaussians'', \nbp{85--96}. 3734220 \tpar Johan\ Håstad, ``On small-depth Frege proofs for Tseitin for grids'', \nbp{97--108}. 3734221 \tpar Noah\ Fleming, Denis\ Pankratov, Toniann\ Pitassi\ and Robert\ Robere, ``Random $\Theta(\log n)$-CNFs are hard for cutting planes'', \nbp{109--120}. 3734222 \tpar Pavel\ Hrubeš\ and Pavel\ Pudlák, ``Random formulas, monotone circuits, and interpolation'', \nbp{121--131}. 3734223 \tpar Mika\ Göös, Toniann\ Pitassi\ and Thomas\ Watson, ``Query-to-communication lifting for $\ssf{BPP}$'', \nbp{132--143}. 3734224 \tpar Mark\ Braverman\ and Rotem\ Oshman, ``A rounds vs. communication tradeoff for multi-party set disjointness'', \nbp{144--155}. 3734225 \tpar Yi-Jun\ Chang\ and Seth\ Pettie, ``A time hierarchy theorem for the LOCAL model'', \nbp{156--167}. 3734226 \tpar Chien-Chung\ Huang, Danupon\ Nanongkai\ and Thatchaphol\ Saranurak, ``Distributed exact weighted all-pairs shortest paths in $\tilde O(n^{5/4})$ rounds'', \nbp{168--179}. 3734227 \tpar Manuela\ Fischer, Mohsen\ Ghaffari\ and Fabian\ Kuhn, ``Deterministic distributed edge-coloring via hypergraph maximal matching'', \nbp{180--191}. 3734228 \tpar Amir\ 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 \tpar Brett\ Hemenway, Noga\ Ron-Zewi\ and Mary\ Wootters, ``Local list recovery of high-rate tensor codes \& applications'', \nbp{204--215}. 3734230 \tpar Itzhak\ Tamo, Min\ Ye\ and Alexander\ Barg, ``Optimal repair of Reed-Solomon codes: achieving the cut-set bound'', \nbp{216--227}. 3734231 \tpar Yuval\ Peres\ and Alex\ Zhai, ``Average-case reconstruction for the deletion channel: subpolynomially many traces suffice'', \nbp{228--239}. 3734232 \tpar Alexander\ A.\ Sherstov\ and Pei\ Wu, ``Optimal interactive coding for insertions, deletions, and substitutions'', \nbp{240--251}. 3734233 \tpar Daniel\ Kane, Shachar\ Lovett\ and Sankeerth\ Rao, ``The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes'', \nbp{252--259}. 3734234 \tpar Waldo\ Gálvez, Fabrizio\ Grandoni, Sandy\ Heydrich, Salvatore\ Ingala, Arindam\ Khan\ and Andreas\ Wiese, ``Approximating geometric knapsack via L-packings'', \nbp{260--271}. 3734235 \tpar Mark\ de Berg, ``Removing depth-order cycles among triangles: an efficient algorithm generating triangular fragments'', \nbp{272--282}. 3734236 \tpar Shi\ Li, ``Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations'', \nbp{283--294}. 3734237 \tpar Barna\ Saha, ``Fast \& space-efficient approximations of language edit distance and RNA folding: an amnesic dynamic programming approach'', \nbp{295--306}. 3734238 \tpar Karl\ Bringmann, Allan\ Grønlund\ and Kasper\ Green\ Larsen, ``A dichotomy for regular expression membership testing'', \nbp{307--318}. 3734239 \tpar Andrei\ A.\ Bulatov, ``A dichotomy theorem for nonuniform CSPs'', \nbp{319--330}. 3734240 \tpar Dmitriy\ Zhuk, ``A proof of CSP dichotomy conjecture'', \nbp{331--342}. 3734241 \tpar Adam\ R.\ Klivans\ and Raghu\ Meka, ``Learning graphical models using multiplicative weights'', \nbp{343--354}. 3734242 \tpar Daniel\ M.\ Kane, Shachar\ Lovett, Shay\ Moran\ and Jiapeng\ Zhang, ``Active classification with comparison queries'', \nbp{355--366}. 3734243 \tpar Leslie\ G.\ Valiant, ``Capacity of neural networks for lifelong learning of composable tasks'', \nbp{367--378}. 3734244 \tpar Samuel\ B.\ Hopkins\ and David\ Steurer, ``Efficient Bayesian estimation from few samples: community detection and related problems'', \nbp{379--390}. 3734245 \tpar Daniel\ Kane, Sushrut\ Karmalkar\ and Eric\ Price, ``Robust polynomial regression up to the information theoretic limit'', \nbp{391--402}. 3734246 \tpar Joran\ van Apeldoorn, András\ Gilyén, Sander\ Gribling\ and Ronald\ de Wolf, ``Quantum SDP-solvers: better upper and lower bounds'', \nbp{403--414}. 3734247 \tpar Fernando\ G. S. L. Brandao\ and Krysta\ M.\ Svore, ``Quantum speed-ups for solving semidefinite programs'', \nbp{415--426}. 3734248 \tpar Lior\ Eldar\ and Aram\ W.\ Harrow, ``Local Hamiltonians whose ground states are hard to approximate'', \nbp{427--438}. 3734249 \tpar András\ Gilyén\ and Or\ Sattath, ``On preparing ground states of gapped Hamiltonians: an efficient quantum Lovász local lemma'', \nbp{439--450}. 3734250 \tpar Kun\ He, Liang\ Li, Xingwu\ Liu, Yuyi\ Wang\ and Mingji\ Xia, ``Variable-version Lovász local lemma: beyond Shearer's bound'', \nbp{451--462}. 3734251 \tpar Yinan\ Li\ and Youming\ Qiao, ``Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model (extended abstract)'', \nbp{463--474}. 3734252 \tpar Michael\ Kapralov, Jelani\ Nelson, Jakub\ Pachocki, Zhengyu\ Wang, David\ P.\ Woodruff\ and Mobin\ Yahyazadeh, ``Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams'', \nbp{475--486}. 3734253 \tpar Zeyuan\ Allen-Zhu\ and Yuanzhi\ Li, ``First efficient convergence for streaming $k$-PCA: a global, gap-free, and near-optimal rate'', \nbp{487--492}. 3734254 \tpar Nikhil\ Bansal, Marek\ Eliáš\ and Grigorios\ Koumoutsos, ``Weighted $k$-server bounds via combinatorial dichotomies'', \nbp{493--504}. 3734255 \tpar Krati\ Nayyar\ and Sharath\ Raghvendra, ``An input sensitive online algorithm for the metric bipartite matching problem'', \nbp{505--515}. 3734256 \tpar Yang\ Cai\ and Constantinos\ Daskalakis, ``Learning multi-item auctions with (or without) samples'', \nbp{516--527}. 3734257 \tpar Miroslav\ 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 \tpar Paul\ Dütting, Michal\ Feldman, Thomas\ Kesselheim\ and Brendan\ Lucier, ``Prophet inequalities made easy: stochastic optimization by pricing non-stochastic inputs'', \nbp{540--551}. 3734259 \tpar Thomas\ Steinke\ and Jonathan\ Ullman, ``Tight lower bounds for differentially private selection'', \nbp{552--563}. 3734260 \tpar Dakshita\ Khurana\ and Amit\ Sahai, ``How to achieve non-malleability in one or two rounds'', \nbp{564--575}. 3734261 \tpar Huijia\ Lin, Rafael\ Pass\ and Pratik\ Soni, ``Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles'', \nbp{576--587}. 3734262 \tpar Sanjam\ Garg\ and Akshayaram\ Srinivasan, ``Garbled protocols and two-round MPC from bilinear maps'', \nbp{588--599}. 3734263 \tpar Daniel\ Wichs\ and Giorgos\ Zirdelis, ``Obfuscating compute-and-compare programs under LWE'', \nbp{600--611}. 3734264 \tpar Rishab\ Goyal, Venkata\ Koppula\ and Brent\ Waters, ``Lockable obfuscation'', \nbp{612--621}. 3734265 \tpar Ilan\ Komargodski, Moni\ Naor\ and Eylon\ Yogev, ``White-box vs. black-box complexity of search problems: Ramsey and graph property testing'', \nbp{622--632}. 3734266 \tpar Kasper\ Green\ Larsen\ and Jelani\ Nelson, ``Optimality of the Johnson-Lindenstrauss lemma'', \nbp{633--638}. 3734267 \tpar Noga\ Alon\ and Bo'az\ Klartag, ``Optimal compression of approximate inner products and dimension reduction'', \nbp{639--650}. 3734268 \tpar Michael\ Kapralov, ``Sample efficient estimation and recovery in sparse FFT via isolation on average'', \nbp{651--662}. 3734269 \tpar Søren\ Dahlgaard, Mathias\ Bæk Tejs Knudsen\ and Mikkel\ Thorup, ``Fast similarity sketching'', \nbp{663--671}. 3734270 \tpar Cameron\ Musco\ and David\ P.\ Woodruff, ``Sublinear time low-rank approximation of positive semidefinite matrices'', \nbp{672--683}. 3734271 \tpar Rasmus\ Kyng\ and Peng\ Zhang, ``Hardness results for structured linear systems'', \nbp{684--695}. 3734272 \tpar Ola\ Svensson\ and Jakub\ Tarnawski, ``The matching problem in general graphs is in quasi-NC'', \nbp{696--707}. 3734273 \tpar Adam\ Bouland, Lijie\ Chen, Dhiraj\ Holden, Justin\ Thaler\ and Prashant\ Nalini\ Vasudevan, ``On the power of statistical zero knowledge'', \nbp{708--719}. 3734274 \tpar Samuel\ B.\ Hopkins, Pravesh\ K.\ Kothari, Aaron\ Potechin, Prasad\ Raghavendra, Tselil\ Schramm\ and David\ Steurer, ``The power of sum-of-squares for detecting hidden structures'', \nbp{720--731}. 3734275 \tpar Ran\ Raz, ``A time-space lower bound for a large class of learning problems'', \nbp{732--742}. 3734276 \tpar Parinya\ Chalermsook, Marek\ Cygan, Guy\ Kortsarz, Bundit\ Laekhanukit, Pasin\ Manurangsi, Danupon\ Nanongkai\ and Luca\ Trevisan, ``From gap-ETH to FPT-inapproximability: clique, dominating set, and more'', \nbp{743--754}. 3734277 \tpar David\ R.\ Karger, ``Faster (and still pretty simple) unbiased estimators for network (un)reliability'', \nbp{755--766}. 3734278 \tpar Glencora\ Borradaile, Hung\ Le\ and Christian\ Wulff-Nilsen, ``Minor-free graphs have light spanners'', \nbp{767--778}. 3734279 \tpar Ken-ichi\ Kawarabayashi\ and Anastasios\ Sidiropoulos, ``Polylogarithmic approximation for minimum planarization (almost)'', \nbp{779--788}. 3734280 \tpar Chandra\ Chekuri\ and Kent\ Quanrud, ``Approximating the Held-Karp bound for metric TSP in nearly-linear time'', \nbp{789--800}. 3734281 \tpar Jack\ Murtagh, Omer\ Reingold, Aaron\ Sidford\ and Salil\ Vadhan, ``Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space'', \nbp{801--812}. 3734282 \tpar Rocco\ A.\ Servedio\ and Li-Yang\ Tan, ``Deterministic search for CNF satisfying assignments in almost polynomial time'', \nbp{813--823}. 3734283 \tpar Rocco\ A.\ Servedio\ and Li-Yang\ Tan, ``Fooling intersections of low-weight halfspaces'', \nbp{824--835}. 3734284 \tpar Benny\ Applebaum, ``Exponentially-hard gap-CSP and local PRG via local hardcore functions'', \nbp{836--847}. 3734285 \tpar Noga\ Alon, Omri\ Ben-Eliezer\ and Eldar\ Fischer, ``Testing hereditary properties of ordered graphs and matrices'', \nbp{848--858}. 3734286 \tpar Felix\ Joos, Jaehoon\ Kim, Daniela\ Kühn\ and Deryk\ Osthus, ``A characterization of testable hypergraph properties (extended abstract)'', \nbp{859--867}. 3734287 \tpar Xi\ Chen, Erik\ Waingarten\ and Jinyu\ Xie, ``Boolean unateness testing with $\widetilde O(n^{3/4})$ adaptive queries'', \nbp{868--879}. 3734288 \tpar Tuğkan\ Batu\ and Clément\ L.\ Canonne, ``Generalized uniformity testing'', \nbp{880--889}. 3734289 \tpar Zeyuan\ Allen-Zhu, Yuanzhi\ Li, Rafael\ Oliveira\ and Avi\ Wigderson, ``Much faster algorithms for matrix scaling'', \nbp{890--901}. 3734290 \tpar Michael\ B.\ Cohen, Aleksander\ Mądry, Dimitris\ Tsipras\ and Adrian\ Vladu, ``Matrix scaling and balancing via box constrained Newton's method and interior point methods'', \nbp{902--913}. 3734291 \tpar Nima\ Anari, Leonid\ Gurvits, Shayan\ Oveis\ Gharan\ and Amin\ Saberi, ``Simply exponential approximation of the permanent of positive semidefinite matrices'', \nbp{914--925}. 3734292 \tpar David\ Durfee, John\ Peebles, Richard\ Peng\ and Anup\ B.\ Rao, ``Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees'', \nbp{926--937}. 3734293 \tpar Thomas\ D.\ Ahle, ``Optimal Las Vegas locality sensitive data structures'', \nbp{938--949}. 3734294 \tpar Danupon\ Nanongkai, Thatchaphol\ Saranurak\ and Christian\ Wulff-Nilsen, ``Dynamic minimum spanning forest with subpolynomial worst-case update time'', \nbp{950--961}. 3734295 \tpar Vincent\ Cohen-Addad, Søren\ Dahlgaard\ and Christian\ Wulff-Nilsen, ``Fast and compact exact distance oracle for planar graphs'', \nbp{962--973}. 3734296 \tpar Irit\ Dinur\ and Tali\ Kaufman, ``High dimensional expanders imply agreement expanders'', \nbp{974--985}. 3734297 \tpar Jingcheng\ Liu, Alistair\ Sinclair\ and Piyush\ Srivastava, ``The Ising partition function: zeros and deterministic approximation'', \nbp{986--997}. 3734298 \tpar Yin\ Tat\ Lee\ and Santosh\ S.\ Vempala, ``Eldan's stochastic localization and the KLS hyperplane conjecture: an improved lower bound for expansion'', \nbp{998--1007}. 3734299 \tpar Vijay\ Bhattiprolu, Venkatesan\ Guruswami, Euiwoong\ Lee, Mrinalkanti\ Ghosh\ and Madhur\ Tulsiani, ``Weak decoupling, polynomial folds, and approximate optimization over the sphere'', \nbp{1008--1019}. 3734300 \tpar Javad\ B.\ Ebrahimi, Damian\ Straszak\ and Nisheeth\ K.\ Vishnoi, ``Subdeterminant maximization via nonconvex relaxations and anti-concentration (extended abstract)'', \nbp{1020--1031}. 3734301 \tpar Moses\ Charikar\ and Paris\ Siminelakis, ``Hashing-based-estimators for kernel density in high dimensions'', \nbp{1032--1043}. 3734302 \tpar