| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Baptiste Louf, Colin McDiarmid, Fiona Skerman |
Modularity and Graph Expansion.  |
ITCS  |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha |
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Tomer Ezra, Michal Feldman, Maya Schlesinger |
On the (In)approximability of Combinatorial Contracts. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Gregory Valiant |
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin |
Graph Threading. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Teresa Anna Steiner |
Differentially Private Approximate Pattern Matching. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhao Song 0002, Lichen Zhang 0003, Ruizhe Zhang 0001 |
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani |
Extractors for Polynomial Sources over 2. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Kevin Pratt |
On Generalized Corners and Matrix Multiplication. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Charlotte Out, Nicolás Rivera, Thomas Sauerwald, John Sylvester 0001 |
Rumors with Changing Credibility. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Rex Fernando, Yuval Gelles, Ilan Komargodski |
Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha |
Quantum Merlin-Arthur and Proofs Without Relative Phase. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Tanmay Inamdar 0002, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan 0001, Saket Saurabh 0001 |
Exponential-Time Approximation Schemes via Compression. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Harry Buhrman, William Kretschmer |
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Lisa Hellerstein, Naifeng Liu, Kevin Schewior |
Quickly Determining Who Won an Election. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason D. Hartline, Aleck C. Johnsen |
Equivocal Blends: Prior Independent Lower Bounds. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen |
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, Manolis Zampetakis |
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, Kasturi R. Varadarajan |
Geometric Covering via Extraction Theorem. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang |
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Weihao Kong, Mingda Qiao, Rajat Sen |
A Combinatorial Approach to Robust PCA. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishay Haviv |
The Chromatic Number of Kneser Hypergraphs via Consensus Division. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty |
Smooth Nash Equilibria: Algorithms and Complexity. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman |
An Improved Protocol for ExactlyN with More Than 3 Players. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Milionis, Ciamac C. Moallemi, Tim Roughgarden |
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam |
Discreteness of Asymptotic Tensor Ranks (Extended Abstract). |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann |
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Atanas Dinev, S. Matthew Weinberg |
Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Euiwoong Lee, Pasin Manurangsi |
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Louis Golowich, Tali Kaufman |
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Monika Henzinger, Barna Saha, Martin P. Seybold, Christopher Ye |
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Nico Döttling, Tamer Mour |
On the Black-Box Complexity of Correlation Intractability. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Noam Mazor, Rafael Pass |
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi-Jun Chang |
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Siddharth Barman, Anand Krishna, Pooja Kulkarni, Shivika Narang |
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Barak Nehoran, Mark Zhandry |
A Computational Separation Between Quantum No-Cloning and No-Telegraphing. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Hadley Black, Eric Blais, Nathaniel Harms |
Testing and Learning Convex Sets in the Ternary Hypercube. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Mayank Goswami 0001, Riko Jacob |
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Lukás Folwarczný, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan 0002 |
One-Way Functions vs. TFNP: Simpler and Improved. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | C. Ramya, Pratik Shastri |
Lower Bounds for Planar Arithmetic Circuits. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Huacheng Yu, Wei Zhan |
Sampling, Flowers and Communication. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Peter Robinson 0002 |
The Message Complexity of Distributed Graph Optimization. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Asaf Petruschka, Shay Sapir, Elad Tzalik |
Color Fault-Tolerant Spanners. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Prantar Ghosh, Vihan Shah |
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran |
Loss Minimization Yields Multicalibration for Large Neural Networks. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Nika Haghtalab, Nicole Immorlica, Brendan Lucier, Markus Mobius, Divyarthi Mohan |
Communicating with Anecdotes (Extended Abstract). |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Joseph Slote |
Parity vs. AC0 with Simple Quantum Preprocessing. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke |
Classical Verification of Quantum Learning. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Abhranil Chatterjee 0001, Mrinal Kumar 0001, Ben Lee Volk |
Determinants vs. Algebraic Branching Programs. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ari Karchmer |
Distributional PAC-Learning from Nisan's Natural Proofs. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ragesh Jaiswal, Amit Kumar 0001, Jatin Yadav |
FPT Approximation for Capacitated Sum of Radii. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov |
Homogeneous Algebraic Complexity Theory and Algebraic Formulas. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Zhandry |
Quantum Money from Abelian Group Actions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Iddo Tzameret, Luming Zhang |
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ce Jin 0001, R. Ryan Williams, Nathaniel Young |
A VLSI Circuit Model Accounting for Wire Delay. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Zhandry |
The Space-Time Cost of Purifying Quantum Computations. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bene Watts, John Bostanci |
Quantum Event Learning and Gentle Random Measurements. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Clément L. Canonne, Yucheng Sun |
Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Kaartik Bhushan, Venkata Koppula, Manoj Prabhakaran 0001 |
Homomorphic Indistinguishability Obfuscation and Its Applications. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron (Louie) Putterman, Edward Pyne |
Pseudorandom Linear Codes Are List-Decodable to Capacity. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hubácek, Erfan Khaniki, Neil Thapen |
TFNP Intersections Through the Lens of Feasible Disjunction. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh 0001, Meirav Zehavi |
Kernelization of Counting Problems. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Xingjian Li 0006, Qipeng Liu 0001, Angelos Pelecanos, Takashi Yamakawa |
Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Huacheng Yu, Wei Zhan |
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Shir Peleg, Amir Shpilka, Ben Lee Volk |
Tensor Reconstruction Beyond Constant Rank. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Nick Fischer, Piotr Kaliciak, Adam Polak 0001 |
Deterministic 3SUM-Hardness. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen |
Pseudorandom Strings from Pseudorandom Quantum States. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Avrim Blum, Melissa Dutz |
Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksandar Nikolov, Haohua Tang |
General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabien Dufoulon, Michael Moorman, William K. Moses Jr., Gopal Pandurangan |
Time- and Communication-Efficient Overlay Network Construction via Gossip. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Haosen Ge, Hamsa Bastani, Osbert Bastani |
Rethinking Fairness for Human-AI Collaboration (Extended Abstract). |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Roi Livni |
Making Progress Based on False Discoveries. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Karam |
Small Sunflowers and the Structure of Slice Rank Decompositions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Gabriel Bathie, R. Ryan Williams |
Towards Stronger Depth Lower Bounds. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Jiawei Li |
Total NP Search Problems with Abundant Solutions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Henry L. Fleischmann |
Spanning Adjacency Oracles in Sublinear Time. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jyun-Jie Liao |
Recursive Error Reduction for Regular Branching Programs. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Chiesa, Ziyi Guan, Burcu Yildiz |
On Parallel Repetition of PCPs. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami (eds.) |
15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA |
ITCS |
2024 |
DBLP BibTeX RDF |
|
| 1 | Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals |
Proving Unsatisfiability with Hitting Formulas. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy |
Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ofer Neiman, Idan Shabat |
On the Size Overhead of Pairwise Spanners. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuhao Li 0002, William Pires, Robert Robere |
Intersection Classes in TFNP and Proof Complexity. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Minming Li, Peter Robinson 0002, Xianbin Zhu 0002 |
Dynamic Maximal Matching in Clique Networks. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ke Wu 0001, Elaine Shi, Hao Chung |
Maximizing Miner Revenue in Transaction Fee Mechanism Design. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Yumou Fei, Leslie Ann Goldberg, Pinyan Lu |
Two-State Spin Systems with Negative Interactions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Varsha Dani, Thomas P. Hayes, Seth Pettie, Jared Saia |
Fraud Detection for Random Walks. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan |
Electrical Flows for Polylogarithmic Competitive Oblivious Routing. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Renato Ferreira Pinto Jr., Nathaniel Harms |
Distribution Testing with a Confused Collector. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Maryam Aliakbarpour, Rose Silver, Thomas Steinke 0002, Jonathan R. Ullman |
Differentially Private Medians and Interior Points for Non-Pathological Data. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang |
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Anindya De, Yuhao Li 0002, Shivam Nadimpalli, Rocco A. Servedio |
Testing Intersecting and Union-Closed Families. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang |
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Keller Blackwell, Mary Wootters |
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafael M. Frongillo, Maneesha Papireddygari, Bo Waggoner |
An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Justin Y. Chen, Piotr Indyk, David P. Woodruff |
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Greg Bodwin, Nicole Wein |
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights? |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Romain Cosson, Laurent Massoulié |
Collective Tree Exploration via Potential Function Method. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff |
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license