Cover Image

Separations between Combinatorial Measures for Transitive Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Sourav, Kayal, Chandrima, Paraashar, Manaswi
Format:	Preprint
Published:	2021
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

Testing Isomorphism of Boolean Functions over Finite Abelian Groups
by: Datta, Swarnalipa, et al.
Published: (2025)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
by: Datta, Swarnalipa, et al.
Published: (2026)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
by: Samar, Sahil, et al.
Published: (2026)

The Interplay Between Domination and Separation in Graphs
by: Chakraborty, Dipayan, et al.
Published: (2026)

On the Complexity of Combinatorial Optimization on Fixed Structures
by: Megiddo, Nimrod
Published: (2024)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

A faster FPRAS for #NFA
by: Meel, Kuldeep S., et al.
Published: (2023)

Constructive Separations and Their Consequences
by: Chen, Lijie, et al.
Published: (2022)

Reasonable Bounds for Combinatorial Lines of Length Three
by: Bhangale, Amey, et al.
Published: (2024)

Resolution Over Linear Equations: Combinatorial Games for Tree-like Size and Space
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
by: Chia, Nai-Hui, et al.
Published: (2024)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
by: Chakraborty, Sourav, et al.
Published: (2024)

Subordination Involving Gauss Hypergeometric Function
by: Kumar, Anish, et al.
Published: (2024)

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

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
by: Bhattacharjee, Sutanay, et al.
Published: (2026)

Combinatorial refinement on circulant graphs
by: Kluge, Laurence
Published: (2022)

On the Smoothed Complexity of Combinatorial Local Search
by: Giannakopoulos, Yiannis, et al.
Published: (2022)

Derandomizing Isolation In Catalytic Logspace
by: Arvind, V., et al.
Published: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

Symport/Antiport P Systems with Membrane Separation Characterize P^(#P)
by: Ducros, Vivien, et al.
Published: (2025)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
by: Bhattacharya, Sreejata Kishor, et al.
Published: (2024)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Reinforced Generation of Combinatorial Structures: Ramsey Numbers
by: Nagda, Ansh, et al.
Published: (2026)

Matrix Chaos Inequalities and Chaos of Combinatorial Type
by: Bandeira, Afonso S., et al.
Published: (2024)

Nonogram: Complexity of Inference and Phase Transition Behavior
by: Foote, Aaron, et al.
Published: (2025)

Explaining the Ubiquity of Phase Transitions in Decision Problems
by: Jackson, Andrew
Published: (2025)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
by: Grigorescu, Elena, et al.
Published: (2025)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
by: Putterman, Aaron, et al.
Published: (2026)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
by: Jackson, Andrew
Published: (2025)

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
by: Devillers, Raymond, et al.
Published: (2022)