Cover Image

Simple Circuit Extensions for XOR in PTIME

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Carmosino, Marco, Dang, Ngu, Jackman, Tim
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Convergent Gate Elimination and Constructive Circuit Lower Bounds
by: Carmosino, Marco, et al.
Published: (2026)

Constructive Separations from Gate Elimination
by: Carmosino, Marco, et al.
Published: (2026)

An XOR Lemma for Deterministic Communication Complexity
by: Iyer, Siddharth, et al.
Published: (2024)

XOR Lemmas for Communication via Marginal Information
by: Iyer, Siddharth, et al.
Published: (2023)

Refuting approaches to the log-rank conjecture for XOR functions
by: Hatami, Hamed, et al.
Published: (2023)

One-Way Communication Complexity of Partial XOR Functions
by: Podolskii, Vladimir V., et al.
Published: (2023)

Strong XOR Lemma for Information Complexity
by: Sawettamalya, Pachara, et al.
Published: (2024)

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

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

Multi-Structural Games and Beyond
by: Carmosino, Marco, et al.
Published: (2023)

Parallel Repetition for $3$-Player XOR Games
by: Bhangale, Amey, et al.
Published: (2024)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
by: Chukhin, Nikolai, et al.
Published: (2024)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Parallel Play Saves Quantifiers
by: Carmosino, Marco, et al.
Published: (2024)

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
by: Mao, Songtao
Published: (2026)

A Simple Constructive Bound on Circuit Size Change Under Truth Table Perturbation
by: Krinkin, Kirill
Published: (2026)

Average-Case Reductions for $k$-XOR and Tensor PCA
by: Bresler, Guy, et al.
Published: (2026)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
by: Dinur, Itai, et al.
Published: (2021)

Arithmetic Circuits with Division
by: Sacher, Silas Cato
Published: (2025)

A Simple Proof that Ricochet Robots is PSPACE-Complete
by: Balanza-Martinez, Jose, et al.
Published: (2024)

Symmetric Distributions from Shallow Circuits
by: Kane, Daniel M., et al.
Published: (2025)

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

Circuits and Backdoors: Five Shades of the SETH
by: Lampis, Michael
Published: (2024)

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

Improved Bounds on the Space Complexity of Circuit Evaluation
by: Shalunov, Yakov
Published: (2025)

A Quadratic Lower Bound for Noncommutative Circuits
by: Shastri, Pratik
Published: (2026)

Optimal Depth-Three Circuits for Inner Product
by: Gurumukhani, Mohit, et al.
Published: (2026)

On the Complexity of Target Set Selection in Simple Geometric Networks
by: Dvořák, Michal, et al.
Published: (2023)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Range Avoidance in Boolean Circuits via Turan-type Bounds
by: Kuntewar, Neha, et al.
Published: (2025)

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

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
by: Gurumukhani, Mohit, et al.
Published: (2026)