Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Brendan Juba:

TR15-030 | 6th March 2015
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

Revisions: 1

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

TR13-094 | 13th June 2013
Brendan Juba

On Non-automatizability in PAC-Semantics

We consider the proof search ("automatizability") problem for integrated learning and reasoning, a problem modeling certain kinds of data mining and common sense reasoning (Juba, 2013a). In such a problem, the approximate validity (i.e., under Valiant’s PAC-Semantics (Valiant, 2000)) of an input query formula over a background probability distribution is ... more >>>

TR12-107 | 30th August 2012
Brendan Juba, Ryan Williams

Massive Online Teaching to Bounded Learners

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and ``massively open'': the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We ... more >>>

TR10-155 | 14th October 2010
Brendan Juba, Madhu Sudan

Efficient Semantic Communication via Compatible Beliefs

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

TR09-075 | 17th September 2009
Oded Goldreich, Brendan Juba, Madhu Sudan

A Theory of Goal-Oriented Communication

Revisions: 1 , Comments: 1

We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. The goals can vary from setting to setting, and we provide a general framework for describing any such goal. In this ... more >>>

TR08-095 | 31st October 2008
Brendan Juba, Madhu Sudan

Universal Semantic Communication II: A Theory of Goal-Oriented Communication

Revisions: 1

We continue the investigation of the task of meaningful communication among intelligent entities (players, agents) without any prior common language. Our generic thesis is that such communication is feasible provided the goals of the communicating players are verifiable and compatible. In a previous work we gave supporting evidence for this ... more >>>

TR07-084 | 4th September 2007
Brendan Juba, Madhu Sudan

Universal Semantic Communication I

Is it possible for two intelligent beings to communicate meaningfully, without any common language or background? This question has interest on its own, but is especially relevant in the context of modern computational infrastructures where an increase in the diversity of computers is making the task of inter-computer interaction increasingly ... more >>>

ISSN 1433-8092 | Imprint