default search action
SIAM Journal on Computing, Volume 46
Volume 46, Number 1, 2017
- Salman Beigi, Omid Etesami, Amin Gohari
:
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. 1-36 - Ilan Komargodski, Ran Raz
Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound. 37-57 - Keren Censor-Hillel, Bernhard Haeupler, Jonathan A. Kelner, Petar Maymounkov:
Rumor Spreading with No Dependence on Conductance. 58-79 - Gonzalo Navarro, Yakov Nekrich
Time-Optimal Top-k Document Retrieval. 80-113 - Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson:
Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation. 114-131 - Venkatesan Guruswami, Prahladh Harsha
Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes. 132-159
- Julia Chuzhoy, Alexander Russell:
Special Section on the Fifty-Fifth Annual ACM Symposium on Foundations of Coomputer Science (FOCS 2014). 160 - Daniel Lokshtanov, Marcin Pilipczuk
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. 161-189 - Uriel Feige, Tomer Koren, Moshe Tennenholtz:
Chasing Ghosts: Competing with Stateful Policies. 190-223 - Thomas Rothvoss:
Constructive Discrepancy Minimization for Convex Sets. 224-234 - Subhash Khot, Rishi Saket:
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2(log n)Ømega(1) Colors. 235-271 - Hyung-Chan An, Mohit Singh, Ola Svensson:
LP-Based Algorithms for Capacitated Facility Location. 272-306 - Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. 307-335 - Mrinal Kumar, Shubhangi Saraf:
On the Power of Homogeneous Depth 4 Arithmetic Circuits. 336-387 - Mark Braverman, Klim Efremenko
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. 388-428 - Gregory Valiant, Paul Valiant:
An Automatic Inequality Prover and Instance Optimal Identity Testing. 429-455 - Michael Kapralov
Single Pass Spectral Sparsification in Dynamic Streams. 456-477
Volume 46, Number 2, 2017
- Iftach Haitner, Eliad Tsfadia:
An Almost-Optimally Fair Three-Party Coin-Flipping Protocol. 479-542 - Christos Boutsidis, David P. Woodruff:
Optimal CUR Matrix Decompositions. 543-589 - David Gamarnik, Madhu Sudan:
Performance of Sequential Local Algorithms for the Random NAE-K-SAT Problem. 590-619 - Brendan Lucier, Allan Borodin:
Equilibria of Greedy Combinatorial Auctions. 620-660 - Ho-Lin Chen, David Doty
Parallelism and Time in Hierarchical Self-Assembly. 661-709 - Richard Peng, He Sun, Luca Zanetti
Partitioning Well-Clustered Graphs: Spectral Clustering Works! 710-743 - Elad Hazan
Near-Optimal Algorithms for Online Matrix Prediction. 744-773 - Michael E. Saks, C. Seshadhri:
Estimating the Longest Increasing Sequence in Polylogarithmic Time. 774-823 - Soroush Alamdari, Patrizio Angelini
How to Morph Planar Graph Drawings. 824-852
Volume 46, Number 3, 2017
- Jin-Yi Cai, Pinyan Lu
Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP. 853-889 - Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee:
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile. 890-910 - MohammadTaghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi:
Online Node-weighted Steiner Forest and Extensions via Disk Paintings. 911-935 - Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. 936-971 - Peter Bürgisser, Matthias Christandl, Ketan D. Mulmuley, Michael Walter
Membership in Moment Polytopes is in NP and coNP. 972-991 - Rishi Gupta, Tim Roughgarden:
A PAC Approach to Application-Specific Algorithm Selection. 992-1017 - Venkatesan Guruswami, Euiwoong Lee
Nearly Optimal NP-Hardness of Unique Coverage. 1018-1028 - Matthias Poloczek, Georg Schnitger, David P. Williamson, Anke van Zuylen:
Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds. 1029-1061 - Magnús M. Halldórsson
The Power of Oblivious Wireless Power. 1062-1086 - Vladimir Kolmogorov, Andrei A. Krokhin
The Complexity of General-Valued CSPs. 1087-1110 - Gianluigi Greco, Francesco Scarcello
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems. 1111-1145 - Juan Luis Esteban
A Correction on Shiloach's Algorithm for Minimum Linear Arrangement of Trees. 1146-1151
Volume 46, Number 4, 2017
- Joshua A. Grochow, Youming Qiao
Algorithms for Group Isomorphism via Group Extensions and Cohomology. 1153-1216 - Nicole Megow
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty. 1217-1240 - Johan Thapper, Stanislav Zivný:
The Power of Sherali-Adams Relaxations for General-Valued CSPs. 1241-1279 - Glencora Borradaile, Philip N. Klein, Shay Mozes
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. 1280-1303 - Carl A. Miller, Yaoyun Shi:
Universal Security for Randomness Expansion from the Spot-Checking Protocol. 1304-1335 - Roee David, Irit Dinur
Direct Sum Testing. 1336-1369 - Zengfeng Huang
The Communication Complexity of Distributed epsilon-Approximations. 1370-1394 - Pu Gao, Nicholas C. Wormald:
Uniform Generation of Random Regular Graphs. 1395-1427 - Xiaohui Bei
Worst-Case Mechanism Design via Bayesian Analysis. 1428-1448 - Ran Gelles, Bernhard Haeupler:
Capacity of Interactive Communication over Erasure Channels and Channels with Feedback. 1449-1472 - Christoph Lenzen, Joel Rybicki
Efficient Counting with Optimal Resilience. 1473-1500
Volume 46, Number 5, 2017
- Hideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta:
The "Runs" Theorem. 1501-1514 - Kousha Etessami, Alistair Stewart, Mihalis Yannakakis:
A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes. 1515-1553 - Per Austrin, Venkatesan Guruswami, Johan Håstad:
(2+ε)-Sat Is NP-hard. 1554-1573 - Sergio Cabello
Peeling Potatoes Near-Optimally in Near-Linear Time. 1574-1602 - Talya Eden, Amit Levi
Approximately Counting Triangles in Sublinear Time. 1603-1646 - André Chailloux, Iordanis Kerenidis:
Physical Limitations of Quantum Cryptographic Primitives or Optimal Bounds for Quantum Coin Flipping and Bit Commitment. 1647-1677
Volume 46, Number 6, 2017
- Danny Z. Chen, Ziyun Huang
On Clustering Induced Voronoi Diagrams. 1679-1711 - Sariel Har-Peled
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs. 1712-1744 - Alina Ene, Sariel Har-Peled
Geometric Packing under Nonuniform Constraints. 1745-1784 - Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, Shie Mannor
Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback. 1785-1826 - Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan:
Multikey Fully Homomorphic Encryption and Applications. 1827-1892 - Viresh Patel, Guus Regts:
Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials. 1893-1919 - Andrew M. Childs
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision. 1920-1950
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-14 20:49 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: