Show indexed articles as search result.

Contents: Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, MadhuSudan and Salil Vadhan, Robust PCPs of proximity, shorter PCPs and applications to coding 1–10; Jonas Holmerin and Subhash Khot, A new PCP outer verifier with applications to homogeneous linear equations and max-bisection 11–20; Julia Chuzhoy, SudiptoGuha, Eran Halperin, Sanjeev Khanna, Guy Kortsarzand Joseph Naor, Asymmetric \(k\)-center is log\(^*\) \(n\)-hard to approximate 21–27; Julia Chuzhoy and Joseph Naor, New hardness results for congestion minimization and machine scheduling 28–34; Susanne Albers and MarkusSchmidt, On the performance of greedy algorithms in packet buffering 35–44; Baruch Awerbuch and Robert D. Kleinberg, Adaptive routing with end-to-end feedback: distributed learning and geometric approaches 45–53; Gurmeet Singh Manku, Moni Naor and UdiWieder, Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks 54–63; Yossi Azar and Yossi Richter, The zero-one principle for switching networks 64–71; Noga Alon and Assaf Naor, Approximating the cut-norm via Grothendieck’s inequality 72–80; Daniel A. Spielman and Shang-Hua Teng, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems 81–90; Richard Cole, Lee-Ad Gottlieb and MosheLewenstein, Dictionary matching and indexing with errors and don’t cares 91–100.
IreneFinocchi and Giuseppe F. Italiano, Sorting and searching in the presence of memory faults (without redundancy) 101–110; Andris Ambainis, Quantum algorithms a decade after Shor 111; Andrew Chi-Chih Yao, Graph entropy and quantum sorting problems 112–117; Scott Aaronson, Multilinear formulas and skepticism of quantum computing 118–127; Ziv Bar-Yossef, T. S.Jayram and Iordanis Kerenidis, Exponential separation of quantum and classical one-way communication complexity 128–137; G. Kortsarz and Z. Nutov, Approximation algorithm for \(k\)-node connected subgraphs via critical graphs 138–145; D. Bienstock and G. Iyengar, Solving fractional packing problems in \(O^{*}(1/\varepsilon)\) iterations 146–155; Chandra Chekuri, Sanjeev Khanna and F. BruceShepherd, The all-or-nothing multicommodity flow problem 156–165; Nikhil Bansal, Avrim Blum, Shuchi Chawla and Adam Meyerson, Approximation algorithms for deadline-TSP and vehicle routing with time-windows 166–174.
Artur Czumaj and ChristianSohler, Estimating the weight of metric minimum spanning trees in sublinear-time 175–183; Liam Roditty and Uri Zwick, A fully dynamic reachability algorithm for directed graphs with an almost linear update time 184–191; Alexander Healy, SalilVadhan and Emanuele Viola, Using nondeterminism to amplify hardness 192–201.
Rajeev Alur and P. Madhusudan, Visibly pushdown languages 202–211; Jianer Chen, Xiuzhen Huang, Iyad A.Kanj and Ge Xia, Linear FPT reductions and computational lower bounds 212–221; SanjeevArora, Satish Rao and Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning 222–231; Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority 232–241; Manoj Prabhakaran and Amit Sahai, New notions of security: achieving universal composability without trusted setup 242–251; Danny Harnik, Moni Naor, Omer Reingold and Alon Rosen, Completeness in two-party secure computation: a computational view 252–261; Yuval Ishai, Eyal Kushilevitz, RafailOstrovsky and Amit Sahai, Batch codes and their applications 262–271; Claire Kenyon, Yuval Rabani and Alistair Sinclair, Low distortion maps between point sets 272–280; KunalTalwar, Bypassing the embedding: algorithms for low dimensional metrics 281–290; SarielHar-Peled and Soham Mazumdar, On coresets for \(k\)-means and \(k\)-median clustering 291–300.
Jean-Daniel Boissonnat, David Cohen-Steiner and Gert Vegter, Isotopic implicit surface meshing 301–309; László Lovász and Santosh Vempala, Hit-and-run from a corner 310–314; John Dunagan and Santosh Vempala, A simple polynomial-time rescaling algorithm for solving linear programs 315–320; Bogdan S.Chlebus, Dariusz R. Kowalski and Alexander A. Shvartsman, Collective asynchronous reading with polylogarithmic worst-case overhead 321–330; MichaelElkin, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem 331–340; Éva Tardos, Network games 341–342; Rene Beier and Berthold Vöcking, Typical properties of winners and losers in discrete optimization 343–352; Retsef Levi, Robin Roundy and David B. Shmoys, Primal-dual algorithms for deterministic inventory problems 353–362; Chandra Chekuri, Ashish Goel, Sanjeev Khanna and Amit Kumar, Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation 363–372; Piotr Indyk, Algorithms for dynamic geometric problems over data streams 373–380; Tugkan Batu, Ravi Kumar [{}S. Ravi Kumar]{} and Ronitt Rubinfeld, Sublinear algorithms for testing monotone and unimodal distributions 381–390; Eldar Fischer, The difficulty of testing for isomorphism against a graph that is given in advance 391–397; José R. Correa and Michel X. Goemans, An approximate König’s theorem for edge-coloring weighted bipartite graphs 398–406.
Harold N. Gabow, Finding paths and cycles of superpolylogarithmic length 407–416; Anupam Gupta, Martin Pál, R. Ravi and Amitabh Sinha, Boosted sampling: approximation algorithms for stochastic optimization 417–426; Amir Shpilka and Avi Wigderson, Derandomizing homomorphism testing in general groups 427–435; Venkatesan Guruswami, Better extractors for better codes? 436–444; Eyal Rozenman, Aner Shalev and Avi Wigderson, A new family of Cayley expanders 445–454; Jonathan A. Kelner, Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus 455–464; Scott Aaronson, Lower bounds for local search by quantum arguments 465–474; Peter Burgisser and Felipe Cucker, Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets 475–485; Miklós Ajtai, A conjecture about polynomial time computable lattice-lattice functions 486–493; Miklos Santha and Mario Szegedy, Quantum and classical query complexities of local search are polynomially related 494–501.
Ben W. Reichardt, The quantum adiabatic optimization algorithm and local minima 502–510; Rahul Garg and Sanjiv Kapoor, Auction algorithms for market equilibrium 511–518; Nikhil R. Devanur, The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results 519–528; Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, RajmohanRajaraman, Ravi Sundaram and Adrian Vetta, (Almost) tight bounds and existence theorems for confluent flows 529–538; Kenji Obata, Approximate max-integral-flow/min-multicut theorems 539–545; Mihai Pǎtraşcu and Erik D. Demaine, Lower bounds for dynamic connectivity 546–553; Nir Ailon and Bernard Chazelle, Lower bounds for linear degeneracy testing 554–560; David Kempe and Frank McSherry, A decentralized algorithm for spectral analysis 561–568; Jon Kleinberg and Mark Sandler, Using mixture models for collaborative filtering 569–578; Avi Wigderson, Depth through breadth, or why should we attend talks in other areas? 579; Ashish Goel, Sanatan Rai and Bhaskar Krishnamachari, Sharp thresholds for monotone properties in random geometric graphs 580–586; Dimitris Achlioptas and Assaf Naor, The two possible values of the chromatic number of a random graph 587–593; Uriel Feige, On sums of independent random variables with unbounded variance, and estimating the average degree in a graph 594–603.
Alex Fabrikant, Christos Papadimitriou and Kunal Talwar, The complexity of pure Nash equilibria 604–612; Martin Gairing, Thomas Lücking, Marios Mavronicolas and Burkhard Monien, Computing Nash equilibria for scheduling on restricted parallel links 613–622; Joseph Halpern and Vanessa Teague, Rational secret sharing and multiparty computation: extended abstract 623–632; Ran Raz, Multi-linear formulas for permanent and determinant are of super-polynomial size 633–641.
The articles of mathematical interest will be reviewed individually. The preceding conference has been reviewed (see Zbl 1074.68503).
Indexed articles:
Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil, Robust PSPs of proximity, shorter PSPs and applications to coding, 1-10, electronic only [Zbl 1192.68286]
Holmerin, Jonas; Khot, Subhash, A new PCP outer verifier with applications to homogeneous linear equations and max-bisection, 11-20, electronic only [Zbl 1192.68324]
Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Naor, Joseph, Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate, 21-27, electronic only [Zbl 1192.68314]
Chuzhoy, Julia; Naor, Joseph, New hardness results for congestion minimization and machine scheduling, 28-34, electronic only [Zbl 1192.90254]
Albers, Susanne; Schmidt, Markus, On the performance of greedy algorithms in packet buffering, 35-44, electronic only [Zbl 1192.68938]
Awerbuch, Baruch; Kleinberg, Robert D., Adaptive routing with end-to-end feedback: distributed learning and geometric approaches, 45-53, electronic only [Zbl 1192.68020]
Manku, Gurmeet Singh; Naor, Moni; Wieder, Udi, Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks, 54-63, electronic only [Zbl 1192.68048]
Azar, Yossi; Richter, Yossi, The zero-one principle for switching networks, 64-71, electronic only [Zbl 1192.68021]
Alon, Noga; Naor, Assaf, Approximating the cut-norm via Grothendieck’s inequality, 72-80, electronic only [Zbl 1192.68866]
Spielman, Daniel A.; Teng, Shang-Hua, Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems, 81-90, electronic only [Zbl 1192.65048]
Cole, Richard; Gottlieb, Lee-Ad; Lewenstein, Moshe, Dictionary matching and indexing with errors and don’t cares, 91-100, electronic only [Zbl 1192.68818]
Finocchi, Irene; Italiano, Giuseppe F., Sorting and searching in the presence of memory faults (without redundancy), 101-110, electronic only [Zbl 1192.68958]
Yao, Andrew Chi-Chih, Graph entropy and quantum sorting problems, 112-117, electronic only [Zbl 1192.81109]
Aaronson, Scott, Multilinear formulas and skepticism of quantum computing, 118-127, electronic only [Zbl 1192.81045]
Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis, Exponential separation of quantum and classical one-way communication complexity, 128-137, electronic only [Zbl 1192.81052]
Kortsarz, G.; Nutov, Z., Approximation algorithm for \(k\)-node connected subgraphs via critical graphs, 138-145, electronic only [Zbl 1192.90233]
Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce, The all-or-nothing multicommodity flow problem, 156-165, electronic only [Zbl 1192.68878]
Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi; Meyerson, Adam, Approximation algorithms for deadline-TSP and vehicle routing with time-windows, 166-174, electronic only [Zbl 1192.90216]
Czumaj, Artur; Sohler, Christian, Estimating the weight of metric minimum spanning trees in sublinear-time, 175-183, electronic only [Zbl 1192.68888]
Roditty, Liam; Zwick, Uri, A fully dynamic reachability algorithm for directed graphs with an almost linear update time, 184-191, electronic only [Zbl 1192.90238]
Healy, Alexander; Vadhan, Salil; Viola, Emanuele, Using nondeterminism to amplify hardness, 192-201, electronic only [Zbl 1192.68294]
Alur, Rajeev; Madhusudan, P., Visibly pushdown languages, 202-211, electronic only [Zbl 1192.68396]
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge, Linear FPT reductions and computational lower bounds, 212-221, electronic only [Zbl 1192.68313]
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh, Expander flows, geometric embeddings and graph partitioning, 222-231, electronic only [Zbl 1192.68467]
Pass, Rafael, Bounded-concurrent secure multi-party computation with a dishonest majority, 232-241, electronic only [Zbl 1192.68077]
Prabhakaran, Manoj; Sahai, Amit, New notions of security: achieving universal composability without trusted setup, 242-251, electronic only [Zbl 1192.94124]
Harnik, Danny; Naor, Moni; Reingold, Omer; Rosen, Alon, Completeness in two-party secure computation: a computational view, 252-261, electronic only [Zbl 1192.94120]
Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit, Batch codes and their applications, 262-271, electronic only [Zbl 1192.94100]
Kenyon, Claire; Rabani, Yuval; Sinclair, Alistair, Low distortion maps between point sets, 272-280, electronic only [Zbl 1192.68366]
Talwar, Kunal, Bypassing the embedding: algorithms for low dimensional metrics, 281-290, electronic only [Zbl 1192.68918]
Har-Peled, Sariel; Mazumdar, Soham, On coresets for \(k\)-means and \(k\)-median clustering, 291-300, electronic only [Zbl 1192.68904]
Boissonnat, Jean-Daniel; Cohen-Steiner, David; Vegter, Gert, Isotopic implicit surface meshing, 301-309, electronic only [Zbl 1192.65016]
Lovász, László; Vempala, Santosh, Hit-and-run from a corner, 310-314, electronic only [Zbl 1192.68371]
Dunagan, John; Vempala, Santosh, A simple polynomial-time rescaling algorithm for solving linear programs, 315-320, electronic only [Zbl 1192.90116]
Chlebus, Bogdan S.; Kowalski, Dariusz R.; Shvartsman, Alexander A., Collective asynchronous reading with polylogarithmic worst-case overhead, 321-330, electronic only [Zbl 1192.68079]
Elkin, Michael, Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem, 331-340, electronic only [Zbl 1192.68319]
Tardos, Éva, Network games, 341-342, electronic only [Zbl 1192.91046]
Beier, Rene; Vöcking, Berthold, Typical properties of winners and losers in discrete optimization, 343-352, electronic only [Zbl 1192.90156]
Levi, Retsef; Roundy, Robin; Shmoys, David B., Primal-dual algorithms for deterministic inventory problems, 353-362, electronic only [Zbl 1192.90010]
Chekuri, Chandra; Goel, Ashish; Khanna, Sanjeev; Kumar, Amit, Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation, 363-372, electronic only [Zbl 1192.68096]
Indyk, Piotr, Algorithms for dynamic geometric problems over data streams, 373-380, electronic only [Zbl 1192.68179]
Batu, Tugkan; Kumar, Ravi; Rubinfeld, Ronitt, Sublinear algorithms for testing monotone and unimodal distributions, 381-390, electronic only [Zbl 1192.68345]
Fischer, Eldar, The difficulty of testing for isomorphism against a graph that is given in advance, 391-397, electronic only [Zbl 1192.68857]
Correa, José R.; Goemans, Michel X., An approximate König’s theorem for edge-coloring weighted bipartite graphs, 398-406, electronic only [Zbl 1192.05046]
Gabow, Harold N., Finding paths and cycles of superpolylogarithmic length, 407-416, electronic only [Zbl 1192.68361]
Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha, Amitabh, Boosted sampling: approximation algorithms for stochastic optimization, 417-426, electronic only [Zbl 1192.90171]
Shpilka, Amir; Wigderson, Avi, Derandomizing homomorphism testing in general groups, 427-435, electronic only [Zbl 1192.68378]
Guruswami, Venkatesan, Better extractors for better codes?, 436-444, electronic only [Zbl 1192.68363]
Rozenman, Eyal; Shalev, Aner; Wigderson, Avi, A new family of Cayley expanders (?), 445-454, electronic only [Zbl 1192.68862]
Kelner, Jonathan A., Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus, 455-464, electronic only [Zbl 1192.05162]
Aaronson, Scott, Lower bounds for local search by quantum arguments, 465-474, electronic only [Zbl 1192.68256]
Bürgisser, Peter; Cucker, Felipe, Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets, 475-485, electronic only [Zbl 1192.68289]
Ajtai, Miklós, A conjecture about polynomial time computable lattice-lattice functions, 486-493, electronic only [Zbl 1192.68335]
Santha, Miklos; Szegedy, Mario, Quantum and classical query complexities of local search are polynomially related, 494-501, electronic only [Zbl 1192.68266]
Reichardt, Ben W., The quantum adiabatic optimization algorithm and local minima, 502-510, electronic only [Zbl 1192.81098]
Garg, Rahul; Kapoor, Sanjiv, Auction algorithms for market equilibrium, 511-518, electronic only [Zbl 1192.91011]
Devanur, Nikhil R., The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results, 519-528, electronic only [Zbl 1192.91101]
Chen, Jiangzhuo; Kleinberg, Robert D.; Lovász, László; Rajaraman, Rajmohan; Sundaram, Ravi; Vetta, Adrian, ({A}lmost) tight bounds and existence theorems for confluent flows, 529-538, electronic only [Zbl 1192.90022]
Obata, Kenji, Approximate max-integral-flow/min-multicut theorems, 539-545, electronic only [Zbl 1192.90236]
Pǎtraşcu, Mihai; Demaine, Erik D., Lower bounds for dynamic connectivity, 546-553, electronic only [Zbl 1192.68185]
Ailon, Nir; Chazelle, Bernard, Lower bounds for linear degeneracy testing, 554-560, electronic only [Zbl 1192.68306]
Kempe, David; McSherry, Frank, A decentralized algorithm for spectral analysis, 561-568, electronic only [Zbl 1192.68848]
Kleinberg, Jon; Sandler, Mark, Using mixture models for collaborative filtering, 569-578, electronic only [Zbl 1192.68685]
Goel, Ashish; Rai, Sanatan; Krishnamachari, Bhaskar, Sharp thresholds for monotone properties in random geometric graphs, 580-586, electronic only [Zbl 1192.05145]
Achlioptas, Dimitris; Naor, Assaf, The two possible values of the chromatic number of a random graph, 587-593, electronic only [Zbl 1192.05140]
Feige, Uriel, On sums of independent random variables with unbounded variance, and estimating the average degree in a graph, 594-603, electronic only [Zbl 1192.60021]
Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal, The complexity of pure Nash equilibria, 604-612, electronic only [Zbl 1192.91042]
Gairing, Martin; Lücking, Thomas; Mavronicolas, Marios; Monien, Burkhard, Computing Nash equilibria for scheduling on restricted parallel links, 613-622, electronic only [Zbl 1192.90072]
Halpern, Joseph; Teague, Vanessa, Rational secret sharing and multiparty computation, 623-632, electronic only [Zbl 1192.94119]
Raz, Ran, Multi-linear formulas for permanent and determinant are of super-polynomial size, 633-641, electronic only [Zbl 1192.68328]
Ambainis, Andris, Quantum algorithms a decade after Shor, 111, electronic only [Zbl 1192.81049]
Wigderson, Avi, Depth through breadth, or why should we attend talks in other areas?, 579, electronic only [Zbl 1192.68254]