:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bisoyi, Sagar, Dinesh, Krishnamoorthy, Rai, Bhabya Deep, Sarma, Jayalal
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2409.07208
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Hazard-free Decision Trees
by: Benson, Deepu, et al.
Published: (2025)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

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

NP-Completeness of Multicast Beamforming in Wireless Communication
by: Shrestha, Sagar
Published: (2025)

The Computational Complexity of Almost Stable Clustering with Penalties
by: Khodamoradi, Kamyar, et al.
Published: (2025)

One-Way Functions and Polynomial Time Dimension
by: Nandakumar, Satyadev, et al.
Published: (2024)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
by: S., Karthik C., et al.
Published: (2021)

Polynomial-Time PIT from (Almost) Necessary Assumptions
by: Andrews, Robert, et al.
Published: (2025)

Can Almost Everybody be Almost Happy? PCP for PPAD and the Inapproximability of Nash
by: Babichenko, Yakov, et al.
Published: (2015)

Qubit Routing for (Almost) Free
by: de Griend, Arianne Meijer-van
Published: (2026)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
by: Hörsch, Florian, et al.
Published: (2025)

$m$-Eternal Dominating Set Problem on Subclasses of Chordal Graphs
by: Rai, Ashutosh, et al.
Published: (2026)

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
by: Guruswami, Venkatesan, et al.
Published: (2024)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
by: Rai, Shanthanu S
Published: (2024)

Rounding Almost Commuting Hamiltonians
by: Faisal, Islam, et al.
Published: (2026)

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Closure under factorization from a result of Furstenberg
by: Bhattacharjee, Somnath, et al.
Published: (2025)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
by: Sarkar, Rohit Sarma, et al.
Published: (2024)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
by: Asadi, Vahid R., et al.
Published: (2026)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

RoPE Attention Can Be Trained in Almost Linear Time
by: Cao, Yang, et al.
Published: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Equivalence of Countable and Computable
by: Zhang, Hantao
Published: (2024)

Lossy Catalytic Computation
by: Gupta, Chetan, et al.
Published: (2024)

An Overview of the Theory of Instances Computational Complexity
by: Jorge A. Ruiz-Vanoye
Published: (2011)

The Radical Solution and Computational Complexity
by: Zheng, Bojin, et al.
Published: (2024)

The Computational Complexity of Factored Graphs
by: Gupta, Shreya, et al.
Published: (2024)

Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)

Computational Complexity of Game Boy Games
by: Tirmazi, Hayder, et al.
Published: (2024)

Assembly Theory and its Relationship with Computational Complexity
by: Kempes, Christopher P., et al.
Published: (2024)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
by: Erhardt, Alexander, et al.
Published: (2025)

Computing the Elementary Symmetric Polynomials in Positive Characteristics
by: Orzel, Ian
Published: (2025)

Reverse-Robust Computation with Chemical Reaction Networks
by: Kini, Ravi, et al.
Published: (2026)

Topics in Theoretical Computer Science
by: Rode, Alexander Forrest
Published: (2025)

Computational Complexity and Integer Programming Formulation of the Oredango Puzzle
by: Takahata, Takuma, et al.
Published: (2025)