default search action
9th ITCS 2018: Cambridge, MA, USA
- Anna R. Karlin:
9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA. LIPIcs 94, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-060-6 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xii
- Klim Efremenko
, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson:
Barriers for Rank Methods in Arithmetic Complexity. 1:1-1:19 - Jin-Yi Cai, Zhiguo Fu, Kurt Girstmair, Michael Kowalczyk:
A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory. 2:1-2:22 - Srinivasan Arunachalam, Jop Briët, Carlos Palazuelos
Quantum Query Algorithms are Completely Bounded Forms. 3:1-3:21 - Bill Fefferman, Cedric Yen-Yu Lin:
A Complete Characterization of Unitary Quantum Space. 4:1-4:21 - Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang:
Matrix Completion and Related Problems via Strong Duality. 5:1-5:22 - Michael Ben-Or
A Quasi-Random Approach to Matrix Spectral Analysis. 6:1-6:22 - Aditya Bhaskara, Silvio Lattanzi:
Non-Negative Sparse Regression and Column Subset Selection with L1 Error. 7:1-7:15 - Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff:
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. 8:1-8:21 - Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde:
Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs. 9:1-9:18 - Paul Beame
Stabbing Planes. 10:1-10:20 - Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz
A Candidate for a Strong Separation of Information and Communication. 11:1-11:13 - Mark Braverman, Young Kun-Ko:
Information Value of Two-Prover Games. 12:1-12:15 - Yuqing Kong, Grant Schoenebeck
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. 13:1-13:20 - Yuqing Kong, Grant Schoenebeck
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case. 14:1-14:20 - Rafael M. Frongillo, Bo Waggoner:
An Axiomatic Study of Scoring Rule Markets. 15:1-15:20 - Avrim Blum, Yishay Mansour:
On Price versus Quality. 16:1-16:12 - Shafi Goldwasser, Ofer Grossman, Dhiraj Holden:
Pseudo-Deterministic Proofs. 17:1-17:18 - Oded Goldreich, Guy N. Rothblum:
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. 18:1-18:19 - Itay Berman, Ron D. Rothblum, Vinod Vaikuntanathan:
Zero-Knowledge Proofs of Proximity. 19:1-19:20 - Eric Allender
Minimum Circuit Size, Graph Isomorphism, and Related Problems. 20:1-20:20 - Elette Boyle, Niv Gilboa
Foundations of Homomorphic Secret Sharing. 21:1-21:21 - Rina Panigrahy, Ali Rahimi, Sushant Sachdeva
Convergence Results for Neural Networks via Electrodynamics. 22:1-22:19 - Jelena Diakonikolas, Lorenzo Orecchia
Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method. 23:1-23:19 - Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter
Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. 24:1-24:20 - Josh Alman, Virginia Vassilevska Williams:
Further Limitations of the Known Approaches for Matrix Multiplication. 25:1-25:15 - Srikanth Srinivasan
Local Decoding and Testing of Polynomials over Grids. 26:1-26:14 - Tom Gur, Govind Ramnarayan, Ron D. Rothblum:
Relaxed Locally Correctable Codes. 27:1-27:11 - Dana Moshkovitz, Michal Moshkovitz:
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. 28:1-28:20 - Pooya Hatami, Avishay Tal:
Pseudorandom Generators for Low Sensitivity Functions. 29:1-29:13 - Christoph Dürr, Thomas Erlebach, Nicole Megow
Scheduling with Explorable Uncertainty. 30:1-30:14 - Martin Groß, Anupam Gupta, Amit Kumar
A Local-Search Algorithm for Steiner Forest. 31:1-31:17 - Daniel Lokshtanov, Pranabendu Misra
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. 32:1-32:13 - Jon M. Kleinberg, Manish Raghavan:
Selection Problems in the Presence of Implicit Bias. 33:1-33:17 - Erik D. Demaine, Andrea Lincoln
Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. 34:1-34:23 - Amir Abboud, Aviad Rubinstein:
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. 35:1-35:14 - Irit Dinur, Pasin Manurangsi:
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. 36:1-36:20 - Paul W. Goldberg
Towards a Unified Complexity Theory of Total Functions. 37:1-37:20 - Paul Beame
Edge Estimation with Independent Set Oracles. 38:1-38:21 - Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
Computing Exact Minimum Cuts Without Knowing the Graph. 39:1-39:16 - Nir Ailon, Anup Bhattacharya, Ragesh Jaiswal
Approximate Clustering with Same-Cluster Queries. 40:1-40:21 - Vedat Levi Alev
Graph Clustering using Effective Resistance. 41:1-41:16 - Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota
Lattice-based Locality Sensitive Hashing is Optimal. 42:1-42:18 - Victor Balcer, Salil P. Vadhan:
Differential Privacy on Finite Computers. 43:1-43:21 - Vishesh Karwa, Salil P. Vadhan:
Finite Sample Differentially Private Confidence Intervals. 44:1-44:9 - Jacob Steinhardt, Moses Charikar
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. 45:1-45:21 - Qingqing Huang, Sham M. Kakade, Weihao Kong, Gregory Valiant:
Recovering Structured Probability Matrices. 46:1-46:14 - Mingda Qiao, Gregory Valiant:
Learning Discrete Distributions from Untrusted Batches. 47:1-47:20 - Yishay Mansour, Aleksandrs Slivkins, Zhiwei Steven Wu
Competing Bandits: Learning Under Competition. 48:1-48:27 - Lucas Boczkowski, Ofer Feinerman, Amos Korman, Emanuele Natale
Limits for Rumor Spreading in Stochastic Populations. 49:1-49:21 - Keren Censor-Hillel, Ran Gelles, Bernhard Haeupler:
Making Asynchronous Distributed Computations Robust to Channel Noise. 50:1-50:20 - Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, Frieder Smolny:
Distance-Preserving Graph Contractions. 51:1-51:14 - Shay Solomon:
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. 52:1-52:19 - Alessandro Chiesa, Tom Gur:
Proofs of Proximity for Distribution Testing. 53:1-53:14 - Lior Gishboliner, Asaf Shapira:
Efficient Testing without Efficient Regularity. 54:1-54:14 - Pravesh K. Kothari, Roi Livni:
Improper Learning by Refuting. 55:1-55:10 - Greg Yang:
A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma. 56:1-56:16 - Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala:
Long Term Memory and the Densest K-Subgraph Problem. 57:1-57:15 - Bernard Chazelle:
Toward a Theory of Markov Influence Systems and their Renormalization. 58:1-58:18 - Georgios Piliouras, Leonard J. Schulman
Learning Dynamics and the Co-Evolution of Competing Sexual Species. 59:1-59:3
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-10-31 20:02 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: