Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with machine learning:
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 >>>

TR07-088 | 7th September 2007
Elad Hazan, C. Seshadhri

Adaptive Algorithms for Online Decision Problems

Revisions: 1

We study the notion of learning in an oblivious changing environment. Existing online learning algorithms which minimize regret are shown to converge to the average of all locally optimal solutions. We propose a new performance metric, strengthening the standard metric of regret, to capture convergence to locally optimal solutions, and ... more >>>

TR08-053 | 27th March 2008
Stephen A. Fenner, William Gasarch, Brian Postow

The complexity of learning SUBSEQ(A)

Higman showed that if A is *any* language then SUBSEQ(A)
is regular, where SUBSEQ(A) is the language of all
subsequences of strings in A. (The result we attribute
to Higman is actually an easy consequence of his work.)
Let s_1, s_2, s_3, ... more >>>

ISSN 1433-8092 | Imprint