††thanks<EMAIL_ADDRESS>ORCID: 0000-0003-2550-7038††thanks:
<EMAIL_ADDRESS>ORCID: 0000-0002-1287-8780††thanks:
<EMAIL_ADDRESS>ORCID: 0000-0001-9888-0971

# Dark Branches of Immortal Stars at the Galactic Center

Isabelle John  Stockholm University and The Oskar Klein Centre for
Cosmoparticle Physics, Alba Nova, 10691 Stockholm, Sweden  Rebecca K. Leane
Particle Theory Group, SLAC National Accelerator Laboratory, Stanford, CA
94035, USA  Kavli Institute for Particle Astrophysics and Cosmology, Stanford
University, Stanford, CA 94035, USA  Tim Linden  Stockholm University and The
Oskar Klein Centre for Cosmoparticle Physics, Alba Nova, 10691 Stockholm,
Sweden

###### Abstract

We show that stars in the inner parsec of the Milky Way can be significantly
affected by dark matter annihilation, producing population-level effects that
are visible in a Hertzsprung-Russell (HR) diagram. We establish the dark HR
diagram, where stars lie on a new stable _dark main sequence_ with similar
luminosities, but lower temperatures, than the standard main sequence. The
dark matter density in these stars continuously replenishes, granting these
stars immortality and solving multiple stellar anomalies. Upcoming telescopes
could detect the dark main sequence, offering a new dark matter discovery
avenue.

††preprint: SLAC-PUB-17770

Stars evolve along well-established tracks within which an equilibrium between
the gravitational force and the pressure from nuclear fusion can be
maintained. Their blackbody spectrum also directly links their luminosity,
temperature and radius. These relationships are apparent on the Hertzprung-
Russell (HR) diagram, which plots the observable stellar luminosities and
temperatures, tracing various mass-dependent tracks stars travel across over
their lifetime.

This standard picture of stellar evolution assumes that nuclear fusion is the
only process capable of providing pressure support for the star. However, in
the early Universe [1, 2, 3, 4, 5, 6, 7, 8], or in regions very close to the
Galactic Center [9, 10, 11, 12], dark matter annihilation may provide a
considerable additional energy source. In extreme cases, dark matter
annihilation can cause stars to move backwards along the HR diagrams towards
proto-stellar configurations (Hayashi track) that have extremely large radii
and low temperatures compared to standard stars [11]. In some cases, dark
matter annihilation can cause stars to be disrupted entirely [13].

In this _letter_ we produce, for the first time, a population-level
description of main sequence evolution under the influence of significant dark
matter energy injection – and construct a novel _dark main sequence_. We
discover a new branch of higher-mass dark matter powered stars that are
observationally distinct from the standard main sequence. The stability of
these stars is analogous to the hydrostatic equilibrium of standard stars – as
the star expands the dark matter capture rate can decrease (see App. I),
causing the stars to contract again. The continuous accretion of dark matter
fuel allows these stars to maintain equilibrium eternally, causing the dark
main sequence to dominate the stellar population.

Figure 1: The dark main sequence (top) compared to the standard main sequence
for stellar evolution (bottom), which predicts qualitatively different stellar
populations in the Galactic Center. The dark main sequence is shown for
benchmark parameters of 1 GeV dark matter mass, scattering cross section of
$3\times 10^{-35}$ cm2, and an NFW dark matter profile with $\gamma=1.5$.

Figure 1 shows our main result: the new dark main sequence (top), which
characterizes stars very close ($<$ 0.1 pc) to the Galactic Center. Compared
to the standard main sequence (bottom), there are striking differences. First,
dark matter powered stars can exist in stable equilibria at similar
luminosities, but lower temperatures (near the Henyey track) than the standard
main sequence. Second, the dark main sequence lacks low-mass stars, as they
are overpowered by dark matter and move backwards along the Hayashi track [11]
— potentially to the point that they are entirely disrupted [13].

Studying the impact of dark matter on stars at the population level allows us
to statistically distinguish the dark main sequence from the standard main
sequence. To date, the number of known stars in the inner parsec is limited,
and more stars are needed to robustly detect any effect from dark matter. This
will be possible with upcoming thirty-meter class telescopes, which will
measure many new stars near the Galactic Center [14].

Interestingly, our initial data regarding stars near the Galactic Center
already unveils numerous anomalies that might be solved by the dark main
sequence. Star formation models suggest that stars cannot form within $\sim$
0.1 pc of the central black hole, where the S-cluster stars are found [15].
Rather, the stars must have formed elsewhere and migrated towards the Galactic
Center [16]. Conversely, observations suggest that stars in this region are
young ($\lesssim 15$ Myr), which indicates that the stars might have formed
more locally [17]. The tension between these two observations is known as the
“paradox of youth” problem: Galactic Center stars are as bright as young stars
but show spectroscopic features of more evolved stars [16]. Additionally,
there is a “conundrum of old age”, which describes the paucity of old and
evolved stars, despite the fact that models predict the detection of many
evolved stars [18, 19]. Finally, observations indicate that the initial mass
function of stars near the Galactic Center is surprisingly top-heavy (biased
towards high-mass stars), with observations indicating that the stellar birth
distribution lies between $M^{-1.7}$ [20] and $M^{-0.45}$ [21], compared to a
standard Salpeter index of $M^{-2.35}$ [22]. These anomalous observations are
unique to stars at the Galactic Center, and are not well explained by
conventional stellar evolution models. The very inner Galaxy is exactly where
the dark matter density is high enough for dark matter annihilation to
substantially replace nuclear fusion as the stellar energy source [23, 11, 24,
25, 13], allowing stars to stay forever young despite their advanced age [26].
This explains both the paradox of youth (because the stars have had sufficient
time to migrate towards the Galactic Center), and the conundrum of old age
(because the stars continue to reside on or near the main sequence). Because
this effect is maximized in relatively high-mass stars ($\gtrsim\,$5
$M_{\odot}$), while less massive stars tend to evolve backwards along the
Hayashi track or be entirely disrupted, the observed stellar distribution will
naturally have a top-heavy initial mass function [21]. These otherwise
anomalous observations of Galactic Center stars are therefore all naturally
predicted on our dark main sequence.

Stellar Population Inputs.— To construct our standard and dark HR diagrams, we
generate a mock stellar population that evolves both with and without the
influence of dark matter. Throughout this letter, we choose relatively
standard star formation parameters which are also motivated by the observation
of S-cluster stars observed near the Galactic Center [17, 27].

We start by randomly selecting stars following a Salpeter initial mass
function [22]

$\frac{dN}{dM_{\star}}\sim M_{\star}^{-2.35},$ (1)

where $N$ is the number of stars and $M_{\star}$ is the stellar mass. We
consider stars with masses ranging from 1 to 20 $M_{\odot}$ with a step of
0.05 $M_{\odot}$.

We set the stellar distances to follow a radial distribution that falls as
$r^{-2}$ [28, 15, 29], ranging from ${4\times 10^{-5}}$ to ${4\times 10^{-2}}$
pc. Motivated by the migration scenario, where stars cannot form closely to
the inner black hole [16], our stellar evolution models in dark matter
scenarios do not include any dark matter energy injection until stars enter
the main sequence, meaning that the radial binning of stars is irrelevant
during their pre-main sequence life. We finally assume that star formation and
migration occurs in steady state throughout the 10 Gyr lifetime of our
simulations, matching the age of the Milky Way.

For simplicity, we assume that the stellar orbits are circular, $i.e.$ the
dark matter capture rate is constant along the orbit. While the orbits of
Galactic Center stars are highly eccentric, the equilibrium timescale for dark
matter capture and annihilation is much longer than the stars’ orbital period,
meaning that the effective dark matter annihilation rate is only set by the
time-averaged orbital radius. Thus, this only shifts the exact capture rate
for each star that is found somewhere along the region around Sagittarius A*
that we consider, and does not largely change our results.

Figure 2: The impact of dark matter burning on stars over a range of masses
and Galactic Center distances, for Benchmark Models 1 (left panel) and 2
(right panel). Green shades indicate how much main sequence stellar evolution
is slowed down by the added dark matter power compared to the standard
evolution scenario. This corresponds to stars that are more massive and
experience a lower dark matter density. Stars in higher density regions are
significantly changed and show atypical evolution: The stars maintain
equilibrium through dark matter burning and only rely on small amounts of
fusion, making them reside on the Henyey track (yellow shade), or have no
fusion at all, which corresponds to the Hayashi track (orange shades). This
essentially “freezes” their evolution, as stellar evolution is driven by
nuclear fusion. The continuous re-supply of captured dark matter acts as an
effectively infinite power source, making these stars immortal.

Dark Matter Inputs.— We generate two dark matter model benchmarks.
Qualitatively, we find similar behavior across both, and show that similar
behavior is expected for a wide range of dark matter parameters. In both
cases, we assume a dark matter mass of 1 GeV, but vary the following
parameters:

### Benchmark 1.

We set the dark matter-nucleon scattering cross section to ${\sigma_{\chi
N}=3\times 10^{-35}}$ cm2. For this, we follow our constraints on the
scattering cross section from Ref. [13] for the star S2, which stands as the
best-measured S-cluster object. To set the dark matter density along the
different orbits, we choose a generalized NFW profile [30] with index
${\gamma=1.5}$. This corresponds to dark matter densities of $\sim
10^{9}-10^{13}$ GeV/cm3 for the distances considered here.

### Benchmark 2.

We choose a smaller dark matter-nucleon scattering cross section of
${\sigma_{\chi N}=1\times 10^{-37}}$ cm2. For the dark matter density, we
choose a standard NFW (${\gamma=1.0}$), but include a density spike that
arises from the adiabatic accretion of matter by Sagittarius A* [31, 32]. We
follow the spike model from [33, 13], $i.e.$ ${\gamma=1.0}$,
${R_{\text{spike}}=10}$ pc and ${\gamma_{\text{spike}}=7/3}$. This results in
higher dark matter densities compared to Benchmark 1, and the density
increases more steeply towards the Galactic Center, i.e., $\sim
10^{10}-10^{16}$ GeV/cm3.

Our benchmarks are not excluded by direct detection for spin-dependent dark
matter models [34, 35, 36, 37, 38], and even given improved direct detection
limits in the future, there are a wide range of additional parameter points
that provide qualitatively similar results to those we show here. For example,
our qualitative results are not affected for lower dark matter masses. In
addition, at lower cross sections, large dark matter densities can compensate
for any decrease in the signal. Finally, we note that for extremely high
densities, the efficient annihilation of dark matter may cause the dark matter
density to saturate at a value that depends on the dark matter mass and
annihilation cross section. However, in the case of models that use stellar
capture to focus dark matter annihilation, our scattering cross-section limits
continue to apply even for extremely small annihilation cross-sections that
will not saturate up to very large densities.

Stellar Evolution Simulations.— We use the stellar evolution code MESA [39,
40, 41, 42, 43, 44], version r24.03.1 with Software Development Kit (SDK)
version 23.7.3, to investigate the effect of dark matter energy injection on a
wide range of stellar masses. We base our model on the default work model, but
implement a custom module to calculate the capture rate at each time step
according to the current stellar radius. To obtain the capture rate, we follow
the formalism of Ref. [45], under the assumption of capture-annihilation
equilibrium, and add the annihilation energy into the stellar core through the
inject_uniform_extra_heat parameter. The injection of the additional energy
can be restricted to a certain mass region of the star through the parameters
min_q_for_uniform_extra_heat and max_q_for_uniform_extra_heat. We consider the
stellar core to correspond to the inner 10% of the star, but have tested that
injecting the dark matter annihilation energy in the inner 1% only results in
slight numerical differences, while uniform injection throughout the star only
changes our results by a factor of a few, which does not have qualitative
effects. We assume that all stars initially form and evolve in a low dark
matter density environment until their early main sequence phase, $i.e.$ their
pre-main sequence evolution is not affected by dark matter. We assume that
these stars migrate as main sequence stars towards the Galactic Center where
their subsequent evolution is influenced by dark matter annihilation. As
discussed above, this migration scenario is a commonly considered case, due to
the fact that stellar formation close to Sagittarius A* is expected to be
inhibited [16]. In MESA, we start injecting the additional energy when the
hydrogen fraction in the star center drops below 0.67, which corresponds to an
early main sequence core composition, through the parameter
xa_central_lower_limit. Once the star experiences dark matter energy
injection, we evolve the star until it reaches the red giant branch phase,
using the stopping condition stop_at_phase_ZACHeB, or until an age of 10 Gyr
is reached, corresponding to the age of the Galaxy.

Results and Discussion.— Figure 2 shows the effects of dark matter energy
injection on stars of different masses and distances from the Galactic Center
for Benchmark 1 and 2. These models only differ in the dark matter-nucleon
scattering cross section and the underlying dark matter profile, that
determines the amount of dark matter a star can capture along its orbit. We
find that stellar evolution is affected in various ways:

  1. (1)

Longer-lived. The green shaded regions correspond to stars that are not
significantly or only moderately changed by dark matter burning. Their
evolution follows the typical stages, but as part of the nuclear fusion power
needed to maintain hydrostatic equilibrium is replaced by dark matter power,
hydrogen in the core fuses more slowly and thus the stars’ evolution is slowed
down. This makes the stars longer-lived. While light green shades correspond
to stars that are only slightly affected as their evolution times are similar
to the standard scenario, dark green regions represent stars that can become
as much as 10–100$\times$ longer-lived.

  2. (2)

Stuck on Henyey track. The yellow region corresponds to stars that are found
on the Henyey track in the HR diagram, which, in the standard evolutionary
scenario, is a rapid phase just before stars enter the main sequence, when
hydrogen burning is ignited and increasing. This means that at the onset of
dark matter burning in the stellar core, stars can move “backwards” in
evolution, returning from the main sequence to a stage with only small amounts
of nuclear fusion, and maintain equilibrium primarily through dark matter
burning. Dark stellar evolution on the Henyey track is extremely slow, until
eventually the star does run out of hydrogen in the core and moves back to a
more typical evolution on the red giant track. Thus, these stars are in
principle extremely long-lived and would eventually follow the standard
evolution stages, but, as in our simulations we do not evolve stars for longer
than 10 Gyr, which corresponds to the Galaxy’s age, these stars never move off
the Henyey track. Note that many of the stars in scenario (1) that are
significantly longer-lived ($\gtrsim 5$ times) also spend some time on the
Henyey track, but experience a lower amount of dark matter burning and thus
need to undergo more nuclear fusion, forcing them to move back to the main
sequence and resume evolution earlier.

  3. (3)

Stuck on Hayashi track. The orange region corresponds to dark matter powered
stars that are found in the region of the Hayashi track in the HR diagram,
which, in the standard picture, describes pre-main sequence stars that are
still contracting and have not yet started nuclear fusion. At the onset of
dark matter burning, main sequence stars evolve “backwards”, similar to the
stars halting on the Henyey track described above. In this scenario however,
dark matter burning replaces nuclear fusion entirely, and stars move all the
way to the Hayashi track. The stars do not undergo any further evolutionary
stages as long as the dark matter capture rate remains sufficiently high to
prevent nuclear fusion from resuming. A star like this might look like a
young, still-forming star but has features of a star that has undergone
nuclear fusion in the past – and is effectively immortal.

  4. (4)

Beyond Hayashi track. The dark orange region corresponds to stars moving back
onto the Hayashi track, similar to case (3). However, in this case, the stars
move further up the Hayashi track to even earlier evolutionary states. In our
MESA simulations, these stars end up higher on the Hayashi track than their
starting position. We emphasize that this scenario is highly reliant on the
modelling methods (as MESA does not simulate of the very early stages of star
formation). It is possible that these stars could expand even further or be
entirely disrupted by the dark matter energy injection. A scenario like this
may be consistent with G-objects, a recently discovered strange class of
objects found at similar orbits around Sgr A* as the S-cluster stars that
resemble clouds of gas surrounding a denser core [46, 47].

In both benchmarks, massive stars further out from the Galactic Center are the
least affected, while light stars can become immortal even at distances where
the dark matter density is not sufficient to significantly affect more massive
stars. The different dark matter density profiles are also reflected in Fig.
2: While Benchmark 1 (left panel) uses an NFW profile, Benchmark 2 (right
panel) includes a dark matter spike that steepens the profile and,
accordingly, the region of the parameter space in which stars are immortal.

Figure 3: Dark HR diagram for a population of Galactic Center stars, for our
dark matter benchmark 2, with 1-GeV dark matter mass, scattering cross section
of $10^{-37}$ cm2, and NFW dark matter profile with a spike (see text for
details).

Figure 1 shows HR diagrams for a population of Galactic Center stars with and
without dark matter for Benchmark 1, and Figure 3 shows the dark HR diagram
for the our additional Benchmark 2. We include evolutionary stages from the
early main sequence up until the stars leave the main sequence and start
hydrogen shell burning. We do not include stars that have become red giants
and start core Helium burning, $i.e.$ most of the stars on the HR diagram are
main sequence stars. Most stars lie on the main sequence, $i.e.$ the diagonal
line, where more massive stars are at the top left, as they are hotter and
more luminous, and lighter stars are at the bottom right. The small number of
stars scattered to the right of the main sequence are stars that are older
stars that have just moved away from the main sequence towards the red giant
branch; which manifests in a lower temperature compared to the main sequence.

For our dark main sequence in Figs. 1 and 3, the effect of dark matter burning
results in strikingly distinct features. Compared to the standard main
sequence, the Hayashi tracks (approximately vertical tracks at low
temperatures) are densely populated with immortal stars (see scenarios (3) and
(4) above), and the Henyey tracks (approximately horizontal tracks at high
luminosities), are clearly visible (see scenario (2) above), containing stars
that are mostly powered by dark matter burning with only small amounts of
nuclear fusion, making their evolution extremely slow. Additionally, the
region where light main sequence stars are located (lower luminosities and
temperatures), are only sparsely populated, as most of these stars have moved
to the Hayashi tracks. In Benchmark 2 (Fig. 3), more of these low-mass stars
remain on the main sequence compared to Benchmark 1 (Fig. 1), due to the
steeply increasing dark matter density of the spike model, as can also be seen
in Fig. 2. We note that the striped features observed in the Henyey branch are
due to our distance (and thus dark matter density) binning, which sets the
stellar luminosity, and are thus not a physical feature.

Finally, we note that the fraction of high-mass stars increases in dark matter
scenarios due to the effect of stellar immortality. If only standard stellar
models were considered, the large fraction of high-mass stars would be
misconstrued as evidence of a top-heavy initial mass function (IMF).
Intriguingly, observations have found evidence of a top-heavy IMFs at the
Galactic center [48, 20, 21]. We find that dark matter would harden the IMF,
compared to a Salpeter IMF, by approximately ${\sim 0.5-2.5}$, as shown in
Figs. 1 and 3.

Summary and Outlook.— We have produced the first population-level prediction
for stellar evolution under the presence of dark matter capture and
annihilation near the Galactic Center. We have established a new “dark main
sequence” that is observable in the Hertzsprung-Russell diagram of stars
observed in dark matter rich environments. This sequence has three observable
characteristics that clearly separate it from standard main sequence stellar
evolution: (1) a top-heavy initial mass function along the main sequence
branch, produced by the efficient removal of low-mass stars off of the main
sequence and into locations on the Hayashi or Beyond-Hayashi tracks, (2) a
bright and densely populated Hayashi track, produced by low-mass main sequence
stars which achieve eternally stable equilibria in configurations with large
stellar radii and low stellar temperatures, (3) a bright and densely populated
Henyey track at higher-masses, populated by effectively immortal (typical
lifespans $>$10 Gyr) high-mass stars with similar luminosities but slightly
lower temperatures than their main sequence configurations.

Excitingly, there are several anomalies in Galactic Center stellar
observations which can be simultaneously explained by stellar evolution along
our dark main sequence. The top-heavy initial mass function near the Galactic
Center is automatically produced by our simulations with dark matter, while
both the paradox of youth and conundrum of old age can be explained if
relatively high-mass stars are powered indefinitely by dark matter
annihilation. Finally, observations of G-objects (extremely large gas clouds
which may hold a central star), may be consistent with Beyond-Hayashi
evolution, although the stability of such solutions falls beyond the
parameters of our current MESA modeling. We will investigate this in upcoming
work.

Going forward, our stellar population predictions have important implications
for the extremely difficult observations of Galactic Center stars. The vastly
cooler temperatures of Hayashi track stars may impede their detection unless
observational efforts specifically look for such objects. Additionally, the
dark Henyey track stars may be mischaracterized as standard main sequence
stars if the possibility of Henyey track evolution is not considered.
Verifying or ruling out dark main sequence evolution will require the
detection of new stars for sufficient sampling and to sufficiently populate
the dark main sequence. This will be possible with new telescopes, such as
thirty-meter class telescopes, or with additional stars measured with the Very
Large Telescope (VLT) or the Keck Observatory.

Acknowledgments.— We thank Andrea Ghez for helpful discussions. This work was
supported by a collaborative visit funded and hosted by Stanford KIPAC and the
Cosmology and Astroparticle Student and Postdoc Exchange Network (CASPEN).
I.J. and T.L. acknowledge support by the Swedish Research Council under
contract 2022-04283. T.L. also acknowledges support from the Swedish National
Space Agency under contract 117/19. R.K.L. is supported by the U.S. Department
of Energy under Contract DE-AC02-76SF00515. This project used computing
resources from the National Academic Infrastructure for Supercomputing in
Sweden (NAISS) under project NAISS 2023/3-21.

Dark Branches of Immortal Stars at the Galactic Center

Supplemental Material
Isabelle John, Rebecca K. Leane, and Tim Linden

##  I Dark Matter Capture Rates for Actively Evolving Stars

Figure S1: Left panel: Dark matter capture rate as a function of stellar
radius, for a scattering cross section of $10^{-37}$ cm2. Right panel: Capture
rate as a function of scattering cross section, for stellar radii of 1 and 10
solar radii, and a fixed stellar mass of 1 solar mass. The dashed line shows
the transition cross sections for the two stars. To calculate these capture
rates, we assume an example dark matter mass of 0.1 GeV, orbital velocity of
$10^{8}$ cm/s and dark matter density $2\times 10^{12}$ GeV/cm3.

Figure S1 (left panel) shows the dark matter capture rates expected as the
star undergoes evolution, $i.e.$ taking into account the changing mass and
radius of the star. The first point to note, as highlighted by the left
figure, is that the capture rate changes as the stellar radius changes, and so
it is important to take the updated stellar radius into account for the
capture rate as the star evolves. This implementation is an improvement over
previous studies [13]. The second point is that for a fixed stellar mass and
fixed dark matter scattering cross section, the dark matter capture rate can
decrease as the stellar radius increases. The reason for this can be
understood from the right figure.

Figure S1 (right panel) shows the capture rate as a function of scattering
cross section, for two example stars of radius 1 and 10 times the solar
radius, for a fixed stellar mass of 1 solar mass. We also show as the dashed
line the transition cross section for these two example stars. Here, the
transition cross section is $\sigma_{\rm tr}=\pi R^{2}/N$, where $N$ is the
number of stellar nucleons available for scattering. Physically, this
corresponds to a mean free path of the dark matter of about the size of the
star, and therefore corresponds to the cross section above which multiple
scatters can be needed for capture to occur. Below this cross section, dark
matter can only be captured with roughly one scatter, as the scattering is so
weak that on average one or zero scatters occur. As the mass of these two
example stars stays the same, the number of targets also remains the same,
except they are distributed over a larger volume, the transition cross section
between the two simply scales as their radius ratio squared.

As Fig. S1 (right) shows, larger radii stars do capture more dark matter in
the sufficiently-high cross section regime where roughly all incoming dark
matter is captured, as their surface areas available for capture are larger.
However, less dense objects have lower escape velocities, so require more
scatters (i.e. a larger cross section) to bring the dark matter to a low
enough speed to be captured, which is why the larger star needs a larger cross
section increase above its transition cross section at $\sim 10^{-33}$ cm2 to
reach its geometric capture rate. In comparison, the smaller radius star
increases less above its $\sim 10^{-35}$ cm2 transition before reaching
geometric capture, because it is more efficient at capture (and so needs fewer
scatters) due to its higher escape velocity. Once comparing the capture rates
for these two objects at their transition cross section, the puffier star is
already down a larger penalty compared to its geometric maximum capture than
the more dense star, which is then cancelled out by its size, such that at
their respective transition cross sections (which are two orders of magnitude
apart) they actually have the same capture rate. This means that, because the
capture rate decreases linearly with cross section below the transition cross
section, the puffier, larger radius star has a lower capture rate at smaller
cross sections, as its transition cross section is higher to start with. This
can lead to interesting effects during the stellar evolution process as the
star becomes larger, as the dark matter capture and annihilation driving the
growth in radii consequently decreases.

## References

  * Spolyar  _et al._ [2008] D. Spolyar, K. Freese, and P. Gondolo, Phys. Rev. Lett. 100, 051101 (2008), arXiv:0705.0521 [astro-ph] .
  * Iocco [2008] F. Iocco, Astrophys. J. Lett. 677, L1 (2008), arXiv:0802.0941 [astro-ph] .
  * Freese  _et al._ [2009] K. Freese, P. Gondolo, J. A. Sellwood, and D. Spolyar, Astrophys. J. 693, 1563 (2009), arXiv:0805.3540 [astro-ph] .
  * Taoso  _et al._ [2008] M. Taoso, G. Bertone, G. Meynet, and S. Ekstrom, Phys. Rev. D 78, 123510 (2008), arXiv:0806.2681 [astro-ph] .
  * Sivertsson and Gondolo [2011] S. Sivertsson and P. Gondolo, Astrophys. J. 729, 51 (2011), arXiv:1006.0025 [astro-ph.CO] .
  * Freese  _et al._ [2016] K. Freese, T. Rindler-Daller, D. Spolyar, and M. Valluri, Rept. Prog. Phys. 79, 066902 (2016), arXiv:1501.02394 [astro-ph.CO] .
  * Ilie  _et al._ [2020a] C. Ilie, C. Levy, J. Pilawa, and S. Zhang, (2020a), arXiv:2009.11478 [astro-ph.CO] .
  * Ilie  _et al._ [2020b] C. Ilie, C. Levy, J. Pilawa, and S. Zhang, (2020b), arXiv:2009.11474 [astro-ph.CO] .
  * Salati and Silk [1989] P. Salati and J. Silk, Astrophys. J. 338, 24 (1989).
  * Fairbairn  _et al._ [2008] M. Fairbairn, P. Scott, and J. Edsjo, Phys. Rev. D 77, 047301 (2008), arXiv:0710.3396 [astro-ph] .
  * Scott  _et al._ [2009] P. Scott, M. Fairbairn, and J. Edsjo, Mon. Not. Roy. Astron. Soc. 394, 82 (2009), arXiv:0809.1871 [astro-ph] .
  * Lopes and Lopes [2021] J. Lopes and I. Lopes, Astron. Astrophys. 651, A101 (2021), arXiv:2107.13885 [astro-ph.SR] .
  * John  _et al._ [2023] I. John, R. K. Leane, and T. Linden, (2023), arXiv:2311.16228 [astro-ph.HE] .
  * Skidmore  _et al._ [2015] W. Skidmore _et al._ (TMT International Science Development Teams & TMT Science Advisory Committee), Res. Astron. Astrophys. 15, 1945 (2015), arXiv:1505.01195 [astro-ph.IM] .
  * Sabha  _et al._ [2012] N. Sabha, A. Eckart, D. Merritt, M. Zamaninasab, G. Witzel, M. García-Marín, B. Jalali, M. Valencia-S., S. Yazici, R. Buchholz, B. Shahzamanian, C. Rauch, M. Horrobin, and C. Straubmeier, Astronomy & Astrophysics 545, A70 (2012), arXiv:1203.2625 [astro-ph.GA] .
  * Ghez  _et al._ [2005] A. M. Ghez, S. Salim, S. D. Hornstein, A. Tanner, M. Morris, E. E. Becklin, and G. Duchene, Astrophys. J. 620, 744 (2005), arXiv:astro-ph/0306130 .
  * Habibi  _et al._ [2017] M. Habibi, S. Gillessen, F. Martins, F. Eisenhauer, P. M. Plewa, O. Pfuhl, E. George, J. Dexter, I. Waisberg, T. Ott, S. von Fellenberg, M. Bauböck, A. Jimenez-Rosales, and R. Genzel, Astrophys. J. 847, 120 (2017), arXiv:1708.06353 [astro-ph.SR] .
  * Buchholz  _et al._ [2009] R. M. Buchholz, R. Schödel, and A. Eckart, Astronomy & Astrophysics 499, 483–501 (2009).
  * Merritt [2010] D. Merritt, The Astrophysical Journal 718, 739–761 (2010).
  * Lu  _et al._ [2013] J. R. Lu, T. Do, A. M. Ghez, M. R. Morris, S. Yelda, and K. Matthews, Astrophys. J. 764, 155 (2013), arXiv:1301.0540 [astro-ph.SR] .
  * Bartko  _et al._ [2010] H. Bartko, F. Martins, S. Trippe, T. K. Fritz, R. Genzel, T. Ott, F. Eisenhauer, S. Gillessen, T. Paumard, T. Alexander, K. Dodds-Eden, O. Gerhard, Y. Levin, L. Mascetti, S. Nayakshin, H. B. Perets, G. Perrin, O. Pfuhl, M. J. Reid, D. Rouan, M. Zilka, and A. Sternberg, Astrophys. J. 708, 834 (2010), arXiv:0908.2177 [astro-ph.GA] .
  * Salpeter [1955] E. E. Salpeter, Astrophys. J. 121, 161 (1955).
  * Eisenhauer  _et al._ [2005] F. Eisenhauer _et al._ , Astrophys. J. 628, 246 (2005), arXiv:astro-ph/0502129 .
  * Lu  _et al._ [2009] J. R. Lu, A. M. Ghez, S. D. Hornstein, M. R. Morris, E. E. Becklin, and K. Matthews, Astrophys. J. 690, 1463 (2009), arXiv:0808.3818 [astro-ph] .
  * Hassani  _et al._ [2020] E. Hassani, R. Pazhouhesh, and H. Ebadi, Int. J. Mod. Phys. D 29, 2050052 (2020), arXiv:2003.12451 [astro-ph.GA] .
  * Dylan [1973] B. Dylan, “Forever young,” (1973), Asylum Records .
  * Peißker  _et al._ [2020] F. Peißker, A. Eckart, M. Zajaček, B. Ali, and M. Parsa, Astrophys. J. 899, 50 (2020), arXiv:2008.04764 [astro-ph.GA] .
  * von Fellenberg  _et al._ [2022] S. D. von Fellenberg _et al._ , Astrophys. J. Lett. 932, L6 (2022), arXiv:2205.07595 [astro-ph.GA] .
  * Hopman and Madigan [2011] C. Hopman and A. Madigan, in  _The Galactic Center: a Window to the Nuclear Environment of Disk Galaxies_, Astronomical Society of the Pacific Conference Series, Vol. 439, edited by M. R. Morris, Q. D. Wang, and F. Yuan (2011) p. 180, arXiv:1002.1220 [astro-ph.GA] .
  * Navarro  _et al._ [1996] J. F. Navarro, C. S. Frenk, and S. D. M. White, Astrophys. J. 462, 563 (1996), arXiv:astro-ph/9508025 .
  * Gondolo and Silk [1999] P. Gondolo and J. Silk, Phys. Rev. Lett. 83, 1719 (1999), arXiv:astro-ph/9906391 .
  * Bertone  _et al._ [2024] G. Bertone, A. R. A. C. Wierda, D. Gaggero, B. J. Kavanagh, M. Volonteri, and N. Yoshida, (2024), arXiv:2404.08731 [astro-ph.CO] .
  * Lacroix [2018] T. Lacroix, Astron. Astrophys. 619, A46 (2018), arXiv:1801.01308 [astro-ph.GA] .
  * Aprile  _et al._ [2019] E. Aprile _et al._ (XENON), Phys. Rev. Lett. 123, 241803 (2019), arXiv:1907.12771 [hep-ex] .
  * Aprile  _et al._ [2023] E. Aprile _et al._ (XENON), Phys. Rev. Lett. 131, 041003 (2023), arXiv:2303.14729 [hep-ex] .
  * Abdelhameed  _et al._ [2019] A. H. Abdelhameed _et al._ (CRESST), Phys. Rev. D 100, 102002 (2019), arXiv:1904.00498 [astro-ph.CO] .
  * Aalbers  _et al._ [2022] J. Aalbers _et al._ (LZ), (2022), arXiv:2207.03764 [hep-ex] .
  * Agnes  _et al._ [2018] P. Agnes _et al._ (DarkSide), Phys. Rev. Lett. 121, 081307 (2018), arXiv:1802.06994 [astro-ph.HE] .
  * Paxton  _et al._ [2011] B. Paxton, L. Bildsten, A. Dotter, F. Herwig, P. Lesaffre, and F. Timmes, ApJS 192, 3 (2011), arXiv:1009.1622 [astro-ph.SR] .
  * Paxton  _et al._ [2013] B. Paxton, M. Cantiello, P. Arras, L. Bildsten, E. F. Brown, A. Dotter, C. Mankovich, M. H. Montgomery, D. Stello, F. X. Timmes, and R. Townsend, ApJS 208, 4 (2013), arXiv:1301.0319 [astro-ph.SR] .
  * Paxton  _et al._ [2015] B. Paxton, P. Marchant, J. Schwab, E. B. Bauer, L. Bildsten, M. Cantiello, L. Dessart, R. Farmer, H. Hu, N. Langer, R. H. D. Townsend, D. M. Townsley, and F. X. Timmes, ApJS 220, 15 (2015), arXiv:1506.03146 [astro-ph.SR] .
  * Paxton  _et al._ [2018] B. Paxton, J. Schwab, E. B. Bauer, L. Bildsten, S. Blinnikov, P. Duffell, R. Farmer, J. A. Goldberg, P. Marchant, E. Sorokina, A. Thoul, R. H. D. Townsend, and F. X. Timmes, ApJS 234, 34 (2018), arXiv:1710.08424 [astro-ph.SR] .
  * Paxton  _et al._ [2019] B. Paxton, R. Smolec, J. Schwab, A. Gautschy, L. Bildsten, M. Cantiello, A. Dotter, R. Farmer, J. A. Goldberg, A. S. Jermyn, S. M. Kanbur, P. Marchant, A. Thoul, R. H. D. Townsend, W. M. Wolf, M. Zhang, and F. X. Timmes, ApJS 243, 10 (2019), arXiv:1903.01426 [astro-ph.SR] .
  * Jermyn  _et al._ [2023] A. S. Jermyn, E. B. Bauer, J. Schwab, R. Farmer, W. H. Ball, E. P. Bellinger, A. Dotter, M. Joyce, P. Marchant, J. S. G. Mombarg, W. M. Wolf, T. L. Sunny Wong, G. C. Cinquegrana, E. Farrell, R. Smolec, A. Thoul, M. Cantiello, F. Herwig, O. Toloza, L. Bildsten, R. H. D. Townsend, and F. X. Timmes, ApJS 265, 15 (2023), arXiv:2208.03651 [astro-ph.SR] .
  * Leane and Smirnov [2023] R. K. Leane and J. Smirnov, JCAP 12, 040 (2023), arXiv:2309.00669 [hep-ph] .
  * Witzel  _et al._ [2017] G. Witzel, B. N. Sitarski, A. M. Ghez, M. R. Morris, A. Hees, T. Do, J. R. Lu, S. Naoz, A. Boehle, G. Martinez, S. Chappell, R. Schödel, L. Meyer, S. Yelda, E. E. Becklin, and K. Matthews, Astrophys. J. 847, 80 (2017), arXiv:1707.02301 [astro-ph.GA] .
  * Ciurlo  _et al._ [2020] A. Ciurlo, R. D. Campbell, M. R. Morris, T. Do, A. M. Ghez, A. Hees, B. N. Sitarski, K. Kosmo O’Neil, D. S. Chu, G. D. Martinez, S. Naoz, and A. P. Stephan, Nature (London) 577, 337 (2020), arXiv:2001.08325 [astro-ph.GA] .
  * Do  _et al._ [2013] T. Do, J. R. Lu, A. M. Ghez, M. R. Morris, S. Yelda, G. D. Martinez, S. A. Wright, and K. Matthews, Astrophys. J. 764, 154 (2013), arXiv:1301.0539 [astro-ph.SR] .


201059-70Nancy, France 59

V. Arvind Srikanth Srinivasan

# The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

V. Arvind  and  S. Srinivasan  The Institute of Mathematical Sciences,
C.I.T. Campus, Chennai 600 113, India<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Using $\varepsilon$-bias spaces over $\mathbb{F}_{2}$, we show that the Remote
Point Problem (RPP), introduced by Alon et al [APY09], has an $\mbox{\rm
NC}^{2}$ algorithm (achieving the same parameters as [APY09]). We study a
generalization of the Remote Point Problem to groups: we replace
$\mathbb{F}_{2}^{n}$ by $\mathcal{G}^{n}$ for an arbitrary fixed group
$\mathcal{G}$. When $\mathcal{G}$ is Abelian we give an $\mbox{\rm NC}^{2}$
algorithm for RPP, again using $\varepsilon$-bias spaces. For nonabelian
$\mathcal{G}$, we give a deterministic polynomial-time algorithm for RPP. We
also show the connection to construction of expanding generator sets for the
group $\mathcal{G}^{n}$. All our algorithms for the RPP achieve essentially
the same parameters as [APY09].

###### Key words and phrases:

Small Bias Spaces, Expander Graphs, Cayley Graphs, Remote Point Problem.

###### 1991 Mathematics Subject Classification:

Algorithms and Complexity Theory

##  1\. Introduction

Valiant, in his celebrated work [V77] on circuit lower bounds for computing
linear transformations $A:\mathbb{F}^{n}\longrightarrow\mathbb{F}^{m}$ for a
field $\mathbb{F}$, initiated the study of rigid matrices. If explicit rigid
matrices of certain parameters can be constructed it would result in
superlinear lower bounds for logarithmic depth linear circuits over
$\mathbb{F}$. This problem and the construction of such rigid matrices has
remained elusive for over three decades.

Alon, Panigrahy and Yekhanin [APY09] recently proposed a problem that appears
to be of intermediate difficulty. Given a subspace $L$ of $\mathbb{F}_{2}^{n}$
by its basis and a number $r\in[n]$ as input, the problem is to compute in
deterministic polynomial time a point $v\in\mathbb{F}_{2}^{n}$ such that
$\Delta(u,v)\geq r$ for all $u\in L$, where $\Delta(u,v)$ is the Hamming
distance. They call this the _Remote Point Problem_. The point $v$ is said to
be $r$-far from the subspace $L$.

Alon et al [APY09] give a nice polynomial time-bounded (in $n$) algorithm for
computing a $v\in\mathbb{F}_{2}^{n}$ that is $c\log n$-far from a given
subspace $L$ of dimension $n/2$ and $c$ is a fixed constant. For $L$ such that
$\dim(L)=k<n/2$ they give a polynomial-time algorithm for computing a point
$v\in\mathbb{F}_{2}^{n}$ that is $\frac{cn\log k}{k}$-far from $L$.

#### Results of this paper

In [AS09a] we recently investigated the problem of proving circuit lower
bounds in the presence of help functions. Specifically, one of the problems we
consider is proving lower bounds for constant-depth Boolean circuits which can
take a given set of (arbitrary) help functions
$\\{h_{1},h_{2},\cdots,h_{m}\\}$ at the input level, where
$h_{i}:\\{0,1\\}^{n}\longrightarrow\\{0,1\\}$ for each $i$. Proving explicit
lower bounds for this model would allow us to separate EXP from the
polynomial-time many-one closure of nonuniform $\mbox{\rm AC}^{0}$. We show
that it suffices to find a polynomial-time solution to the Remote Point
Problem for parameters $k=2^{(\log\log n)^{c}}$ and $r=\frac{n}{2^{(\log\log
n)^{d}}}$ for all constants $c$ and $d$. Unfortunately, the parameters of the
Alon et al algorithm are inadequate for our application.

However, motivated by this connection, in the present paper we carry out a
more detailed study of the Remote Point Problem as an algorithmic question. We
briefly summarize our results.

1. The first question we address is whether we can give a deterministic parallel (i.e. NC) algorithm for the problem — Alon et al’s algorithm is inherently sequential as it is based on the method of conditional probabilities and pessimistic estimators.

It turns out an element of an $\varepsilon$-bias space for suitably chosen
$\varepsilon$ is a solution to the Remote Point Problem which gives us an NC
algorithm quite easily.

2. Since the RPP for $\mathbb{F}_{2}^{n}$ can be solved using small bias spaces, it naturally leads us to address the problem in a more general group-theoretic setting.

In the generalization we study we will replace $\mathbb{F}_{2}$ with an
arbitrary fixed finite group $\mathcal{G}$ such that $|\mathcal{G}|\geq 2$.
Hence we will have the $n$-fold product group $\mathcal{G}^{n}$ instead of the
vector space $\mathbb{F}_{2}^{n}$.

Given elements $x=(x_{1},x_{2},\ldots,x_{n}),y=(y_{1},y_{2},\ldots,y_{n})$ of
$\mathcal{G}^{n}$, let $\Delta(x,y)=|\\{i\mid x_{i}\neq y_{i}\\}|$. I.e.
$\Delta(x,y)$ is the _Hamming distance_ between $x$ and $y$. Furthermore, for
$S\subseteq\mathcal{G}^{n}$, let $\Delta(x,S)$ denote $\min_{y\in
S}\Delta(x,y)$.

We now define the _Remote Point Problem (RPP) over a finite group
$\mathcal{G}$_. The input is a subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$,
where $\mathcal{H}$ is given by a generating set, and a number $r\in[n]$. The
problem is to compute in deterministic polynomial (in $n$) time an element
$x\in\mathcal{G}^{n}$ such that $\Delta(x,H)>r$. The results we show in this
general setting are the following.

  * (a)

The Remote Point Problem over any _Abelian group_ $\mathcal{G}$ has an
$\mbox{\rm NC}^{2}$ algorithm for $r=O(\frac{n\log k}{k})$ and $k\leq n/2$,
where $k=\log_{|\mathcal{G}|}|\mathcal{H}|$.

  * (b)

Over an arbitrary group $\mathcal{G}$ the Remote point problem has a
polynomial-time algorithm for $r=O(\frac{n\log k}{k})$ and $k\leq n/2$, where
$k=\log_{|\mathcal{G}|}|\mathcal{H}|$.

The parallel algorithm stated in part(a) above is based on $\varepsilon$-bias
space constructions for finite Abelian groups described in Azar et al [AMN98].
The sequential algorithm stated in part(b) above is a group-theoretic
generalization of the Alon et al algorithm for $\mathbb{F}_{2}^{n}$ [APY09].

Due to lack of space, some proofs have been omitted. They may be found in the
full version which has been published as an ECCC report [AS09b].

##  2\. Preliminaries

Fix a finite group $\mathcal{G}$ such that $|\mathcal{G}|\geq 2$. Given any
$x\in\mathcal{G}^{n}$, let $wt(x)$ denote the number of coordinates $i$ such
that $x_{i}\neq 1$, where $1$ is the identity of the group $\mathcal{G}$. By
$B(r)$, we will refer to the set of $x\in\mathcal{G}^{n}$ such that $wt(x)\leq
r$. Given a subset $S$ of $\mathcal{G}^{n}$, $B(S,r)$ will denote the set
$S\cdot B(r)=\left\\{sx\>\middle|\>s\in S,x\in B(r)\right\\}$. Clearly, for
any $S\subseteq\mathcal{G}^{n}$ and any $x\in\mathcal{G}^{n}$, $x\in B(S,r)$
if and only if $\Delta(x,S)\leq r$. We say that $x$ is _$r$ -close_ to $S$ if
$x\in B(S,r)$ and _$r$ -far_ from $S$ if $x\notin B(S,r)$.

The _Remote Point Problem (RPP) over $\mathcal{G}$_ is defined to be the
following algorithmic problem:

  * INPUT: A subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$ (given by its generators) and an $r\in\mathbb{N}$.

  * OUTPUT: An $x\in\mathcal{G}^{n}$ such that $x\notin B(\mathcal{H},r)$.

Clearly, there are inputs to the above problem where no solution can be found.
But the input instances of the kind that we will study will clearly have a
solution (in fact, a random point of $\mathcal{G}^{n}$ will be a solution with
high probability).

Given a subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$, denote by
$\delta(\mathcal{H})$ the quantity $\log_{|\mathcal{G}|}|\mathcal{H}|$. We
will call $\delta(\mathcal{H})$ the _dimension of $\mathcal{H}$ in
$\mathcal{G}^{n}$_.

We say that the RPP over $\mathcal{G}$ has a $(k(n),r(n))$-algorithm if there
is an efficient algorithm that solves the Remote Point Problem when given as
input a subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$ of dimension at most
$k(n)$ and an $r$ that is bounded by $r(n)$. (Here, ‘efficient’ can correspond
to polynomial time or some smaller complexity class.)

A simple counting argument shows that there is a valid solution to the RPP
over $\mathcal{G}$ on inputs $(\mathcal{H},r)$ where
$\delta(\mathcal{H})+r\leq n(1-\frac{H(r/n)}{\log|G|}-\varepsilon)$, for any
fixed $\varepsilon>0$ (where $H(\cdot)$ denotes the binary entropy function).
However, the best known deterministic solution to the RPP – from [APY09] – is
a polynomial time $(k,\frac{cn\log k}{k})$-algorithm which works over
$\mathbb{F}_{2}^{n}$ (i.e, the group $\mathcal{G}$ involved is the additive
group of the field $\mathbb{F}_{2}$).

###  2.1. Some Group-Theoretic Algorithms

We introduce basic definitions and review some group-theoretic algorithms. Let
$\mathrm{Sym}(\Omega)$ denote the group of all permutations on a finite set
$\Omega$ of size $m$. In this section we use $G,H$ etc. to denote _permutation
groups on $\Omega$_, which are simply subgroups of $\mathrm{Sym}(\Omega)$.

Let $G$ be a subgroup of $\mathrm{Sym}(\Omega)$. For a subset
$\Delta\subseteq\Omega$ denote by $G_{\\{\Delta\\}}$ the _point-wise
stabilizer_ of $\Delta$. I.e $G_{\\{\Delta\\}}$ is the subgroup consisting of
exactly those elements of $G$ that fix each element of $\Delta$.

######  Theorem 2.1 (Schreier-Sims).

[Lu93]

  1. (1)

If a subgroup $G$ of $\mathrm{Sym}(\Omega)$ is given by a generating set as
input along with the subset $\Delta$ there is a polynomial-time (sequential)
algorithm for computing a generator set for $G_{\\{\Delta\\}}$.

  2. (2)

If a subgroup $G$ of $\mathrm{Sym}(\Omega)$ is given by a generating set as
input, then there is a polynomial time algorithm for computing $|G|$.

  3. (3)

Given as input a permutation $\sigma\in\mathrm{Sym}(\Omega)$ and a generator
set for a subgroup $G$ of $\mathrm{Sym}(\Omega)$, we can test in deterministic
polynomial time if $\sigma$ is an element of $G$.

We are also interested in a special case of this problem which we now define.
A subset $\Gamma\subseteq\Omega$ is an _orbit_ of $G$ if
$\Gamma=\left\\{\sigma(i)\>\middle|\>\sigma\in G\right\\}$ for some
$i\in\Omega$. Any subgroup $G$ of $\mathrm{Sym}(\Omega)$ partitions $\Omega$
into orbits (called $G$-orbits).

For a constant $b>0$, a subgroup $G$ of $\mathrm{Sym}(\Omega)$ is defined to
be a _$b$ -bounded permutation group_ if every $G$-orbit is of size at most
$b$.

In [MC87], McKenzie and Cook studied the parallel complexity of _Abelian_
permutation group problems. Specifically, they gave an $\mbox{\rm NC}^{3}$
algorithm for testing membership in an Abelian permutation group given by a
generator set and for computing the order of an Abelian permutation group.
When restricted to $b$-bounded Abelian permutation groups, the algorithms of
[MC87] for these problems are actually $\mbox{\rm NC}^{2}$ algorithms. We
formally state their result and derive a consequence.

######  Theorem 2.2 ([MC87]).

There is an $\mbox{\rm NC}^{2}$ algorithm for membership testing in a
$b$-bounded Abelian permutation group $G$ given by a generator set.

We now consider problems over $\mathcal{G}^{n}$, for a fixed finite group
$\mathcal{G}$. We know from basic group theory that every group $\mathcal{G}$
is a permutation group acting on itself. I.e. every $\mathcal{G}$ can be seen
as a subgroup of $\mathrm{Sym}(\mathcal{G})$, where $\mathcal{G}$ acts on
itself by left (or right) multiplication. Therefore, $\mathcal{G}^{n}$ can be
easily seen as a permutation group on the set $\Omega=\mathcal{G}\times[n]$
and hence, $\mathcal{G}^{n}$ can be considered a subgroup of
$\mathrm{Sym}(\Omega)$. Furthermore, notice that each subset
$\mathcal{G}\times\\{i\\}$ is an orbit of this group $\mathcal{G}^{n}$. Hence,
$\mathcal{G}^{n}$ is a $b$-bounded permutation group contained in
$\mathrm{Sym}(\Omega)$, where $b=|\mathcal{G}|$. Finally, if $\mathcal{G}$ is
an Abelian group, then so is this subgroup of $\mathrm{Sym}(\Omega)$. We have
the following lemma as an easy consequence of Theorem 2.2.

######  Lemma 2.3.

Let $\mathcal{G}$ be Abelian. There is an $\mbox{\rm NC}^{2}$ algorithm that
takes as input a generator set for some subgroup $\mathcal{H}$ of
$\mathcal{G}^{n}$ and an $x\in\mathcal{G}^{n}$, and accepts iff
$x\in\mathcal{H}$.

Given any $y=(y_{1},y_{2},\ldots,y_{i})\in\mathcal{G}^{i}$ with $1\leq i\leq
n$ and any $S\subseteq\mathcal{G}^{n}$, let $S_{y}$ denote the set
$\left\\{x\in S\>\middle|\>x_{j}=y_{j}\text{ for }1\leq j\leq i\right\\}$.

######  Lemma 2.4.

Let $\mathcal{G}$ be any fixed finite group. There is a polynomial time
algorithm that takes as input a subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$,
where $\mathcal{H}$ is given by generators, and a $y\in\mathcal{G}^{i}$ with
$1\leq i\leq n$, and computes $|\mathcal{H}_{y}|$.

######  Proof 2.5.

Let $\mathcal{K}=\\{(x_{1},x_{2},\ldots,x_{n})\in\mathcal{H}\mid
x_{1}=x_{2}=\cdots=x_{i}=1\\}$, where $1$ denotes the identity element of
$\mathcal{G}$. Clearly, $\mathcal{K}$ is a subgroup of $\mathcal{H}$. The set
$\mathcal{H}_{y}$, if nonempty, is simply a coset of $\mathcal{K}$ and thus,
we have $|\mathcal{H}_{y}|=|\mathcal{K}|$. To check if $\mathcal{H}_{y}$ is
nonempty, we consider the map
$\pi_{i}:\mathcal{G}^{n}\rightarrow\mathcal{G}^{i}$ that projects its input
onto its first $i$ coordinates; note that $\mathcal{H}_{y}$ is nonempty iff
the subgroup $\pi_{i}(\mathcal{H})$ contains $y$, which can be checked in
polynomial time by point ($3$) of Theorem 2.1 (here, we are identifying
$\mathcal{G}^{n}$ with a subgroup of $\mathrm{Sym}(\mathcal{G}\times[n])$ as
above). If $y\notin\pi_{i}(\mathcal{H})$, the algorithm outputs $0$.
Otherwise, we have $|\mathcal{H}_{y}|=|\mathcal{K}|$ and it suffices to
compute $|\mathcal{K}|$. But $\mathcal{K}$ is simply the point-wise stabilizer
of the set $\mathcal{G}\times[i]$ in $\mathcal{H}$, and hence $|\mathcal{K}|$
can be computed in polynomial time by points ($1$) and ($2$) of Theorem 2.1.

##  3\. Expanding Cayley Graphs and the Remote Point Problem

Fix a group $\mathcal{G}$ such that $|\mathcal{G}|\geq 2$, and consider an
instance of the RPP over $\mathcal{G}$. The main idea that we develop in this
section is that if we have a (symmetric) expanding generator set $S$ for the
group $\mathcal{G}^{n}$ with appropriate expansion parameters then for a
subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$ such that $\delta(\mathcal{H})\leq
k$ some element of $S$ will be $r$-far from $H$, for suitable $k$ and $r$.

We review some definitions related to expander graphs (e.g. see the survey of
Hoory, Linial, and Wigderson [HLW06]). An undirected multigraph $G=(V,E)$ is
an $(n,d,\alpha)$-graph for $n,d\in\mathbb{N}$ and $\alpha>0$ if $|V|=n$, the
degree of each vertex is $d$, and the second largest value $\lambda(G)$ from
among the absolute values of eigenvalues of $A(G)$ – the adjacency matrix of
the graph $G$ – is bounded by $\alpha d$.

A _random walk_ of length $t\in\mathbb{N}$ on an $(n,d,\alpha)$-graph
$G=(V,E)$ is the output of the following random process: a vertex $v_{0}\in V$
of picked uniformly at random, and for $0\leq i<t$, if $v_{i}$ has been
picked, then $v_{i+1}$ is obtained by selecting a neighbour $v_{i+1}$
uniformly at random (i.e a random edge out of $v_{i}$ is picked, and $v_{i+1}$
is chosen to be the other endpoint of the edge); the output of the process is
$(v_{0},v_{1},\ldots,v_{t})$. We now state an important result regarding
random walks on expanders (see [HLW06, Theorem 3.6] for details).

######  Lemma 3.1.

Let $G=(V,E)$ be an $(n,d,\alpha)$-graph and $B\subseteq V$ with $|B|\leq\beta
n$. Then, the probability that a random walk $(v_{0},v_{1},\ldots,v_{t})$ is
entirely contained inside $B$ (i.e, $v_{i}\in B$ for each $i$) is bounded by
$(\beta+\alpha)^{t}$.

Let $\mathcal{H}$ be a group and $S$ a _symmetric_ multiset of elements from
$\mathcal{H}$. I.e. there is a bijection of multisets $\varphi:S\rightarrow S$
such that $\varphi(s)=s^{-1}$ for each $s\in S$. We define the Cayley graph
$C(\mathcal{H},S)$ to be the (multi)graph $G$ with vertex set $\mathcal{H}$
and edges of the form $(x,xs)$ for each $x\in\mathcal{H}$ and each $s\in S$;
since $S$ is symmetric, we consider $C(\mathcal{H},S)$ to be an undirected
graph by identifying the edges $(x,xs)$ and $(xs,(xs)\varphi(s))$, for each
$x$ and $s$.

We now show a lemma that will help relate generators of expanding Cayley
graphs on $\mathcal{G}^{n}$ and the RPP over $\mathcal{G}$. In what follows,
let $S$ be a symmetric multiset of elements from $\mathcal{G}^{n}$; let $G$
denote the Cayley graph $C(\mathcal{G}^{n},S)$; and let $N,D$ denote
$|\mathcal{G}|^{n}$ and $|S|$ (counted with repetitions) respectively.

######  Lemma 3.2.

Assume $S$ as above is such that $G$ is an $(N,D,\alpha)$-graph, where
$\alpha\leq\frac{1}{n^{d}}$, for some fixed $d>0$. Then, given any subgroup
$\mathcal{H}$ of $\mathcal{G}^{n}$ such that $\delta(\mathcal{H})\leq 2n/3$,
we have $\frac{|S\cap\mathcal{H}|}{|S|}\leq\frac{1}{n^{d/2}}$ for large enough
$n$ (where the elements of $S\cap\mathcal{H}$ are counted with repetitions).

######  Proof 3.3.

Let $S^{\prime}=S\cap\mathcal{H}$ and let $\eta=|S^{\prime}|/|S|$. We want an
upper bound on $\eta$. Consider a random walk $(x_{0},x_{1},\ldots,x_{t})$ of
length $t$ on the graph $G$ (the exact value of $t$ will be fixed later). Let
$\mathcal{B}$ denote the following event: there is a $y\in\mathcal{G}^{n}$
such that all the vertices $x_{0},x_{1},\ldots,x_{t}$ are all contained in the
coset $y\mathcal{H}$ of $\mathcal{H}$. Let $p$ denote the probability that
$\mathcal{B}$ occurs.

We will first lower bound $p$. At each step of the random walk, a random
$s_{i}\in S$ is chosen and $x_{i+1}$ is set to $x_{i}s_{i}$. If these $s_{i}$
all happen to belong to $S^{\prime}$, then the cosets $x_{i}\mathcal{H}$ and
$x_{i+1}\mathcal{H}$ are the same for all $i$ and hence, the event
$\mathcal{B}$ does occur. Hence, $p\geq\eta^{t}$.

We now upper bound $p$. Fix any coset $y\mathcal{H}$ of the subgroup
$\mathcal{H}$. Since the dimension of $\mathcal{H}$ in $\mathcal{G}^{n}$ is
bounded by $2n/3$, we have
$|y\mathcal{H}|=|\mathcal{H}|\leq|\mathcal{G}|^{2n/3}\leq
2^{-n/3}|\mathcal{G}^{n}|$. That is, the coset $y\mathcal{H}$ is a very small
subset of $\mathcal{G}^{n}$. Applying Lemma 3.1, we see that the probability
that the random walk $(x_{0},x_{1},\ldots,x_{t})$ is completely contained
inside this coset is bounded by
$(2^{-n/3}+n^{-d})^{t}\leq\frac{2^{t}}{n^{dt}}$, for large enough $n$. As the
total number of cosets of $\mathcal{H}$ is bounded by $|\mathcal{G}|^{n}$, an
application of the union bound tells us that $p$ is upper bounded by
$|\mathcal{G}|^{n}\frac{2^{t}}{n^{dt}}\leq\frac{|\mathcal{G}|^{n+t}}{n^{dt}}$.
Setting $t=\frac{2n}{d\log_{|G|}n-2}$ we see that $p$ is at most
$\frac{1}{n^{dt/2}}$.

Putting the upper and lower bounds together, we see that
$\eta^{t}\leq\frac{1}{n^{dt/2}}$ and hence, $\eta\leq\frac{1}{n^{d/2}}$. This
completes the proof.

We follow the structure of the algorithm for the RPP over $\mathbb{F}_{2}$ in
[APY09]. We first describe their $(n/2,c\log n)$-algorithm for the RPP,
followed by our own algorithm. We then describe how they extend this algorithm
to a $(k,\frac{cn\log k}{k})$-algorithm for any $k\leq n/2$; the same
procedure works for our algorithm also.

The $(n/2,c\log n)$-algorithm proceeds as follows. On an input instance
consisting of a subgroup $V$ (which is a subspace of $\mathbb{F}_{2}^{n}$) of
dimension at most $n/2$ and an $r\leq c\log n$,

  1. (1)

The algorithm first computes a collection of $m=n^{O(c)}$ subspaces
$V_{1},V_{2},\ldots,V_{m}$, each of dimension at most $2n/3$ such that
$B(V,c\log n)\subseteq\bigcup_{i=1}^{m}V_{i}$.

  2. (2)

The algorithm then finds an $x\in\mathbb{F}_{2}^{n}$ such that
$x\notin\bigcup_{i}V_{i}$. (This is done using a method similar to the method
of pessimistic estimators introduced by Raghavan [Rag88].)

Our algorithm will proceed exactly as the above algorithm in the first step.
The second step of our algorithm will be different (assuming that the group
$\mathcal{G}$ is Abelian). We first state Step 1 of the algorithm of [APY09]
in greater generality:

######  Lemma 3.4.

Let $\mathcal{G}$ be any fixed finite group with $|\mathcal{G}|\geq 2$. For
any constant $c>0$ and large enough $n$, the following holds. Given any
subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$ such that
$\delta(\mathcal{H})\leq\frac{n}{2}$, there is a collection of $m\leq n^{10c}$
subgroups $\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{m}$ such that
$B(\mathcal{H},c\log n)\subseteq\bigcup_{i=1}^{m}\mathcal{H}_{i}$, and
$\delta(\mathcal{H}_{i})\leq 2n/3$ for each $i$. Moreover, there is a logspace
algorithm that, when given as input $\mathcal{H}$ as a set of generators,
produces generators for the subgroups
$\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{m}$.

######  Proof 3.5.

The proof follows exactly as in [APY09]. We reproduce it here for completeness
and to analyze the complexity of the procedure.

Let $1$ denote the identity element of $\mathcal{G}$. For each
$S\subseteq[n]$, let $\mathcal{G}^{n}(S)$ denote the subgroup of
$\mathcal{G}^{n}$ consisting of those $x$ such that $x_{i}=1$ for each
$i\notin S$. Note that $\delta(\mathcal{G}^{n}(S))=|S|$. Also note that for
each $S\subseteq[n]$, the group $\mathcal{G}^{n}(S)$ is a normal subgroup; in
particular, this implies that the set $\mathcal{K}\cdot\mathcal{G}^{n}(S)$ is
a subgroup of $\mathcal{G}^{n}$ whenever $\mathcal{K}$ is a subgroup of
$\mathcal{G}^{n}$.

Partition the set $[n]$ into $\ell\leq 10c\log n$ sets of size at most
$\lceil\frac{n}{10c\log n}\rceil$ each – we will call these sets
$S_{1},S_{2},\ldots,S_{\ell}$. For each $A\subseteq[\ell]$ of size $\lceil
c\log n\rceil$, let $\mathcal{K}_{A}$ denote the subgroup
$\mathcal{G}^{n}(\bigcup_{i\in A}S_{i})$. Note that the number of such
subgroups is at most $2^{\ell}\leq n^{10c}$. Also, for each $A$ as above,
$\delta(\mathcal{K}_{A})=|\bigcup_{i\in A}S_{i}|\leq\left(\frac{n}{10c\log
n}+1\right)(c\log n+1)<\frac{n}{9}$, for large enough $n$.

Consider any $x\in B(c\log n)$ (i.e, an element $x$ of $\mathcal{G}^{n}$ s.t
$wt(x)\leq c\log n$). We know that $x\in\mathcal{G}^{n}(S)$ for some $S$ of
size at most $c\log n$. Hence, it can be seen that
$x\in\mathcal{G}^{n}(\bigcup_{i\in A}S_{i})$ for some $A$ of size $\lceil
c\log n\rceil$; this shows that $B(c\log
n)\subseteq\bigcup_{A}\mathcal{K}_{A}$. Therefore, we see that
$B(\mathcal{H},c\log n)=\mathcal{H}B(c\log
n)\subseteq\bigcup_{A}\mathcal{H}\mathcal{K}_{A}$.

For each $A\subseteq[\ell]$ of size $\lceil c\log n\rceil$, let
$\mathcal{H}_{A}$ denote the subgroup $\mathcal{H}\mathcal{K}_{A}$ (note that
this is indeed a subgroup, since $\mathcal{K}_{A}$ is a normal subgroup).
Moreover, the cardinality of this subgroup is bounded by
$|\mathcal{H}|\cdot|\mathcal{K}_{A}|\leq|\mathcal{G}|^{n/2}|\mathcal{G}|^{n/9}<|\mathcal{G}|^{2n/3}$;
hence, $\delta(\mathcal{H}_{A})\leq 2n/3$. Thus, the collection of subgroups
$\\{\mathcal{H}_{A}\\}_{A}$ satisfies all the properties mentioned in the
statement of the lemma. That a set of generators for this subgroup can be
computed in deterministic logspace – for some suitable choice of
$S_{1},S_{2},\ldots,S_{\ell}$ – is a routine check from the definition of the
subgroups $\\{\mathcal{K}_{A}\\}_{A}$. This completes the proof of the lemma.

Using Lemma 3.4, we are able to efficiently “cover” $B(\mathcal{H},c\log n)$
for any small subgroup $\mathcal{H}$ of $\mathcal{G}^{n}$ by a union of small
subgroups. Therefore, to find a point that is $c\log n$-far from
$\mathcal{H}$, it suffices to find a point $x\in\mathcal{G}^{n}$ not contained
in any of the covering subgroups. To do this, we note that if $S$ is a
multiset containing elements from $\mathcal{G}^{n}$ such that
$C(\mathcal{G}^{n},S)$ is a Cayley graph with good expansion, then $S$ must
contain such an element. This is formally stated below.

######  Lemma 3.6.

For any constant $c>0$ and large enough $n\in\mathbb{N}$, the following holds.
Let $S$ be any multiset of elements of $\mathcal{G}^{n}$ such that
$\lambda(C(\mathcal{G}^{n},S))<\frac{1}{n^{20c}}$. Then, for $m\leq n^{10c}$
and any collection $\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{m}$ of
subgroups such that $\delta(\mathcal{H}_{i})\leq 2n/3$ for each $i$, there is
some $s\in S$ such that $s\notin\bigcup_{i}\mathcal{H}_{i}$.

######  Proof 3.7.

The proof follows easily from Lemma 3.2. Given any $i\in[m]$, we know, from
Lemma 3.2, that $|S\cap\mathcal{H}_{i}|<\frac{|S|}{n^{10c}}$ (where the
elements of the multisets are counted with repetitions). Hence,
$|S\cap\bigcup_{i}\mathcal{H}_{i}|\leq\sum_{i}|S\cap\mathcal{H}_{i}|<\frac{m|S|}{n^{10c}}\leq|S|$.
Therefore, there must be some $s\in S$ such that
$s\notin\bigcup_{i}\mathcal{H}_{i}$.

Therefore, to find a point $x$ that is $c\log n$-far from the subspace
$\mathcal{H}$, it suffices to construct an $S$ such that
$C(\mathcal{G}^{n},S)$ is a sufficiently good expander, find the covering
subgroups $\mathcal{H}_{i}$ ($i\in[m[$), and then to find an $s\in S$ that
does not lie in any of the $\mathcal{H}_{i}$. We follow the above approach to
give an efficient parallel algorithm for the RPP in the case that
$\mathcal{G}$ is an Abelian group. For arbitrary groups, we show that the
method of [APY09] yields a polynomial time algorithm.

##  4\. Remote Point Problem for Abelian Groups

Fix an Abelian group $\mathcal{G}$. Recall that a _character_ $\chi$ of
$\mathcal{G}^{n}$ is a homomorphism from $\mathcal{G}^{n}$ to
$\mathbb{C}^{*}_{1}$, the multiplicative subgroup of the complex numbers of
absolute value $1$. For $\varepsilon>0$, a distribution $\mu$ over
$\mathcal{G}^{n}$ is said to be $\varepsilon$-biased if, given any non-trivial
character $\chi$ of $\mathcal{G}^{n}$,
$\left|\mathop{\textbf{E}}_{x\sim\mu}[\chi(x)]\right|\leq\varepsilon$.

A multiset $S$ consisting of elements from $\mathcal{G}^{n}$ is said to be an
_$\varepsilon$ -biased space in $\mathcal{G}^{n}$_ if the uniform distribution
over $S$ is an $\varepsilon$-biased distribution.

It can be checked that a multiset consisting of
$(\frac{n}{\varepsilon})^{O(1)}$ independent, uniformly random elements from
$\mathcal{G}^{n}$ form an $\varepsilon$-biased space with high probability.
Explicit $\varepsilon$-biased spaces were constructed for the group
$\mathbb{F}_{2}^{n}$ by Naor and Naor in [NN93]; further constructions were
given by Alon et al. in [AGHP92]. Explicit constructions of
$\varepsilon$-biased spaces in $\mathbb{Z}_{d}^{n}$ were given by Azar et al.
in [AMN98]. We observe that this last construction yields a construction for
all Abelian groups $\mathcal{G}^{n}$, when $\mathcal{G}$ is of constant size.
We first state the result of [AMN98] in a form that we will find suitable.

######  Theorem 4.1.

For any fixed $d$, there is an $\mbox{\rm NC}^{2}$ algorithm that does the
following. On input $n$ and $\varepsilon>0$ (both in unary), the algorithm
produces a symmetric multiset $S\subseteq\mathbb{Z}_{d}^{n}$ of size
$O((\frac{n}{\varepsilon})^{2})$ such that $S$ is an $\varepsilon$-biased
space in $\mathbb{Z}_{d}^{n}$.

######  Proof 4.2.

It is easy to see that the $\varepsilon$-biased space construction in [AMN98]
can be implemented in deterministic logspace (and hence in $\mbox{\rm
NC}^{2}$). If the space $S$ obtained is not symmetric, we can consider the
multiset that is the disjoint union of $S$ and $S^{-1}$, which is also easily
seen to be $\varepsilon$-biased.

######  Remark 4.3.

We note that the definition of small bias spaces in [AMN98] differs somewhat
from our own definition above. But it is easy to see that an
$\varepsilon$-bias space in $\mathbb{Z}_{d}^{n}$ in the sense of [AMN98] is a
$(d\varepsilon)$-bias space according to our definition above.

######  Remark 4.4.

In a recent paper, Meka and Zuckerman [MZ09] observe, as we do below, that the
construction of [AMN98] gives small bias spaces for any arbitrary Abelian
group $\mathcal{G}$. Nevertheless, we present our own proof of this fact,
since the small bias spaces that follow from our proof are of _smaller_ size.
Specifically, our proof shows how to explicitly construct sample spaces of
size $O\left(\frac{n^{2}}{\varepsilon^{2}}\right)$, whereas the relevant
result in [MZ09] only produces small bias spaces of size
$O\left((\frac{n}{\varepsilon})^{b}\right)$, where $b$ is some constant that
depends on $\mathcal{G}$ (and can be as large as $\Omega(\log|\mathcal{G}|)$).

######  Lemma 4.5.

For any fixed group $\mathcal{G}$, there is an $\mbox{\rm NC}^{2}$ algorithm
which, on input $n$ and $\varepsilon>0$ in unary, produces a symmetric
multiset $S\subseteq\mathcal{G}^{n}$ of size $O((\frac{n}{\varepsilon})^{2})$
such that $S$ is an $\varepsilon$-biased space in $\mathcal{G}^{n}$.

######  Proof 4.6.

By the Fundamental Theorem of finite Abelian groups,
$\mathcal{G}\cong\mathbb{Z}_{d_{1}}\oplus\mathbb{Z}_{d_{2}}\oplus\cdots\oplus\mathbb{Z}_{d_{k}}$,
for positive integers $d_{1},d_{2},\ldots,d_{k}$ such that $d_{1}\mid
d_{2}\mid\cdots\mid d_{k}$. Let $\mathcal{G}_{0}$ denote
$\mathbb{Z}_{d_{k}}^{k}$. Note that for any $s,t\in\mathbb{N}$,
$\mathbb{Z}_{s}\cong\mathbb{Z}_{st}/\mathbb{Z}_{t}$. Hence, we see that that
$\mathcal{G}\cong\mathcal{G}_{0}/\mathcal{H}$, where $\mathcal{H}$ is the
subgroup
$\mathbb{Z}_{e_{1}}\oplus\mathbb{Z}_{e_{2}}\oplus\cdots\oplus\mathbb{Z}_{e_{k}}$,
and $e_{i}=d_{k}/d_{i}$ for each $i\in[k]$. Therefore,
$\mathcal{G}^{n}\cong\mathcal{G}_{0}^{n}/\mathcal{H}^{n}$. Let
$\pi:\mathcal{G}_{0}^{n}\rightarrow\mathcal{G}^{n}$ be the natural onto
homomorphism with kernel $\mathcal{H}^{n}$. Note that $\pi$ is just the
projection map and can easily be computed in $\mbox{\rm NC}^{2}$.

Since $\mathcal{G}_{0}^{n}\cong\mathbb{Z}_{d_{k}}^{nk}$, by Theorem 4.1, there
is an $\mbox{\rm NC}^{2}$ algorithm that constructs a symmetric multiset
$S_{0}\subseteq\mathcal{G}_{0}^{n}$ of size
$O(\left(\frac{kn}{\varepsilon}\right)^{2})$ such that $S_{0}$ is an
$\varepsilon$-biased space in $\mathcal{G}_{0}^{n}$. We claim that the
multiset $S=\pi(S_{0})$ is a symmetric $\varepsilon$-biased space in
$\mathcal{G}^{n}$. To see this, consider any non-trivial character $\chi$ of
$\mathcal{G}^{n}$; note that $\chi_{0}=\chi\circ\pi$ is a non-trivial
character of $\mathcal{G}_{0}^{n}$. We have

$\left|\mathop{\textbf{E}}_{x\sim
S}[\chi(x)]\right|=\left|\mathop{\textbf{E}}_{x_{0}\sim
S_{0}}[\chi(\pi(x_{0}))]\right|=\left|\mathop{\textbf{E}}_{x_{0}\sim
S_{0}}[\chi_{0}(x)]\right|\leq\varepsilon$

where the first equality follows from the definition of $S$, and the last
inequality follows from the fact that $S_{0}$ is an $\varepsilon$-biased space
in $\mathcal{G}_{0}^{n}$. Since $\chi$ was an arbitrary non-trivial character
of $\mathcal{G}^{n}$, we have proved that $S$ is indeed an
$\varepsilon$-biased space in $\mathcal{G}^{n}$. It is easy to see that $S$ is
symmetric. Finally, note that $S$ can be computed in $\mbox{\rm NC}^{2}$. This
completes the proof.

Finally, we mention a well-known connection between small bias spaces in
$\mathcal{G}^{n}$ and Cayley graphs over $\mathcal{G}^{n}$ (e.g. see Alon and
Roichman [AR94]).

######  Lemma 4.7.

Given any symmetric multiset $S\subseteq\mathcal{G}^{n}$, the Cayley graph
$C(\mathcal{G}^{n},S)$ is an $(|\mathcal{G}|^{n},|S|,\alpha)$-graph iff $S$ is
an $\alpha$-biased space.

Lemmas 4.7 and 4.5 have the following easy consequence:

######  Lemma 4.8.

For any Abelian group $\mathcal{G}$, there is an $\mbox{\rm NC}^{2}$ algorithm
which, on unary inputs $n$ and $\alpha>0$, produces a symmetric multiset
$S\subseteq\mathcal{G}^{n}$ of size $O((\frac{n}{\alpha})^{2})$ such that
$C(\mathcal{G}^{n},S)$ is a $(|\mathcal{G}|^{n},|S|,\alpha)$-graph.

Putting the above statement together with the results of Section 3, we have
the following.

######  Theorem 4.9.

For any constant $c>0$, the RPP over $\mathcal{G}$ has an $\mbox{\rm NC}^{2}$
$(n/2,c\log n)$-algorithm.

######  Proof 4.10.

Let $\mathcal{H}$ denote the input subgroup. By Lemma 3.4, there is a logspace
(and hence $\mbox{\rm NC}^{2}$) algorithm that computes a collection of
$m=n^{O(c)}$ many subgroups
$\mathcal{H}_{1},\mathcal{H}_{2},\ldots,\mathcal{H}_{m}$ such that
$B(\mathcal{H},c\log n)\subseteq\bigcup_{i=1}^{m}\mathcal{H}_{i}$ and
$\delta(\mathcal{H}_{i})\leq 2n/3$ for each $i\in[m]$. Now, fix any multiset
$S\subseteq\mathcal{G}^{n}$ such that the Cayley graph $C(\mathcal{G}^{n},S)$
is a $(|\mathcal{G}|^{n},|S|,\alpha)$-graph, where
$\alpha=\frac{1}{2n^{20c}}$; by Lemma 4.8, such an $S$ can be constructed in
$\mbox{\rm NC}^{2}$. It follows from Lemma 3.6 that there is some $s\in S$
such that $s\notin\bigcup_{i=1}^{m}\mathcal{H}_{i}$. Finally, by Lemma 2.3,
there is an $\mbox{\rm NC}^{2}$ algorithm to test if each $s\in S$ belongs to
$\mathcal{H}_{i}$, for any $i\in[m]$. Hence, we can find out (in parallel)
exactly which $s\in S$ do not belong to any of the $\mathcal{H}_{i}$ and
output one of them. The output element $s$ is surely $c\log n$-far from
$\mathcal{H}$.

Let $\mathcal{G}$ be Abelian. We observe that a method of [APY09], coupled
with Theorem 4.9, yields an efficient $(k,\frac{cn\log k}{k})$-algorithm for
any constant $c>0$, and $k\leq n/2$.

######  Theorem 4.11.

Let $c>0$ be any constant. If $\mathcal{G}$ is an Abelian group, then the RPP
over $\mathcal{G}$ has an $\mbox{\rm NC}^{2}$ $(k,\frac{cn\log
k}{k})$-algorithm for any $k\leq n/2$.

######  Proof 4.12.

Given as input a subgroup $\mathcal{H}$ such that $\delta(\mathcal{H})=k\leq
n/2$, the algorithm partitions $[n]$ as $[n]=\bigcup_{i=1}^{m}T_{i}$, where
$2k\leq|T_{i}|<4k$ for each $i$; note that $m\geq n/4k$. Let $\mathcal{H}_{i}$
denote the subgroup obtained when $\mathcal{H}$ is projected onto the
coordinates in $T_{i}$. Since $\delta(\mathcal{H}_{i})\leq k\leq|T_{i}|/2$, we
can, by Theorem 4.9, efficiently find a point $x_{i}\in\mathcal{G}^{|T_{i}|}$
that is at least $4c\log k$-far from $\mathcal{H}_{i}$. Putting these $x_{i}$
together in the natural way, we obtain an $x\in\mathcal{G}^{n}$ that is
$\frac{cn\log k}{k}$-far from the subgroup $\mathcal{H}$.

Since $\mathcal{G}$ is Abelian, using the algorithm of Theorem 4.9, the
$x_{i}$ can all be computed in parallel in $\mbox{\rm NC}^{2}$. Hence, the
entire procedure can be performed in $\mbox{\rm NC}^{2}$.

##  5\. RPP over General Groups

Let $\mathcal{G}$ denote some fixed finite group. We can generalize the
polynomial-time algorithm of [APY09], described for $\mathbb{F}_{2}$, to
compute a point $x\in\mathcal{G}^{n}$ that is $c\log n$-far from a given input
subgroup $\mathcal{H}$ such that $\delta(\mathcal{H})\leq n/2$. We only state
this result below and refer the interested reader to the full version [AS09b]
for details.

######  Theorem 5.1.

For any constant $c>0$, the RPP over $\mathcal{G}$ has a polynomial time
$(n/2,c\log n)$-algorithm.

Analogous to Theorem 4.11, we have the following solution to RPP for general
groups.

######  Theorem 5.2.

Let $c>0$ be any constant. For any $\mathcal{G}$, the RPP over $\mathcal{G}$
has a polynomial time $(k,\frac{cn\log k}{k})$-algorithm for any $k\leq n/2$.

######  Proof 5.3.

The construction is exactly the same as in the proof of Theorem 4.11. The only
difference is that we will apply the algorithm of Theorem 5.1. In this case,
the $x_{i}$ can all be found in deterministic polynomial time. Hence, the
entire procedure gives us a polynomial-time algorithm.

##  6\. Limitations of expanding sets

In the previous sections, we have shown how generators for expanding Cayley
graphs on $\mathcal{G}^{n}$, where $\mathcal{G}$ is a fixed finite group, can
help solve the RPP over $\mathcal{G}$. In particular, we have the following
easy consequence of Lemmas 3.4 and 3.6.

######  Corollary 6.1.

For any constant $c>0$, large enough $n$, and any symmetric multiset
$S\subseteq\mathcal{G}^{n}$ such that
$\lambda(C(\mathcal{G}^{n},S))<\frac{1}{n^{20c}}$, the following holds. If
$\mathcal{H}$ is any subgroup of $\mathcal{G}^{n}$ such that
$\delta(\mathcal{H})\leq n/2$, there is some $s\in S$ such that $s\notin
B(\mathcal{H},c\log n)$.

It makes sense to ask if the parameters in Corollary 6.1 are far from optimal.
Is it true that any polynomial-sized symmetric multiset
$S\subseteq\mathcal{G}^{n}$ with good enough expansion properties is
$\omega(\log n)$-far from every subgroup of dimension at most $n/2$? We can
show that this is not true. Formally, we can prove:

######  Theorem 6.2.

For any constant $c>0$ and large enough $n$, there is a symmetric multiset
$S\subseteq\mathbb{F}_{2}^{n}$ such that
$\lambda(C(\mathbb{F}_{2}^{n},S))\leq\frac{1}{n^{c}}$ but there is a subspace
$L$ of dimension $n/2$ such that $S\subseteq B(L,20c\log n)$.

It is well known that for any family of $d$-regular multigraphs $G$
$\lambda(G)=\Omega(1/\sqrt{d})$ (see e.g. [HLW06, Theorem 5.3]). As a
consequence of this lower bound it follows for any fixed group $\mathcal{G}$
and any multiset $S\subseteq\mathcal{G}^{n}$ that
$\lambda(C(\mathcal{G},S))=\Omega(1/\sqrt{|S|})$. Hence, the above theorem
tells us that just the expansion properties of $C(\mathbb{F}_{2}^{n},S)$ for
any $\mathop{\mathrm{poly}}(n)$-sized $S$ are not sufficient to guarantee
$\omega(\log n)$-distance from every subspace of dimension $n/2$. The proof of
the above statement can be found in the full version [AS09b].

##  7\. Discussion

For the remote point problem over an Abelian group $\mathcal{G}$, we have
shown how expanding generating sets for Cayley graphs of $\mathcal{G}^{n}$ can
be used to obtain deterministic $\mbox{\rm NC}^{2}$ algorithms. A natural
question is whether we can obtain a similar algorithm for non-Abelian
$\mathcal{G}$. Note that Lemma 3.6 holds in the non-Abelian setting too.
Hence, in order to obtain an $\mbox{\rm NC}^{2}$-algorithm for the RPP over
arbitrary non-Abelian $\mathcal{G}$ along the lines of our algorithm for
Abelian groups, we need to be able to check (in $\mbox{\rm NC}^{2}$) for
membership in $\mathcal{G}^{n}$, and we need to be able to construct small
multisets $S$ of $\mathcal{G}^{n}$ such that $C(\mathcal{G}^{n},S)$ has
sufficiently good expansion properties. Luks’ work [Lu86] yields an $\mbox{\rm
NC}^{4}$ test for membership in $\mathcal{G}^{n}$ for arbitrary $\mathcal{G}$.
Building on that, there is also an $\mbox{\rm NC}^{2}$ membership test for
$\mathcal{G}^{n}$ [AKV05]. However, we are unable to compute a (good enough)
expanding generator set for the group $\mathcal{G}^{n}$ in deterministic NC or
even in deterministic polynomial time.

## Acknowledgements

We are grateful to Noga Alon and Sergey Yekhanin for interesting comments. In
particular, Alon pointed out to us that Lemma 3.2 has an alternative proof
using the expander mixing lemma. We thank the anonymous referees for their
comments and suggestions.

## References

  * [AGHP92] Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta.  Simple construction of almost k-wise independent random variables.  Random Struct. Algorithms, 3(3):289–304, 1992.
  * [AKV05] V. Arvind, Piyush P. Kurur, T. C. Vijayaraghavan.  Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy.  In IEEE Conference on Computational Complexity 2005: 13-27.
  * [APY09] Noga Alon, Rina Panigrahy, and Sergey Yekhanin.  Deterministic approximation algorithms for the nearest codeword problem.  In APPROX-RANDOM, pages 339–351, 2009.
  * [AR94] Noga Alon, Yuval Roichman.  Random Cayley Graphs and Expanders.  Random Structures and Algorithms, 5(2): 271-285 (1994).
  * [AS09a] V. Arvind and Srikanth Srinivasan.  Circuit Complexity, Help Functions and the Remote point problem.  manuscript.
  * [AS09b] V. Arvind and Srikanth Srinivasan.  The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets  ECCC Report TR09-105. Can be found at http://eccc.hpi-web.de/report/2009/105/
  * [AMN98] Yossi Azar, Rajeev Motwani, and Joseph Naor.  Approximating probability distributions using small sample spaces.  Combinatorica, 18(2):151–171, 1998.
  * [HLW06] Shlomo Hoory, Nathan Linial, and Avi Wigderson.  Expander graphs and their applications.  Bull. Amer. Math. Soc. (N.S), 43:439–561, 2006.
  * [Lu86] Eugene M. Luks.  Parallel algorithms for permutation groups and graph isomorphism.  In FOCS, pages 292–302, 1986.
  * [Lu93] Eugene M. Luks.  Permutation groups and polynomial time computation.  Groups and Computation I, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol 11, 139-174, 1993.
  * [MC87] Pierre McKenzie and Stephen Cook.  The parallel complexity of Abelian permutation group problems.  SIAM Journal on Computing, 16(5):880-909, 1987.
  * [MZ09] Raghu Meka and David Zuckerman.  Small-Bias Spaces for Group Products.  APPROX-RANDOM 2009: 658-672.
  * [NN93] Joseph Naor and Moni Naor.  Small-bias probability spaces: Efficient constructions and applications.  SIAM J. Comput., 22(4):838–856, 1993.
  * [Rag88] Prabhakar Raghavan.  Probabilistic construction of deterministic algorithms: Approximating packing integer programs.  Journal of Computer and System Sciences, 37(2):130 – 143, 1988.
  * [Rei08] Omer Reingold.  Undirected connectivity in log-space.  J. ACM, 55(4), 2008.
  * [V77] Leslie G. Valiant.  Graph-Theoretic Arguments in Low-Level Complexity.  Proceedings Mathematical Foundations of Computer Science, LNCS vol. 53: 162-176, Springer 1977.