1 citations · 1 across the 9 of their papers we have counts for
10 papers
Counting almost independent sets in regular graphs
Gaia Carenini
Kahn proved that, among bipartite -regular graphs on vertices, the number of independent sets is maximized by a disjoint union of copies of . Zhao later extended th…
Blocky Matrices and Group Idempotents
Gaia Carenini
We prove a common generalization of two structure theorems: the dimension-free decomposition theorem for idempotent Schur multipliers and the idempotent theorem in harmonic analysi…
The Scaling Window of Random -SAT
Gaia Carenini
We prove a general upper bound for scaling windows of sparse monotone covering problems. From that, we deduce that for every fixed value , the window of random -SAT is…
Ranked spreadness and sample-based testing
Gaia Carenini
In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coor…
A quantitative container characterization of one-sided testability
Gaia Carenini, Cameron Seth, Yuichi Yoshida
We give a quantitative combinatorial characterization of size-oblivious one-sided testability in the dense graph model, resolving a question of Alon, Fischer, Newman, and Shapira.…
Embedding Induced Bounded Degree Graphs
Gaia Carenini
We prove a sparse embedding theorem for induced embeddings of bounded-degree graphs. The theorem applies to pairs : the graph supplies the positive edges of the t…
A unified abstract regularity lemma
Gaia Carenini, Leonardo Franchi
The goal of this short note is to prove a unified abstract regularity lemma which recovers Szemerédi's graph regularity lemma, Green's arithmetic regularity lemma, and a regularity…
A Sparse Transference Principle for a Non-Monotone Ramsey Property
Gaia Carenini
We prove a sparse transference theorem for induced Ramsey graphs. The theorem transfers the weighted random-host proof of Aragão, Campos, Dahia, Filipe, and Marciano to the sparse…
A strengthening of Chang's lemma
Gaia Carenini, Leonardo Franchi
We prove a strengthening of Chang's lemma for subsets of . The classical conclusion that the large spectrum is contained in a subspace of dimension at most $2\vareps…
Quantum Automating -Frege Is LWE-Hard
Noel Arteche, Gaia Carenini, Matthew Gray
We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic as…