Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

DOI10.1145/3055399zbMATH Open1366.68004DBLPconf/stoc/2017OpenAlexW2914050705WikidataQ61971575 ScholiaQ61971575MaRDI QIDQ5271715

No author found.

Publication date: 12 July 2017

Full work available at URL: https://doi.org/10.1145/3055399

Mathematics Subject Classification ID

Proceedings of conferences of miscellaneous specific interest (00B25) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Theory of computing (68Qxx)

Related Items (only showing first 100 items - show all)

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing ⋮ Addition is exponentially harder than counting for shallow monotone circuits ⋮ Strongly exponential lower bounds for monotone computation ⋮ Formula lower bounds via the quantum method ⋮ Information-theoretic thresholds from the cavity method ⋮ The menu-size complexity of revenue approximation ⋮ Communication complexity of approximate Nash equilibria ⋮ Optimal mean-based algorithms for trace reconstruction ⋮ A generalization of permanent inequalities and applications in counting and optimization ⋮ Linear matroid intersection is in quasi-NC ⋮ Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling ⋮ A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees ⋮ Twenty (simple) questions ⋮ Kolmogorov complexity version of Slepian-Wolf coding ⋮ Synchronization strings ⋮ Learning from untrusted data ⋮ Beating 1-1/e for ordered prophets ⋮ Kernel-based methods for bandit convex optimization ⋮ New hardness results for routing on disjoint paths ⋮ A simpler and faster strongly polynomial algorithm for generalized flow maximization ⋮ Finding even cycles faster via capped k-walks ⋮ Strongly refuting random CSPs below the spectral threshold ⋮ Sum of squares lower bounds for refuting any CSP ⋮ Bernoulli factories and black-box reductions in mechanism design ⋮ Simple mechanisms for subadditive buyers via duality ⋮ Stability of service under time-of-use pricing ⋮ Faster space-efficient algorithms for subset sum and k-sum ⋮ Homomorphisms are a good basis for counting small subgraphs ⋮ Lossy kernelization ⋮ Explicit, almost optimal, epsilon-balanced codes ⋮ Deciding parity games in quasipolynomial time ⋮ A weighted linear matroid parity algorithm ⋮ Exponential separation of quantum communication and classical information ⋮ Compression of quantum multi-prover interactive proofs ⋮ Hardness amplification for entangled games via anchoring ⋮ The computational complexity of ball permutations ⋮ The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation ⋮ Uniform sampling through the Lovasz local lemma ⋮ Approximate counting, the Lovasz local lemma, and inference in graphical models ⋮ Real stable polynomials and matroids: optimization and counting ⋮ Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs ⋮ Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree ⋮ Local max-cut in smoothed polynomial time ⋮ Algorithms for stable and perturbation-resilient problems ⋮ Area-convexity, l _∞ regularization, and undirected multicommodity flow ⋮ Pseudorandomness of ring-LWE for any ring and modulus ⋮ Non-interactive delegation and batch NP verification from standard computational assumptions ⋮ Average-case fine-grained hardness ⋮ Equivocating Yao ⋮ Removal lemmas with polynomial bounds ⋮ Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness ⋮ Online and dynamic algorithms for set cover ⋮ Online service with delay ⋮ The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of √log n ⋮ On independent sets, 2-to-2 games, and Grassmann graphs ⋮ Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs ⋮ How well do local algorithms solve semidefinite programs? ⋮ A polynomial restriction lemma with applications ⋮ Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace ⋮ Probabilistic rank and matrix rigidity ⋮ Succinct hitting sets and barriers to proving algebraic circuits lower bounds ⋮ Pseudodeterministic constructions in subexponential time ⋮ An SDP-based algorithm for linear-sized spectral sparsification ⋮ Low rank approximation with entrywise l ₁ -norm error ⋮ An adaptive sublinear-time block sparse fourier transform ⋮ Streaming symmetric norms via measure concentration ⋮ Sampling random spanning trees faster than matrix multiplication ⋮ Distributed exact shortest paths in sublinear time ⋮ Exponential separations in the energy complexity of leader election ⋮ On the complexity of local distributed graph problems ⋮ Efficient massively parallel methods for dynamic programming ⋮ Complexity of short Presburger arithmetic ⋮ Randomized polynomial time identity testing for noncommutative circuits ⋮ Holographic algorithm with matchgates is universal for planar #CSP over boolean domain ⋮ Efficient empirical revenue maximization in single-parameter auction environments ⋮ Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria ⋮ Approximate near neighbors for general symmetric norms ⋮ Algorithmic discrepancy beyond partial coloring ⋮ Geodesic walks in polytopes ⋮ A reverse Minkowski theorem ⋮ Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph ⋮ Efficient quantum tomography II ⋮ Quantum entanglement, sum of squares, and the log rank conjecture ⋮ Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games ⋮ A quantum linearity test for robustly verifying entanglement ⋮ The limitations of optimization from samples ⋮ Approximate modularity revisited ⋮ Trace reconstruction with exp(O(n ^1/3 )) samples ⋮ Provable learning of noisy-OR networks ⋮ Time-space hardness of learning sparse parities ⋮ DecreaseKeys are expensive for external memory priority queues ⋮ Set similarity search beyond MinHash ⋮ Decremental single-source reachability in planar digraphs ⋮ Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time ⋮ Fully-dynamic minimum spanning forest with improved worst-case update time ⋮ Improved non-malleable extractors, non-malleable codes and independent source extractors ⋮ Towards optimal two-source extractors and Ramsey graphs ⋮ Non-malleable codes and extractors for small-depth circuits, and affine functions ⋮ An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy ⋮ Finding approximate local minima faster than gradient descent

This page was built for publication: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing