Pseudorandom Strings from Pseudorandom Quantum States (Englisch)
Freier Zugriff
- Neue Suche nach: Ananth, Prabhanjan
- Weitere Informationen zu Ananth, Prabhanjan:
- https://orcid.org/0000-0001-5387-5730
- Neue Suche nach: Lin, Yao-Ting
- Neue Suche nach: Yuen, Henry
- Weitere Informationen zu Yuen, Henry:
- https://orcid.org/0000-0002-2684-1129
- Neue Suche nach: Ananth, Prabhanjan
- Weitere Informationen zu Ananth, Prabhanjan:
- https://orcid.org/0000-0001-5387-5730
- Neue Suche nach: Lin, Yao-Ting
- Neue Suche nach: Yuen, Henry
- Weitere Informationen zu Yuen, Henry:
- https://orcid.org/0000-0002-2684-1129
- Neue Suche nach: Guruswami, Venkatesan
- Weitere Informationen zu 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
;
6:1-6:22
;
2024
-
ISBN:
-
ISSN:
- Aufsatz (Konferenz) / Elektronische Ressource
-
Titel:Pseudorandom Strings from Pseudorandom Quantum States
-
Beteiligte:Ananth, Prabhanjan ( Autor:in ) / Lin, Yao-Ting ( Autor:in ) / Yuen, Henry ( Autor:in ) / Guruswami, Venkatesan ( Herausgeber:in )
-
Erschienen in:LIPIcs, Volume 287, ITCS 2024 : 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) ; 287 ; 6:1-6:22Leibniz International Proceedings in Informatics (LIPIcs) ; 287 ; 6:1-6:22
-
Verlag:
- Neue Suche nach: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Erscheinungsdatum:24.01.2024
-
Format / Umfang:22 pages , 885879 byte
-
Anmerkungen:LIPIcs, Vol. 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), pages 6:1-6:22
-
ISBN:
-
ISSN:
-
DOI:
-
Medientyp:Aufsatz (Konferenz)
-
Format:Elektronische Ressource
-
Sprache:Englisch
-
Schlagwörter:
-
Lizenzbestimmungen:
-
Datenquelle:
Inhaltsverzeichnis Konferenzband
Die Inhaltsverzeichnisse werden automatisch erzeugt und basieren auf den im Index des TIB-Portals verfügbaren Einzelnachweisen der enthaltenen Beiträge. Die Anzeige der Inhaltsverzeichnisse kann daher unvollständig oder lückenhaft sein.
- 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