Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract) (English)
Free access
- New search for: Briët, Jop
- Further information on Briët, Jop:
- https://orcid.org/0000-0002-9909-3635
- New search for: Buhrman, Harry
- New search for: Castro-Silva, Davi
- Further information on Castro-Silva, Davi:
- https://orcid.org/0000-0002-7101-5758
- New search for: Neumann, Niels M. P.
- Further information on Neumann, Niels M. P.:
- https://orcid.org/0000-0003-2159-8251
- New search for: Briët, Jop
- Further information on Briët, Jop:
- https://orcid.org/0000-0002-9909-3635
- New search for: Buhrman, Harry
- New search for: Castro-Silva, Davi
- Further information on Castro-Silva, Davi:
- https://orcid.org/0000-0002-7101-5758
- New search for: Neumann, Niels M. P.
- Further information on Neumann, Niels M. P.:
- https://orcid.org/0000-0003-2159-8251
- New search for: Guruswami, Venkatesan
- Further information on Guruswami, Venkatesan:
- https://orcid.org/0000-0001-7926-3396
In:
LIPIcs, Volume 287, ITCS 2024
: 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
;
287
;
21:1-21:11
;
2024
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)
-
Contributors:Briët, Jop ( author ) / Buhrman, Harry ( author ) / Castro-Silva, Davi ( author ) / Neumann, Niels M. P. ( author ) / Guruswami, Venkatesan ( editor )
-
Published in:LIPIcs, Volume 287, ITCS 2024 : 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) ; 287 ; 21:1-21:11Leibniz International Proceedings in Informatics (LIPIcs) ; 287 ; 21:1-21:11
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2024-01-24
-
Size:11 pages , 735250 byte
-
Remarks:LIPIcs, Vol. 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pages 21:1-21:11
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
A Qubit, a Coin, and an Advice String Walk into a Relational ProblemAaronson, Scott / Buhrman, Harry / Kretschmer, William et al. | 2024
- 2
-
Quantum PseudoentanglementAaronson, Scott / Bouland, Adam / Fefferman, Bill / Ghosh, Soumik / Vazirani, Umesh / Zhang, Chenyi / Zhou, Zixin et al. | 2024
- 3
-
Differentially Private Medians and Interior Points for Non-Pathological DataAliakbarpour, Maryam / Silver, Rose / Steinke, Thomas / Ullman, Jonathan et al. | 2024
- 4
-
Tensor Ranks and the Fine-Grained Complexity of Dynamic ProgrammingAlman, Josh / Turok, Ethan / Yu, Hantao / Zhang, Hengzhi et al. | 2024
- 5
-
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in GamesAnagnostides, Ioannis / Kalavasis, Alkis / Sandholm, Tuomas / Zampetakis, Manolis et al. | 2024
- 6
-
Pseudorandom Strings from Pseudorandom Quantum StatesAnanth, Prabhanjan / Lin, Yao-Ting / Yuen, Henry et al. | 2024
- 7
-
Geometric Covering via Extraction TheoremBandyapadhyay, Sayan / Maheshwari, Anil / Roy, Sasanka / Smid, Michiel / Varadarajan, Kasturi et al. | 2024
- 8
-
Sublinear Approximation Algorithm for Nash Social Welfare with XOS ValuationsBarman, Siddharth / Krishna, Anand / Kulkarni, Pooja / Narang, Shivika et al. | 2024
- 9
-
Quantum Merlin-Arthur and Proofs Without Relative PhaseBassirian, Roozbeh / Fefferman, Bill / Marwaha, Kunal et al. | 2024
- 10
-
Towards Stronger Depth Lower BoundsBathie, Gabriel / Williams, R. Ryan et al. | 2024
- 11
-
Property Testing with Online AdversariesBen-Eliezer, Omri / Kelman, Esty / Meir, Uri / Raskhodnikova, Sofya et al. | 2024
- 12
-
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights?Bernstein, Aaron / Bodwin, Greg / Wein, Nicole et al. | 2024
- 13
-
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear AlgebraBhattacharjee, Rajarshi / Dexter, Gregory / Musco, Cameron / Ray, Archan / Sachdeva, Sushant / Woodruff, David P. et al. | 2024
- 14
-
Homomorphic Indistinguishability Obfuscation and Its ApplicationsBhushan, Kaartik / Koppula, Venkata / Prabhakaran, Manoj et al. | 2024
- 15
-
Testing and Learning Convex Sets in the Ternary HypercubeBlack, Hadley / Blais, Eric / Harms, Nathaniel et al. | 2024
- 16
-
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and ApplicationsBlackwell, Keller / Wootters, Mary et al. | 2024
- 17
-
Loss Minimization Yields Multicalibration for Large Neural NetworksBłasiok, Jarosław / Gopalan, Parikshit / Hu, Lunjia / Kalai, Adam Tauman / Nakkiran, Preetum et al. | 2024
- 18
-
Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every RoundBlum, Avrim / Dutz, Melissa et al. | 2024
- 19
-
Spanning Adjacency Oracles in Sublinear TimeBodwin, Greg / Fleischmann, Henry et al. | 2024
- 20
-
Discreteness of Asymptotic Tensor Ranks (Extended Abstract)Briët, Jop / Christandl, Matthias / Leigh, Itai / Shpilka, Amir / Zuiddam, Jeroen et al. | 2024
- 21
-
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)Briët, Jop / Buhrman, Harry / Castro-Silva, Davi / Neumann, Niels M. P. et al. | 2024
- 22
-
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower BoundsBringmann, Karl / Grønlund, Allan / Künnemann, Marvin / Larsen, Kasper Green et al. | 2024
- 23
-
Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be MineCanonne, Clément L. / Sun, Yucheng et al. | 2024
- 24
-
Classical Verification of Quantum LearningCaro, Matthias C. / Hinsche, Marcel / Ioannou, Marios / Nietner, Alexander / Sweke, Ryan et al. | 2024
- 25
-
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised LearningChandra, Pritam / Garg, Ankit / Kayal, Neeraj / Mittal, Kunal / Sinha, Tanmay et al. | 2024
- 26
-
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and TreesChang, Yi-Jun et al. | 2024
- 27
-
Determinants vs. Algebraic Branching ProgramsChatterjee, Abhranil / Kumar, Mrinal / Volk, Ben Lee et al. | 2024
- 28
-
Extractors for Polynomial Sources over 𝔽₂Chattopadhyay, Eshan / Goodman, Jesse / Gurumukhani, Mohit et al. | 2024
- 29
-
Recursive Error Reduction for Regular Branching ProgramsChattopadhyay, Eshan / Liao, Jyun-Jie et al. | 2024
- 30
-
Influence Maximization in Ising ModelsChen, Zongchen / Mossel, Elchanan et al. | 2024
- 31
-
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical GroupsChen, Zhili / Grochow, Joshua A. / Qiao, Youming / Tang, Gang / Zhang, Chuanqi et al. | 2024
- 32
-
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric FunctionsChen, Justin Y. / Indyk, Piotr / Woodruff, David P. et al. | 2024
- 33
-
Testing Intersecting and Union-Closed FamiliesChen, Xi / De, Anindya / Li, Yuhao / Nadimpalli, Shivam / Servedio, Rocco A. et al. | 2024
- 34
-
On Parallel Repetition of PCPsChiesa, Alessandro / Guan, Ziyi / Yıldız, Burcu et al. | 2024
- 35
-
Collective Tree Exploration via Potential Function MethodCosson, Romain / Massoulié, Laurent et al. | 2024
- 36
-
Fraud Detection for Random WalksDani, Varsha / Hayes, Thomas P. / Pettie, Seth / Saia, Jared et al. | 2024
- 37
-
Smooth Nash Equilibria: Algorithms and ComplexityDaskalakis, Constantinos / Golowich, Noah / Haghtalab, Nika / Shetty, Abhishek et al. | 2024
- 38
-
Graph ThreadingDemaine, Erik D. / Kirkpatrick, Yael / Lin, Rebecca et al. | 2024
- 39
-
Simple and Optimal Online Contention Resolution Schemes for k-Uniform MatroidsDinev, Atanas / Weinberg, S. Matthew et al. | 2024
- 40
-
On the Black-Box Complexity of Correlation IntractabilityDöttling, Nico / Mour, Tamer et al. | 2024
- 41
-
The Message Complexity of Distributed Graph OptimizationDufoulon, Fabien / Pai, Shreyas / Pandurangan, Gopal / Pemmaraju, Sriram V. / Robinson, Peter et al. | 2024
- 42
-
Time- and Communication-Efficient Overlay Network Construction via GossipDufoulon, Fabien / Moorman, Michael / Moses Jr., William K. / Pandurangan, Gopal et al. | 2024
- 43
-
Homogeneous Algebraic Complexity Theory and Algebraic FormulasDutta, Pranjal / Gesmundo, Fulvio / Ikenmeyer, Christian / Jindal, Gorav / Lysikov, Vladimir et al. | 2024
- 44
-
On the (In)approximability of Combinatorial ContractsEzra, Tomer / Feldman, Michal / Schlesinger, Maya et al. | 2024
- 45
-
Two-State Spin Systems with Negative InteractionsFei, Yumou / Goldberg, Leslie Ann / Lu, Pinyan et al. | 2024
- 46
-
Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader ElectionFernando, Rex / Gelles, Yuval / Komargodski, Ilan et al. | 2024
- 47
-
Distribution Testing with a Confused CollectorFerreira Pinto Jr., Renato / Harms, Nathaniel et al. | 2024
- 48
-
Proving Unsatisfiability with Hitting FormulasFilmus, Yuval / Hirsch, Edward A. / Riazanov, Artur / Smal, Alexander / Vinyals, Marc et al. | 2024
- 49
-
Deterministic 3SUM-HardnessFischer, Nick / Kaliciak, Piotr / Polak, Adam et al. | 2024
- 50
-
One-Way Functions vs. TFNP: Simpler and ImprovedFolwarczný, Lukáš / Göös, Mika / Hubáček, Pavel / Maystre, Gilbert / Yuan, Weiqiang et al. | 2024
- 51
-
An Axiomatic Characterization of CFMMs and Equivalence to Prediction MarketsFrongillo, Rafael / Papireddygari, Maneesha / Waggoner, Bo et al. | 2024
- 52
-
Rethinking Fairness for Human-AI Collaboration (Extended Abstract)Ge, Haosen / Bastani, Hamsa / Bastani, Osbert et al. | 2024
- 53
-
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming VerificationGhosh, Prantar / Shah, Vihan et al. | 2024
- 54
-
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC CodesGolowich, Louis / Kaufman, Tali et al. | 2024
- 55
-
Electrical Flows for Polylogarithmic Competitive Oblivious RoutingGoranci, Gramoz / Henzinger, Monika / Räcke, Harald / Sachdeva, Sushant / Sricharan, A. R. et al. | 2024
- 56
-
An Algorithm for Bichromatic Sorting with Polylog Competitive RatioGoswami, Mayank / Jacob, Riko et al. | 2024
- 57
-
Communicating with Anecdotes (Extended Abstract)Haghtalab, Nika / Immorlica, Nicole / Lucier, Brendan / Mobius, Markus / Mohan, Divyarthi et al. | 2024
- 58
-
An Improved Protocol for ExactlyN with More Than 3 PlayersHambardzumyan, Lianna / Pitassi, Toniann / Sherif, Suhail / Shirley, Morgan / Shraibman, Adi et al. | 2024
- 59
-
Equivocal Blends: Prior Independent Lower BoundsHartline, Jason / Johnsen, Aleck et al. | 2024
- 60
-
The Chromatic Number of Kneser Hypergraphs via Consensus DivisionHaviv, Ishay et al. | 2024
- 61
-
Quickly Determining Who Won an ElectionHellerstein, Lisa / Liu, Naifeng / Schewior, Kevin et al. | 2024
- 62
-
On the Complexity of Algorithms with Predictions for Dynamic Graph ProblemsHenzinger, Monika / Saha, Barna / Seybold, Martin P. / Ye, Christopher et al. | 2024
- 63
-
TFNP Intersections Through the Lens of Feasible DisjunctionHubáček, Pavel / Khaniki, Erfan / Thapen, Neil et al. | 2024
- 64
-
Exponential-Time Approximation Schemes via CompressionInamdar, Tanmay / Kundu, Madhumita / Parviainen, Pekka / Ramanujan, M. S. / Saurabh, Saket et al. | 2024
- 65
-
FPT Approximation for Capacitated Sum of RadiiJaiswal, Ragesh / Kumar, Amit / Yadav, Jatin et al. | 2024
- 66
-
A VLSI Circuit Model Accounting for Wire DelayJin, Ce / Williams, R. Ryan / Young, Nathaniel et al. | 2024
- 67
-
Small Sunflowers and the Structure of Slice Rank DecompositionsKaram, Thomas et al. | 2024
- 68
-
Distributional PAC-Learning from Nisan’s Natural ProofsKarchmer, Ari et al. | 2024
- 69
-
Quantum and Classical Low-Degree Learning via a Dimension-Free Remez InequalityKlein, Ohad / Slote, Joseph / Volberg, Alexander / Zhang, Haonan et al. | 2024
- 70
-
A Combinatorial Approach to Robust PCAKong, Weihao / Qiao, Mingda / Sen, Rajat et al. | 2024
- 71
-
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free GraphsLee, Euiwoong / Manurangsi, Pasin et al. | 2024
- 72
-
Classical vs Quantum Advice and Proofs Under Classically-Accessible OracleLi, Xingjian / Liu, Qipeng / Pelecanos, Angelos / Yamakawa, Takashi et al. | 2024
- 73
-
Dynamic Maximal Matching in Clique NetworksLi, Minming / Robinson, Peter / Zhu, Xianbin et al. | 2024
- 74
-
Intersection Classes in TFNP and Proof ComplexityLi, Yuhao / Pires, William / Robere, Robert et al. | 2024
- 75
-
Total NP Search Problems with Abundant SolutionsLi, Jiawei et al. | 2024
- 76
-
Making Progress Based on False DiscoveriesLivni, Roi et al. | 2024
- 77
-
Kernelization of Counting ProblemsLokshtanov, Daniel / Misra, Pranabendu / Saurabh, Saket / Zehavi, Meirav et al. | 2024
- 78
-
Modularity and Graph ExpansionLouf, Baptiste / McDiarmid, Colin / Skerman, Fiona et al. | 2024
- 79
-
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor DecompositionsMahankali, Arvind V. / Woodruff, David P. / Zhang, Ziyu et al. | 2024
- 80
-
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is FalseMazor, Noam / Pass, Rafael et al. | 2024
- 81
-
A Myersonian Framework for Optimal Liquidity Provision in Automated Market MakersMilionis, Jason / Moallemi, Ciamac C. / Roughgarden, Tim et al. | 2024
- 82
-
A Computational Separation Between Quantum No-Cloning and No-TelegraphingNehoran, Barak / Zhandry, Mark et al. | 2024
- 83
-
On the Size Overhead of Pairwise SpannersNeiman, Ofer / Shabat, Idan et al. | 2024
- 84
-
Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment ConstraintsNeogi, Rian / Pashkovich, Kanstantsin / Swamy, Chaitanya et al. | 2024
- 85
-
General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean EstimationNikolov, Aleksandar / Tang, Haohua et al. | 2024
- 86
-
Rumors with Changing CredibilityOut, Charlotte / Rivera, Nicolás / Sauerwald, Thomas / Sylvester, John et al. | 2024
- 87
-
Tensor Reconstruction Beyond Constant RankPeleg, Shir / Shpilka, Amir / Volk, Ben Lee et al. | 2024
- 88
-
Color Fault-Tolerant SpannersPetruschka, Asaf / Sapir, Shay / Tzalik, Elad et al. | 2024
- 89
-
On Generalized Corners and Matrix MultiplicationPratt, Kevin et al. | 2024
- 90
-
Pseudorandom Linear Codes Are List-Decodable to CapacityPutterman, Aaron (Louie) / Pyne, Edward et al. | 2024
- 91
-
Lower Bounds for Planar Arithmetic CircuitsRamya, C. / Shastri, Pratik et al. | 2024
- 92
-
Parity vs. AC0 with Simple Quantum PreprocessingSlote, Joseph et al. | 2024
- 93
-
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic TimeSong, Zhao / Zhang, Lichen / Zhang, Ruizhe et al. | 2024
- 94
-
Differentially Private Approximate Pattern MatchingSteiner, Teresa Anna et al. | 2024
- 95
-
Stretching Demi-Bits and Nondeterministic-Secure PseudorandomnessTzameret, Iddo / Zhang, Lu-Ming et al. | 2024
- 96
-
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing ThesisValiant, Gregory et al. | 2024
- 97
-
Quantum Event Learning and Gentle Random MeasurementsWatts, Adam Bene / Bostanci, John et al. | 2024
- 98
-
Maximizing Miner Revenue in Transaction Fee Mechanism DesignWu, Ke / Shi, Elaine / Chung, Hao et al. | 2024
- 99
-
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output FunctionsYu, Huacheng / Zhan, Wei et al. | 2024
- 100
-
Sampling, Flowers and CommunicationYu, Huacheng / Zhan, Wei et al. | 2024
- 101
-
Quantum Money from Abelian Group ActionsZhandry, Mark et al. | 2024
- 102
-
The Space-Time Cost of Purifying Quantum ComputationsZhandry, Mark et al. | 2024
- 103
-
Advanced Composition Theorems for Differential ObliviousnessZhou, Mingxun / Zhao, Mengshi / Chan, T-H. Hubert / Shi, Elaine et al. | 2024