dorsal/arxiv
View SchemaComparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds
| Authors | M. de Graaf, P. Valiant |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0211179 |
| URL | https://arxiv.org/abs/quant-ph/0211179 |
Abstract
We show that an oracle A that contains either 1/4 or 3/4 of all strings of length n can be used to separate EQP from the counting classes MOD_{p^k}P. Our proof makes use of the degree of a representing polynomial over the finite field of size p^k. We show a linear lower bound on the degree of this polynomial. We also show an upper bound of O(n^{1/log_p m}) on the degree over the ring of integers modulo m, whenever m is a squarefree composite with largest prime factor p.
{
"annotation_id": "eb354fe1-712e-4e9d-a9a2-e1b98511418a",
"date_created": "2026-03-02T18:01:56.670000Z",
"date_modified": "2026-03-02T18:01:56.670000Z",
"file_hash": "dc45666bec3aebc9826dc38fe3cfc2ab6832b22c17c857ddc89856ae0b369d3a",
"private": false,
"record": {
"abstract": "We show that an oracle A that contains either 1/4 or 3/4 of all strings of\nlength n can be used to separate EQP from the counting classes MOD_{p^k}P. Our\nproof makes use of the degree of a representing polynomial over the finite\nfield of size p^k. We show a linear lower bound on the degree of this\npolynomial.\n We also show an upper bound of O(n^{1/log_p m}) on the degree over the ring\nof integers modulo m, whenever m is a squarefree composite with largest prime\nfactor p.",
"arxiv_id": "quant-ph/0211179",
"authors": [
"M. de Graaf",
"P. Valiant"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Comparing EQP and MOD_{p^k}P using Polynomial Degree Lower Bounds",
"url": "https://arxiv.org/abs/quant-ph/0211179"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b1fd4fa8-799b-426c-a171-89a9ed635017",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}