Imagen de Portada

Pointer Chasing with Unlimited Interaction

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Fischer, Orr, Oshman, Rotem, Rosen, Adi, Roth, Tal
Formato:	Preprint
Publicado:	2025
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
por: Mao, Xinyu, et al.
Publicado: (2024)

Semi-Streaming Algorithms for Graph Property Certification
por: Das, Avinandan, et al.
Publicado: (2025)

King Chasing Problem in Chinese Chess is NP-hard
por: Li, Chao, et al.
Publicado: (2026)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
por: Shpilka, Amir, et al.
Publicado: (2026)

A Wild Sheep Chase Through an Orchard
por: Dempsey, Jordan, et al.
Publicado: (2024)

Non-signalling parallel repetition using de Finetti reductions
por: Arnon, Rotem, et al.
Publicado: (2014)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
por: Błasiok, Jarosław, et al.
Publicado: (2026)

The Rank-Ramsey Problem and the Log-Rank Conjecture
por: Beniamini, Gal, et al.
Publicado: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
por: Elbaz, Tal, et al.
Publicado: (2025)

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions
por: Herman, Tal, et al.
Publicado: (2024)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
por: Aivasiliotis, Panagiotis, et al.
Publicado: (2025)

Quantum-proof multi-source randomness extractors in the Markov model
por: Arnon, Rotem, et al.
Publicado: (2015)

A Relativizing MIP for BQP
por: Aaronson, Scott, et al.
Publicado: (2026)

Parameterised Holant Problems
por: Aivasiliotis, Panagiotis, et al.
Publicado: (2024)

Improved Lower Bounds for QAC0
por: Joshi, Malvika Raj, et al.
Publicado: (2025)

Spiky Rank and Its Applications to Rigidity and Circuits
por: Hambardzumyan, Lianna, et al.
Publicado: (2026)

Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
por: Bogdanov, Andrej, et al.
Publicado: (2025)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
por: Fischer, Nick, et al.
Publicado: (2025)

Two-State Spin Systems with Negative Interactions
por: Fei, Yumou, et al.
Publicado: (2023)

Models That Prove Their Own Correctness
por: Amit, Noga, et al.
Publicado: (2024)

Quantum-Computable One-Way Functions without One-Way Functions
por: Kretschmer, William, et al.
Publicado: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
por: Arteche, Noel, et al.
Publicado: (2024)

Analysis of Boundary Behaviour of Quasidisks and Jordan Repellers
por: Binder, Ilia, et al.
Publicado: (2025)

Counting Subgraphs in Somewhere Dense Graphs
por: Bressan, Marco, et al.
Publicado: (2022)

Hardness results for decoding the surface code with Pauli noise
por: Fischer, Alex, et al.
Publicado: (2023)

The Planted Orthogonal Vectors Problem
por: Kühnemann, David, et al.
Publicado: (2025)

Interactive Proofs For Distribution Testing With Conditional Oracles
por: Biswas, Ari, et al.
Publicado: (2025)

Quantum Cryptography in Algorithmica
por: Kretschmer, William, et al.
Publicado: (2022)

A Comparison Test for Meromorphic Extensions
por: Glücksam, Adi, et al.
Publicado: (2026)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
por: Filmus, Yuval, et al.
Publicado: (2020)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
por: Garg, Abhibhav, et al.
Publicado: (2025)

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
por: Focke, Jacob, et al.
Publicado: (2021)

Quantum Interactive Oracle Proofs
por: Sun, Baocheng, et al.
Publicado: (2026)

Efficiently Batching Unambiguous Interactive Proofs
por: Berger, Bonnie, et al.
Publicado: (2025)

The Complexity of Counting Small Sub-Hypergraphs
por: Bressan, Marco, et al.
Publicado: (2025)

Interactive Oracle Proofs of Proximity to Codes on Graphs
por: Delavenne, Hugo, et al.
Publicado: (2025)

Multi-Prover Interactive Proof Systems with Leakage
por: Asadi, Vahid R., et al.
Publicado: (2026)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
por: Grewal, Sabee, et al.
Publicado: (2025)

Is nasty noise actually harder than malicious noise?
por: Blanc, Guy, et al.
Publicado: (2025)

Measurable entire functions II
por: Glücksam, Adi, et al.
Publicado: (2025)