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

__
TR15-149
| 8th September 2015
__

Mohammad Hajiabadi, Bruce Kapron#### Gambling, Computational Information, and Encryption Security

__
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

__
TR98-026
| 5th May 1998
__

Richard Beigel#### Gaps in Bounded Query Hierarchies

__
TR17-067
| 21st April 2017
__

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

__
TR18-027
| 8th February 2018
__

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan#### General Strong Polarization

__
TR14-040
| 30th March 2014
__

Hamed Hatami, Pooya Hatami, Shachar Lovett#### General systems of linear forms: equidistribution and true complexity

Revisions: 1

__
TR08-027
| 4th December 2007
__

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

__
TR05-142
| 1st December 2005
__

Vadim Lyubashevsky, Daniele Micciancio#### Generalized Compact Knapsacks are Collision Resistant

__
TR04-095
| 3rd November 2004
__

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

__
TR97-061
| 12th November 1997
__

Eli Biham, Dan Boneh, Omer Reingold#### Generalized Diffie-Hellman Modulo a Composite is not Weaker than Factoring

__
TR13-103
| 24th July 2013
__

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha#### Generalized Wong sequences and their applications to Edmonds' problems

__
TR12-170
| 30th November 2012
__

Scott Aaronson, Travis Hance#### Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

__
TR96-007
| 29th January 1996
__

Miklos Ajtai#### Generating Hard Instances of Lattice Problems

Comments: 1

__
TR13-185
| 24th December 2013
__

Fu Li, Iddo Tzameret#### Generating Matrix Identities and Proof Complexity Lower Bounds

Revisions: 3

__
TR04-037
| 14th April 2004
__

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner#### Generation Problems

__
TR05-060
| 30th May 2005
__

Philippe Moser#### Generic Density and Small Span Theorem

__
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

__
TR96-053
| 6th August 1996
__

Yosi Ben-Asher, Ilan Newman#### Geometric Approach for Optimal Routing on Mesh with Buses

Revisions: 1

__
TR96-052
| 2nd October 1996
__

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

__
TR05-116
| 12th October 2005
__

Alex Samorodnitsky, Luca Trevisan#### Gowers Uniformity, Influence of Variables, and PCPs

__
TR12-050
| 25th April 2012
__

Avraham Ben-Aroya, Gil Cohen#### Gradual Small-Bias Sample Spaces

Revisions: 3

__
TR15-162
| 9th October 2015
__

Eric Allender, Joshua Grochow, Cris Moore#### Graph Isomorphism and Circuit Size

Revisions: 1

__
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

__
TR02-037
| 21st May 2002
__

Vikraman Arvind, Piyush Kurur#### Graph Isomorphism is in SPP

__
TR99-033
| 19th August 1999
__

Vikraman Arvind, J. Köbler#### Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

__
TR10-117
| 22nd July 2010
__

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner#### Graph Isomorphism is not AC^0 reducible to Group Isomorphism

__
TR15-032
| 21st February 2015
__

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky#### Graph Isomorphism, Color Refinement, and Compactness

Revisions: 2

__
TR11-077
| 8th May 2011
__

Albert Atserias, Elitza Maneva#### Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics

__
TR98-075
| 9th December 1998
__

Adam Klivans, Dieter van Melkebeek#### Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

__
TR06-116
| 19th July 2006
__

Amin Coja-Oghlan#### Graph partitioning via adaptive spectral techniques

__
TR98-031
| 4th May 1998
__

Dimitris Fotakis, Paul Spirakis#### Graph Properties that Facilitate Travelling

__
TR99-047
| 10th November 1999
__

Wolfgang Slany#### Graph Ramsey games

__
TR14-121
| 22nd September 2014
__

Sebastian Mueller#### Graph Structure and Parity Games

__
TR11-032
| 11th March 2011
__

Fabian Wagner#### Graphs of Bounded Treewidth can be Canonized in AC$^1$

__
TR18-049
| 14th March 2018
__

Stasys Jukna, Hannes Seiwert#### Greedy can also beat pure dynamic programming

__
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

__
TR10-151
| 30th September 2010
__

Raghunath Tewari, Vinodchandran Variyam#### Green’s Theorem and Isolation in Planar Graphs

__
TR05-149
| 7th December 2005
__

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy#### Grid Graph Reachability Problems

Revisions: 1

__
TR14-073
| 14th May 2014
__

Shachar Lovett, Cris Moore, Alexander Russell#### Group representations that resist random sampling

Revisions: 1

Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, Robert E. Schapire

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 >>>

Mohammad Hajiabadi, Bruce Kapron

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 >>>

Stephen A. Fenner, Daniel Grier, Jochen Messner, Luke Schaeffer, Thomas Thierauf

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 >>>

Richard Beigel

<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 >>>

Benny Applebaum

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 >>>

Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, Madhu Sudan

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 >>>

Hamed Hatami, Pooya Hatami, Shachar Lovett

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 >>>

Till Tantau

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 >>>

Vadim Lyubashevsky, Daniele Micciancio

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 >>>

Daniele Micciancio

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 >>>

Eli Biham, Dan Boneh, Omer Reingold

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 >>>

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

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 >>>

Scott Aaronson, Travis Hance

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 >>>

Miklos Ajtai

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 >>>

Fu Li, Iddo Tzameret

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 >>>

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

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 >>>

Philippe Moser

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 >>>

Yunlei Zhao, Jesper Buus Nielsen, Robert H. Deng, Feng Dengguo

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 >>>

Yosi Ben-Asher, Ilan Newman

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 >>>

Martin Dietzfelbinger

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 >>>

Alex Samorodnitsky, Luca Trevisan

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 >>>

Avraham Ben-Aroya, Gil Cohen

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 >>>

Eric Allender, Joshua Grochow, Cris Moore

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 >>>

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner

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 >>>

Vikraman Arvind, Piyush Kurur

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 >>>

Vikraman Arvind, J. Köbler

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 >>>

Arkadev Chattopadhyay, Jacobo Toran, Fabian Wagner

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 >>>

Vikraman Arvind, Johannes Köbler, Gaurav Rattan, Oleg Verbitsky

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 >>>

Albert Atserias, Elitza Maneva

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 >>>

Adam Klivans, Dieter van Melkebeek

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 >>>

Amin Coja-Oghlan

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 >>>

Dimitris Fotakis, Paul Spirakis

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 >>>

Wolfgang Slany

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 >>>

Sebastian Mueller

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 >>>

Fabian Wagner

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 >>>

Stasys Jukna, Hannes Seiwert

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 >>>

Markus Bläser, Gorav Jindal, Anurag Pandey

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 >>>

Raghunath Tewari, Vinodchandran Variyam

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 >>>

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

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 >>>

Shachar Lovett, Cris Moore, Alexander Russell

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 >>>