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

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

Author name not available (Why is that?)

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)

Cited In (only showing first 100 items - show all)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5271715)