Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > G:
A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

G
TR00-068 | 13th July 2000
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E. Schapire

#### Gambling in a rigged casino: The adversarial multi-armed bandit problem

In the multi-armed bandit problem, a gambler must decide which arm
of K non-identical slot machines to play in a sequence of trials
so as to maximize his reward.
This classical problem has received much attention because of the
simple model it provides of the trade-off between
exploration ... more >>>

TR15-149 | 8th September 2015

#### Gambling, Computational Information, and Encryption Security

We revisit the question, originally posed by Yao (1982), of whether encryption security may be characterized using computational information. Yao provided an affirmative answer, using a compression-based notion of computational information to give a characterization equivalent to the standard computational notion of semantic security. We give two other equivalent characterizations. ... more >>>

TR15-021 | 5th February 2015
Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

#### Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games

A black-white combinatorial game is a two-person game in which the pieces are colored either black or white. The players alternate moving or taking elements of a specific color designated to them before the game begins. A player loses the game if there is no legal move available for his ... more >>>

TR98-026 | 5th May 1998
Richard Beigel

#### Gaps in Bounded Query Hierarchies

<html>
Prior results show that most bounded query hierarchies cannot
contain finite gaps. For example, it is known that
<center>
P<sub>(<i>m</i>+1)-tt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup> implies P<sub>btt</sub><sup>SAT</sup> = P<sub><i>m</i>-tt</sub><sup>SAT</sup>
</center>
and for all sets <i>A</i>
<ul>
<li> FP<sub>(<i>m</i>+1)-tt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup> implies FP<sub>btt</sub><sup><i>A</i></sup> = FP<sub><i>m</i>-tt</sub><sup><i>A</i></sup>
</li>
<li> P<sub>(<i>m</i>+1)-T</sub><sup><i>A</i></sup> = P<sub><i>m</i>-T</sub><sup><i>A</i></sup> implies P<sub>bT</sub><sup><i>A</i></sup> = ... more >>>

TR17-067 | 21st April 2017
Benny Applebaum

#### Garbled Circuits as Randomized Encodings of Functions: a Primer

Yao's garbled circuit construction is a central cryptographic tool with numerous applications. In this tutorial, we study garbled circuits from a foundational point of view under the framework of \emph{randomized encoding} (RE) of functions. We review old and new constructions of REs, present some lower bounds, and describe some applications. ... more >>>

TR18-027 | 8th February 2018
Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

#### General Strong Polarization

Ar\i kan's exciting discovery of polar codes has provided an altogether new way to efficiently achieve Shannon capacity. Given a (constant-sized) invertible matrix $M$, a family of polar codes can be associated with this matrix and its ability to approach capacity follows from the $\textit{polarization}$ of an associated $[0,1]$-bounded martingale, ... more >>>

TR14-040 | 30th March 2014
Hamed Hatami, Pooya Hatami, Shachar Lovett

#### General systems of linear forms: equidistribution and true complexity

Revisions: 1

The densities of small linear structures (such as arithmetic progressions) in subsets of Abelian groups can be expressed as certain analytic averages involving linear forms. Higher-order Fourier analysis examines such averages by approximating the indicator function of a subset by a function of bounded number of polynomials. Then, to approximate ... more >>>

TR08-027 | 4th December 2007
Till Tantau

#### Generalizations of the Hartmanis-Immerman-Sewelson Theorem and Applications to Infinite Subsets of P-Selective Sets

The Hartmanis--Immerman--Sewelson theorem is the classical link between the exponential and the polynomial time realm. It states that NE = E if, and only if, every sparse set in NP lies in P. We establish similar links for classes other than sparse sets:

1. E = UE if, and only ... more >>>

TR05-142 | 1st December 2005

#### Generalized Compact Knapsacks are Collision Resistant

The generalized knapsack problem is the following: given $m$ random
elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$
where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002),
it was proved that for appropriate choices of $R$ ... more >>>

TR04-095 | 3rd November 2004
Daniele Micciancio

#### Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 ... more >>>

TR18-074 | 23rd April 2018
Daniel Kane, Shachar Lovett, Shay Moran

#### Generalized comparison trees for point-location problems

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$
can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear ... more >>>

TR97-061 | 12th November 1997
Eli Biham, Dan Boneh, Omer Reingold

#### Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

The Diffie-Hellman key-exchange protocol may naturally be
extended to k>2 parties. This gives rise to the generalized
Diffie-Hellman assumption (GDH-Assumption).
Naor and Reingold have recently shown an efficient construction
of pseudo-random functions and reduced the security of their
construction to the GDH-Assumption.
In this note, we ... more >>>

TR18-064 | 3rd April 2018
Markus Bläser, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov

#### Generalized Matrix Completion and Algebraic Natural Proofs

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual {ACM} {SIGACT} Symposium on Theory of Computing (STOC), pages {653--664}, 2017) and independently by Grochow, Kumar, Saks and Saraf~(CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich's famous barrier result (J. Comput. ... more >>>

TR13-103 | 24th July 2013
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

#### Generalized Wong sequences and their applications to Edmonds' problems

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix $M$ whose entries are homogeneous linear polynomials over the integers. Given a linear subspace $\mathcal{B}$ of the $n \times n$ matrices over some field $\mathbb{F}$, we consider ... more >>>

TR12-170 | 30th November 2012
Scott Aaronson, Travis Hance

#### Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>>

TR96-007 | 29th January 1996
Miklos Ajtai

#### Generating Hard Instances of Lattice Problems

We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three ... more >>>

TR13-185 | 24th December 2013
Fu Li, Iddo Tzameret

#### Generating Matrix Identities and Proof Complexity Lower Bounds

Revisions: 3

Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field $\mathbb{F}$ let $A$ be a non-commutative (associative) $\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$ of $d\times d$ matrices over $\mathbb{F}$). We say that a non-commutative ... more >>>

TR04-037 | 14th April 2004
Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

#### Generation Problems

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>

TR05-060 | 30th May 2005
Philippe Moser

#### Generic Density and Small Span Theorem

We refine the genericity concept of Ambos-Spies et al, by assigning a real number in $[0,1]$ to every generic set, called its generic density.
We construct sets of generic density any E-computable real in $[0,1]$.
We also introduce strong generic density, and show that it is related to packing ... more >>>

TR05-162 | 23rd December 2005
Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo

#### Generic yet Practical ZK Arguments from any Public-Coin HVZK

Revisions: 1

In this work, we present a generic yet practical transformation from any public-coin honest-verifier zero-knowledge (HVZK) protocols to normal zero-knowledge (ZK) arguments. By generic", we mean that the transformation is applicable to any public-coin HVZK protocol under any one-way function (OWF) admitting Sigma-protocols. By practical" we mean that the transformation ... more >>>

TR19-060 | 18th April 2019
Scott Aaronson, Guy Rothblum

#### Gentle Measurement of Quantum States and Differential Privacy

In differential privacy (DP), we want to query a database about $n$ users, in a way that "leaks at most $\varepsilon$ about any individual user," even conditioned on any outcome of the query. Meanwhile, in gentle measurement, we want to measure $n$ quantum states, in a way that "damages the ... more >>>

TR96-053 | 6th August 1996
Yosi Ben-Asher, Ilan Newman

#### Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

The architecture of 'mesh of buses' is an important model in parallel computing. Its main advantage is that the additional broadcast capability can be used to overcome the main disadvantage of the mesh, namely its relatively large diameter. We show that the addition of buses indeed accelerates routing times. Furthermore, ... more >>>

TR96-052 | 2nd October 1996
Martin Dietzfelbinger

#### Gossiping and Broadcasting versus Computing Functions in Networks

The fundamental assumption in the classical theory of
dissemination of information in interconnection networks
(gossiping and broadcasting) is that atomic pieces of information
are communicated. We show that, under suitable assumptions about
the way processors may communicate, computing an n-ary function
that has a "critical input" (e.g., ... more >>>

TR05-116 | 12th October 2005
Alex Samorodnitsky, Luca Trevisan

#### Gowers Uniformity, Influence of Variables, and PCPs

Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f)
of a function f: G -> \C, where G is a finite abelian group and \C are the
complex numbers. Roughly speaking, if a function has small Gowers uniformity
of dimension d, then it looks random'' on ... more >>>

TR12-050 | 25th April 2012
Avraham Ben-Aroya, Gil Cohen

Revisions: 3

A $(k,\epsilon)$-biased sample space is a distribution over $\{0,1\}^n$ that $\epsilon$-fools every nonempty linear test of size at most $k$. Since they were introduced by Naor and Naor [SIAM J. Computing, 1993], these sample spaces have become a central notion in theoretical computer science with a variety of applications.

When ... more >>>

TR15-162 | 9th October 2015
Eric Allender, Joshua Grochow, Cris Moore

#### Graph Isomorphism and Circuit Size

Revisions: 1

We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied ... more >>>

TR10-050 | 25th March 2010
Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

#### Graph Isomorphism for $K_{3,3}$-free and $K_5$-free graphs is in Log-space

Graph isomorphism is an important and widely studied computational problem, with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.
We extend this result of [DLN$^+$09] further
to the ... more >>>

TR02-037 | 21st May 2002
Vikraman Arvind, Piyush Kurur

#### Graph Isomorphism is in SPP

We show that Graph Isomorphism is in the complexity class
SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for
each $k\geq 2$). We derive this result as a corollary of a more
general result: we show that a {\em generic problem} $\FINDGROUP$ has
an $\FP^{\SPP}$ ... more >>>

TR99-033 | 19th August 1999
Vikraman Arvind, J. Köbler

#### Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

We show the following new lowness results for the probabilistic
class ZPP$^{\mbox{\rm NP}}$.

1. The class AM$\cap$coAM is low for ZPP$^{\mbox{\rm NP}}$.
As a consequence it follows that Graph Isomorphism and several
group-theoretic problems known to be in AM$\cap$coAM are low for
ZPP$^{\mbox{\rm ... more >>> TR10-117 | 22nd July 2010 Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner #### Graph Isomorphism is not AC^0 reducible to Group Isomorphism We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of unbounded fan-in with$O(\log\log n)$depth and$O(\log^2 n)$nondeterministic bits, ... more >>> TR15-032 | 21st February 2015 Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky #### Graph Isomorphism, Color Refinement, and Compactness Revisions: 2 Color refinement is a classical technique used to show that two given graphs$G$and$H$are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph$G$amenable to color refinement if the color-refinement procedure succeeds in distinguishing$G$from any non-isomorphic ... more >>> TR11-077 | 8th May 2011 Albert Atserias, Elitza Maneva #### Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics Two graphs with adjacency matrices$\mathbf{A}$and$\mathbf{B}$are isomorphic if there exists a permutation matrix$\mathbf{P}$for which the identity$\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$holds. Multiplying through by$\mathbf{P}$and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show ... more >>> TR98-075 | 9th December 1998 Adam Klivans, Dieter van Melkebeek #### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. We establish hardness versus randomness trade-offs for a broad class of randomized procedures. In particular, we create efficient nondeterministic simulations of bounded round Arthur-Merlin games using a language in exponential time that cannot be decided by polynomial size oracle circuits with access to satisfiability. We show that every language with ... more >>> TR06-116 | 19th July 2006 Amin Coja-Oghlan #### Graph partitioning via adaptive spectral techniques We study the use of spectral techniques for graph partitioning. Let G=(V,E) be a graph whose vertex set has a latent'' partition V_1,...,V_k. Moreover, consider a density matrix'' E=(E_vw)_{v,w in V} such that for v in V_i and w in V_j the entry E_{vw} is the fraction of all possible ... more >>> TR98-031 | 4th May 1998 Dimitris Fotakis, Paul Spirakis #### Graph Properties that Facilitate Travelling In this work, we study two special cases of the metric Travelling Salesman Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of TSP(1,2) and Graph TSP are essentially as hard to approximate as general instances of TSP(1,2). Next, we present an NC algorithm for TSP(1,2) that ... more >>> TR99-047 | 10th November 1999 Wolfgang Slany #### Graph Ramsey games We consider combinatorial avoidance and achievement games based on graph Ramsey theory: The players take turns in coloring still uncolored edges of a graph G, each player being assigned a distinct color, choosing one edge per move. In avoidance games, completing a monochromatic subgraph isomorphic to ... more >>> TR14-121 | 22nd September 2014 Sebastian Mueller #### Graph Structure and Parity Games We investigate the possible structural changes one can perform on a game graph without destroying the winning regions of the players playing a parity game on it. More precisely, given a game graph$(G,p)$for which we can efficiently compute winning regions, can we remove or add a vertex or ... more >>> TR11-032 | 11th March 2011 Fabian Wagner #### Graphs of Bounded Treewidth can be Canonized in AC$^1$In recent results the complexity of isomorphism testing on graphs of bounded treewidth is improved to TC$^1$[GV06] and further to LogCFL [DTW10]. The computation of canonical forms or a canonical labeling provides more information than isomorphism testing. Whether canonization is in NC or even TC$^1$was stated ... more >>> TR18-049 | 14th March 2018 Stasys Jukna, Hannes Seiwert #### Greedy can also beat pure dynamic programming Revisions: 1 Many dynamic programming algorithms are pure'' in that they only use min or max and addition operations in their recursion equations. The well known greedy algorithm of Kruskal solves the minimum weight spanning tree problem on$n$-vertex graphs using only$O(n^2\log n)$operations. We prove that any pure DP algorithm ... more >>> TR16-145 | 16th September 2016 Markus Bläser, Gorav Jindal, Anurag Pandey #### Greedy Strikes Again: A Deterministic PTAS for Commutative Rank of Matrix Spaces Revisions: 2 We consider the problem of commutative rank computation of a given matrix space,$\mathcal{B}\subseteq\mathbb{F}^{n\times n}$. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is$n$, subsumes problems such as testing perfect matching in graphs ... more >>> TR10-151 | 30th September 2010 Raghunath Tewari, Vinodchandran Variyam #### Green’s Theorem and Isolation in Planar Graphs We show a simple application of Green’s theorem from multivariable calculus to the isolation problem in planar graphs. In particular, we construct a skew-symmetric, polynomially bounded, edge weight function for a directed planar graph in logspace such that the weight of any simple cycle in the graph is non-zero with ... more >>> TR05-149 | 7th December 2005 Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy #### Grid Graph Reachability Problems Revisions: 1 We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since * reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and * reachability on certain classes of grid graphs gives ... more >>> TR14-073 | 14th May 2014 Shachar Lovett, Cris Moore, Alexander Russell #### Group representations that resist random sampling Revisions: 1 We show that there exists a family of groups$G_n$and nontrivial irreducible representations$\rho_n$such that, for any constant$t$, the average of$\rho_n$over$t$uniformly random elements$g_1, \ldots, g_t \in G_n$has operator norm$1$with probability approaching 1 as$n \rightarrow \infty\$. More quantitatively, we ... more >>>

ISSN 1433-8092 | Imprint