Buchumschlag

Lifting with Inner Functions of Polynomial Discrepancy

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Manor, Yahel, Meir, Or
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

KRW Composition Theorems via Lifting
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2020)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
von: Meir, Or
Veröffentlicht: (2023)

Lifting for Arbitrary Gadgets
von: Iyer, Siddharth
Veröffentlicht: (2025)

One-Way Functions and Polynomial Time Dimension
von: Nandakumar, Satyadev, et al.
Veröffentlicht: (2024)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
von: Yao, Penghui, et al.
Veröffentlicht: (2025)

Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs
von: Räty, Eero, et al.
Veröffentlicht: (2024)

Optimal Depth-Three Circuits for Inner Product
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2026)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
von: Yang, Guangxu, et al.
Veröffentlicht: (2025)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
von: Wang, Cancan, et al.
Veröffentlicht: (2024)

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
von: Mao, Xinyu, et al.
Veröffentlicht: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
von: Dawar, Anuj, et al.
Veröffentlicht: (2025)

On Matrix Multiplication and Polynomial Identity Testing
von: Andrews, Robert
Veröffentlicht: (2022)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
von: Michno, Katzper
Veröffentlicht: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
von: Nechesov, Andrey
Veröffentlicht: (2024)

On Optimal Testing of Linearity
von: Arora, Vipul, et al.
Veröffentlicht: (2024)

Attacking the Polynomials in the Maze of Finite Fields problem
von: Barbero, Àngela, et al.
Veröffentlicht: (2026)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
von: Orzel, Ian
Veröffentlicht: (2025)

On Factorization of Sparse Polynomials of Bounded Individual Degree
von: Chuyoon, Aminadav, et al.
Veröffentlicht: (2026)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
von: Dutta, Pranjal, et al.
Veröffentlicht: (2024)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
von: Mukhopadhyay, Partha, et al.
Veröffentlicht: (2025)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
von: S., Karthik C., et al.
Veröffentlicht: (2021)

Extractors for Polynomial Sources over $\mathbb{F}_2$
von: Chattopadhyay, Eshan, et al.
Veröffentlicht: (2023)

Polynomial-Time PIT from (Almost) Necessary Assumptions
von: Andrews, Robert, et al.
Veröffentlicht: (2025)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
von: Arvind, V., et al.
Veröffentlicht: (2022)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2024)

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
von: Wu, Xudong, et al.
Veröffentlicht: (2025)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
von: Komarath, Balagopal, et al.
Veröffentlicht: (2025)

Lift-and-Project Integrality Gaps for Santa Claus
von: Bamas, Etienne
Veröffentlicht: (2024)

Low-Degree Polynomials Are Good Extractors
von: Alrabiah, Omar, et al.
Veröffentlicht: (2024)

A Critique of Du's "A Polynomial-Time Algorithm for 3-SAT
von: He, Yumeng, et al.
Veröffentlicht: (2024)

Positive Univariate Polynomials: SOS certificates, algorithms, bit complexity, and T-systems
von: Bender, Matías, et al.
Veröffentlicht: (2025)

Polynomial Lower Bounds for Arithmetic Circuits over Non-Commutative Rings
von: Raz, Ran
Veröffentlicht: (2026)

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
von: Amireddy, Prashanth, et al.
Veröffentlicht: (2025)

Information-Based Complexity vs Computational Complexity in Phaseless Polynomial Interpolation
von: Przybyłek, Michał R., et al.
Veröffentlicht: (2026)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
von: DeJesse, Nicholas, et al.
Veröffentlicht: (2025)

Optimal Polynomial-Time Estimators: A Bayesian Notion of Approximation Algorithm
von: Kosoy, Vanessa, et al.
Veröffentlicht: (2016)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2024)

Virtual Qudits for Simon's Problem: Dimension-Lifted Algorithms on Qubit Hardware
von: Semre, Abed, et al.
Veröffentlicht: (2025)

Inner-approximate Reachability Computation via Zonotopic Boundary Analysis
von: Ren, Dejin, et al.
Veröffentlicht: (2024)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
von: Le, Tran Duy Anh, et al.
Veröffentlicht: (2024)