Leírás
Abstract:
In the talk, we will discuss three problems.1. The first is a decision
problem: Let X={(a_i,b_j): a_i\in A, b_j\in B} be subset of integer
lattice. A and B are 'splitable' sets (see the definition at the talk)
and the question: decide whether any lattice point belongs to the subset
sums of X or not.
This problem is related to a communication complexity question.
2. In the second problem we define Boolean functions based on pseudo
recursive (or Rényi) type sequences giving bound to the cardinality of
their image set.
3. The Influence is a central notion in Theoretical Computer science; it
is the probability that if we flip any variable of a Boolean function
then its value will change. One can guess if the influence is 'low' then
the support of the Boolean function has a big structured part.
We give (with proof) a quantitative bound for this part. One of the main
tool is an "uncertainty inequality" and tools from Additive
Combinatorics.
For Zoom access please contact Andras Biro (biro.andras[a]renyi.hu).