×

Found 118 Documents (Results 1–100)

Light spanners for high dimensional norms via stochastic decompositions. (English) Zbl 1524.68407

Azar, Yossi (ed.) et al., 26th annual European symposium on algorithms, ESA 2018, August 20–22, 2018, Helsinki, Finland. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 112, Article 29, 15 p. (2018).
MSC:  68U05 54E35 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online submodular welfare maximization: greedy beats 1/2 in random order. (English) Zbl 1322.91031

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 889-898 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Secretary problems with non-uniform arrival order. (English) Zbl 1321.68516

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 879-888 (2015).
MSC:  68W27 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Greedy algorithms for Steiner forest. (English) Zbl 1321.68504

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 871-878 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Randomized rounding for the largest simplex problem. (English) Zbl 1321.68319

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 861-870 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Minimizing flow-time on unrelated machines. (English) Zbl 1321.68113

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 851-860 (2015).
MSC:  68M20 68W25 90C05
PDFBibTeX XMLCite
Full Text: DOI arXiv

A polynomial-time bicriteria approximation scheme for planar bisection. (English) Zbl 1321.68501

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 841-850 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Analysis of a classical matrix preconditioning algorithm. (English) Zbl 1321.65045

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 831-840 (2015).
MSC:  65F08
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Super-resolution, extremal functions and the condition number of Vandermonde matrices. (English) Zbl 1321.68421

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 821-830 (2015).
MSC:  68T45 68T05 68U10
PDFBibTeX XMLCite
Full Text: DOI arXiv

From independence to expansion and back again. (English) Zbl 1321.68219

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 813-820 (2015).
MSC:  68P05 68Q17 68R10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Time lower bounds for nonadaptive turnstile streaming algorithms. (English) Zbl 1321.68286

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 803-812 (2015).
MSC:  68Q17 68W05 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Optimal data-dependent hashing for approximate near neighbors. (English) Zbl 1321.68212

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 793-801 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximate \(k\)-flat nearest neighbor search. (English) Zbl 1321.68416

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 783-792 (2015).
MSC:  68T20 68P05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Efficiently learning Ising models on arbitrary graphs (extended abstract). (English) Zbl 1321.68397

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 771-782 (2015).
MSC:  68T05 82B20 82C20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Learning mixtures of Gaussians in high dimensions. (English) Zbl 1321.68403

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 761-770 (2015).
MSC:  68T05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Tight bounds for learning a mixture of two Gaussians (extended abstract). (English) Zbl 1321.68405

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 753-760 (2015).
MSC:  68T05 62F12
PDFBibTeX XMLCite
Full Text: DOI arXiv

Learning arbitrary statistical mixtures of discrete distributions. (English) Zbl 1321.68407

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 743-752 (2015).
MSC:  68T05 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

Solving the shortest vector problem in \(2^n\) time using discrete Gaussian sampling (extended abstract). (English) Zbl 1321.68426

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 733-742 (2015).
MSC:  68W20 11Y16 94A60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Testing cluster structure of graphs. (English) Zbl 1321.68489

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 723-732 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Hypergraph Markov operators, eigenvalues and approximation algorithms. (English) Zbl 1321.05174

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 713-722 (2015).
MSC:  05C65 05C50 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Random permutations using switching networks. (English) Zbl 1321.65007

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 703-712 (2015).
MSC:  65C10 94C10
PDFBibTeX XMLCite
Full Text: DOI

Faster canonical forms for primitive coherent configurations (extended abstract). (English) Zbl 1321.05164

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 693-702 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Computing with tangles. (English) Zbl 1321.05264

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 683-692 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Beyond the Euler characteristic: approximating the genus of general graphs (extended abstract). (English) Zbl 1321.05063

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 675-682 (2015).
MSC:  05C10 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Deterministic global minimum cut of a simple graph in near-linear time. (English) Zbl 1321.05268

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 665-674 (2015).
PDFBibTeX XMLCite
Full Text: DOI

The directed grid theorem. (English) Zbl 1321.05249

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 655-664 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Excluded grid theorem: improved and simplified. (English) Zbl 1321.05248

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 645-654 (2015).
PDFBibTeX XMLCite
Full Text: DOI

How well can graphs represent wireless interference? (English) Zbl 1321.68023

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 635-644 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Adjacency labeling schemes and induced-universal graphs. (English) Zbl 1321.05226

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 625-634 (2015).
MSC:  05C78 05C20 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Test-and-set in optimal space. (English) Zbl 1321.68105

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 615-623 (2015).
MSC:  68M15 68M10 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity. (English) Zbl 1321.68096

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 605-614 (2015).
MSC:  68M15 68M12 68M14
PDFBibTeX XMLCite
Full Text: DOI arXiv

High parallel complexity graphs and memory-hard functions. (English) Zbl 1321.68374

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 595-603 (2015).
MSC:  68R10 94A60 68Q05 68Q10 68Q17 68W10
PDFBibTeX XMLCite
Full Text: DOI

Fast matrix multiplication: limitations of the Coppersmith-Winograd method (extended abstract). (English) Zbl 1321.65063

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 585-593 (2015).
MSC:  65F30 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

2-server PIR with sub-polynomial communication. (English) Zbl 1321.68253

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 577-584 (2015).
MSC:  68P20 94B35
PDFBibTeX XMLCite
Full Text: DOI arXiv

Lower bounds on the size of semidefinite programming relaxations. (English) Zbl 1321.90099

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 567-576 (2015).
MSC:  90C22 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Exponential separation of information and communication for Boolean functions (extended abstract). (English) Zbl 1321.68311

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 557-566 (2015).
MSC:  68Q25 68P30
PDFBibTeX XMLCite
Full Text: DOI

FPTAS for #BIS with degree bounds on one side. (English) Zbl 1321.05185

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 549-556 (2015).
MSC:  05C69 68Q25 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm. (English) Zbl 1321.68434

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 539-548 (2015).
MSC:  68U05 68W20 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quantum spectrum testing. (English) Zbl 1321.68273

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 529-538 (2015).
MSC:  68Q12 68Q25 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries. (English) Zbl 1321.68300

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 519-528 (2015).
MSC:  68Q25 68Q17 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

A directed isoperimetric inequality with application to Bregman near neighbor lower bounds. (English) Zbl 1321.68210

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 509-518 (2015).
MSC:  68P05 68Q17 94A17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Toward a unified theory of sparse dimensionality reduction in Euclidean space. (English) Zbl 1321.68431

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 499-508 (2015).
MSC:  68U05 68T05 68W20
PDFBibTeX XMLCite
Full Text: DOI arXiv

Prioritized metric structures and embedding. (English) Zbl 1321.68222

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 489-498 (2015).
MSC:  68P05 05C22 68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Sketching and embedding are equivalent for norms. (English) Zbl 1321.68428

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 479-488 (2015).
MSC:  68U05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Leveled fully homomorphic signatures from standard lattices. (English) Zbl 1321.94062

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 469-477 (2015).
MSC:  94A60 94A62
PDFBibTeX XMLCite
Full Text: DOI Link

Non-malleable reductions and applications. (English) Zbl 1321.94139

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 459-468 (2015).
MSC:  94B60 94A60
PDFBibTeX XMLCite
Full Text: DOI

Garbled RAM from one-way functions. (English) Zbl 1321.94061

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 449-458 (2015).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Succinct randomized encodings and their applications. (English) Zbl 1321.94041

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 439-448 (2015).
MSC:  94A60 68W20
PDFBibTeX XMLCite
Full Text: DOI

Succinct garbling and indistinguishability obfuscation for RAM programs. (English) Zbl 1321.94050

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 429-437 (2015).
MSC:  94A60
PDFBibTeX XMLCite
Full Text: DOI

Indistinguishability obfuscation for Turing machines with unbounded memory. (English) Zbl 1321.94069

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 419-428 (2015).
MSC:  94A60 68Q05
PDFBibTeX XMLCite
Full Text: DOI

Inapproximability of Nash equilibrium. (English) Zbl 1321.68320

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 409-418 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Inapproximability of truthful mechanisms via generalizations of the VC dimension. (English) Zbl 1321.68303

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 401-408 (2015).
MSC:  68Q25 68Q17 91B26
PDFBibTeX XMLCite
Full Text: DOI arXiv

Hardness of graph pricing through generalized Max-Dicut. (English) Zbl 1321.68287

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 391-399 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the complexity of Nash equilibria in anonymous games. (English) Zbl 1322.91005

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 381-390 (2015).
MSC:  91A06 68Q25 91A10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating the Nash social welfare with indivisible items. (English) Zbl 1322.91030

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 371-380 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Carathéodory’s theorem. (English) Zbl 1322.91006

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 361-369 (2015).
MSC:  91A10 91A05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

The communication complexity of interleaved group products. (English) Zbl 1321.94063

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 351-360 (2015).
MSC:  94A60 20P05
PDFBibTeX XMLCite
Full Text: DOI

An interactive information odometer and applications. (English) Zbl 1321.68260

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 341-350 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Small value parallel repetition for general games. (English) Zbl 1322.91010

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 335-340 (2015).
MSC:  91A20 94A15
PDFBibTeX XMLCite
Full Text: DOI

Sparse quantum codes from quantum circuits. (English) Zbl 1321.81018

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 327-334 (2015).
MSC:  81P70
PDFBibTeX XMLCite
Full Text: DOI arXiv

Quantum information complexity. (English) Zbl 1321.94022

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 317-326 (2015).
MSC:  94A15 68Q12 81P45
PDFBibTeX XMLCite
Full Text: DOI arXiv

Forrelation: a problem that optimally separates quantum from classical computing. (English) Zbl 1321.68272

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 307-316 (2015).
PDFBibTeX XMLCite
Full Text: DOI

Reed-Muller codes for random erasures and errors. (English) Zbl 1321.94117

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 297-306 (2015).
MSC:  94B05 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

A characterization of the capacity of online (causal) binary channels. (English) Zbl 1321.94121

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 287-296 (2015).
MSC:  94B05 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

The list decoding radius of Reed-Muller codes over small fields. (English) Zbl 1321.94120

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 277-285 (2015).
MSC:  94B05 94B35
PDFBibTeX XMLCite
Full Text: DOI arXiv

Polynomially low error PCPs with \(\operatorname{polyloglog} n\) queries via modular composition. (English) Zbl 1321.68305

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 267-276 (2015).
MSC:  68Q25 68Q15 68Q45
PDFBibTeX XMLCite
Full Text: DOI arXiv

Rectangles are nonnegative juntas. (English) Zbl 1321.68313

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 257-266 (2015).
MSC:  68Q25 68Q15
PDFBibTeX XMLCite
Full Text: DOI Link

Almost optimal pseudorandom generators for spherical caps (extended abstract). (English) Zbl 1321.65008

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 247-256 (2015).
MSC:  65C10 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Spectral sparsification and regret minimization beyond matrix multiplicative updates. (English) Zbl 1321.68294

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 237-245 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Nearly-linear time positive LP solver with faster convergence rate. (English) Zbl 1321.90078

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 229-236 (2015).
MSC:  90C05 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Near optimal LP rounding algorithm for correlation clustering on complete and complete \(k\)-partite graphs. (English) Zbl 1321.68495

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 219-228 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

An improved version of the random-facet pivoting rule for the simplex algorithm. (English) Zbl 1321.90080

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 209-218 (2015).
MSC:  90C05 68Q25 68W20
PDFBibTeX XMLCite
Full Text: DOI

The complexity of the simplex method. (English) Zbl 1321.90079

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 201-208 (2015).
MSC:  90C05 90C40 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the Lovász theta function for independent sets in sparse graphs. (English) Zbl 1321.05176

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 193-200 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

\(\ell_p\) row sampling by Lewis weights. (English) Zbl 1321.65064

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 183-192 (2015).
MSC:  65F30 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. (English) Zbl 1321.05253

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 173-182 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Dimensionality reduction for \(k\)-means clustering and low rank approximation. (English) Zbl 1321.68398

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 163-172 (2015).
MSC:  68T05 62H25 62H30
PDFBibTeX XMLCite
Full Text: DOI arXiv

Randomized composable core-sets for distributed submodular maximization. (English) Zbl 1321.68361

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 153-162 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Dictionary learning and tensor decomposition via the sum-of-squares method. (English) Zbl 1321.68396

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 143-151 (2015).
MSC:  68T05 90C22
PDFBibTeX XMLCite
Full Text: DOI arXiv

Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions. (English) Zbl 1321.68317

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 137-142 (2015).
MSC:  68Q25 68T05
PDFBibTeX XMLCite
Full Text: DOI

Local, private, efficient protocols for succinct histograms. (English) Zbl 1321.94037

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 127-135 (2015).
MSC:  94A60 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Preserving statistical validity in adaptive data analysis (extended abstract). (English) Zbl 1321.68401

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 117-126 (2015).
MSC:  68T05 94A60
PDFBibTeX XMLCite
Full Text: DOI arXiv

Inapproximability of combinatorial problems via small LPs and SDPs. (English) Zbl 1321.90098

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 107-116 (2015).
MSC:  90C22 90C27 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Sum of squares lower bounds from pairwise independence (extended abstract). (English) Zbl 1321.68295

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 97-106 (2015).
MSC:  68Q25 68Q17
PDFBibTeX XMLCite
Full Text: DOI arXiv

Sum-of-squares lower bounds for planted clique (extended abstract). (English) Zbl 1321.05241

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 87-96 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the complexity of random satisfiability problems with planted solutions (extended abstract). (English) Zbl 1321.68280

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 77-86 (2015).
MSC:  68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Consistency thresholds for the planted bisection model. (English) Zbl 1321.05242

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 69-75 (2015).
MSC:  05C80 05C85 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Proof of the satisfiability conjecture for large \(k\). (English) Zbl 1321.68304

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 59-68 (2015).
MSC:  68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). (English) Zbl 1321.68548

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 51-58 (2015).
MSC:  68W32 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI arXiv

Matching triangles and basing hardness on an extremely popular conjecture. (English) Zbl 1321.68291

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 41-50 (2015).
MSC:  68Q25 05C21 68Q17
PDFBibTeX XMLCite
Full Text: DOI

Clustered integer 3SUM via additive combinatorics. (English) Zbl 1321.68299

Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 31-40 (2015).
MSC:  68Q25 68Q17 68R05
PDFBibTeX XMLCite
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software