Advanced Complexity Conjectures on Protocol Design

 
The Power of Super-Log
Number of Players
 
Arkadev Chattopadhyay
(TIFR, Mumbai)
 
Joint with:
Michael Saks 
(
Rutgers
)
 
 
                       
A Conjecture
 
 
f:{0,1}
n
 
!
 {0,1}
 
 
X
1
 
X
2
 
X
3
 
X
k
 
(f
±
g) 
(
X
1
,
X
2
,
,
X
k
) =
 
)
 MAJ 
±
 MAJ 
 
ACC
0
 
1
 
1
 
0
 
1
 
0
 
0
 
0
 
f(g(C
1
),
g(C
2
),…,
g(C
n
))
 
n
 
Question: 
Complexity of (MAJ 
± 
MAJ)?
 
Observation:
 
a la Beigel-Tarui’91
 
)
 MAJ 
 
ACC
0
 
Proposed by 
Babai-Kimmel-Lokam’95
 
g:{0,1}
k
 
!
 {0,1} .
TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.:
A
A
A
A
A
A
A
                 
Some Upper Bounds
SYM 
± 
AND 
{
GIP, Disj,…}
 
Popular Names
 
SYM 
± 
g
 
{GIP, MAJ 
±
 MAJ, Disj…}
Deterministic

(n/
2
k 
+ k
¢
 log n )
.
 
 O(k.(log n)
2
), k 
¸
 log n + 2
.
Grolmusz’91, Pudlak
 
Babai-Gal-Kimmel-Lokam’02
k 
¸
 3
 
Ada-C-Fawzi-Nguyen’12
 
g: compressible and
     symmetric
 
SYM 
± 
ANY
 
Simultaneous
 
Simultaneous
Almost- Simultaneous
 
 O(k.(log n)
2
), k 
¸
 log n + 4
.
                       
Block Composition
 
f:{0,1}
n
 
!
 {0,1}
 
 
X
1
 
X
2
 
X
3
 
X
k
 
(f
n
±
g
r
) 
(
X
1
,
X
2
,
,
X
k
) =
 
)
 MAJ 
 
ACC
0
 
f(g(A
1
),
g(A
2
),…,
g(A
n
))
 
n 
= 2
r 
= 3
 
Conjecture:
 
Fact:
 
Babai-Gal-Kimmel-Lokam’02
g:{0,1}
k
£
r
 
!
 {0,1}.
 
Still Open!
 
A
1
 
A
2
 
Even for interactive protocols
TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.:
A
A
A
A
A
A
A
                        
Our Result
 
Theorem: 
SYM
n
 
±
 ANY
r
  has a 2-round k-party deterministic protocol
of cost
when,
 
Remark 1: 
First protocol for r > 1.
 
Remark 2:
 
Corollary: 
MAJ 
±
 MAJ
r
 has efficient protocol when 
r
 is poly-log
and 
k
 is a sufficiently large poly-log.
 
r = O(log log n)
 
Main Ingredients
 
Computing k-1 degree polynomials is easy for k-
players. 
 
(Goldman-Hastad’90’s)
 
 
Degree reduction by basis change.  
(New Idea)
Low degree Polynomials
x
3
 
x
5
 
x
7
   Alice
x
6
 
x
10
 
x
11
x
2
 
x
8
 
x
9
Charlie
   Alex
x
1
 
x
4
 
x
12
 
Bob, Charlie
 
Alice
 
Alex
 
Alice, Charlie
 
Bob, Alex
 
deg(
P
) = 3
 
k
 = 4 > deg(
P
)
 
Simultaneous 
k
-party
deterministic protocol
 
Cost = 
O(
k
¢
 log|
F
|)
                       
A Polynomial Fantasy
f:{0,1}
n
 
!
 {0,1}
 
 
(SYM 
±
 
g) 
(
C
1
,
C
2
,
,
C
n
) =
 
Fantasy: 
P
high
(Ci
) = 0 for all i 
!!
g:{0,1}
k
 
!
 {0,1} 
µ
 
F
p
 
.
Prime p > 
n
 
g(X) 
´
 
P
(
X
1
,
,
X
k
)
 
deg(P) 
·
 
k
 
P 
´
 
P
high
(X) + 
P
low
(X)
 
deg < 
k
 
deg = 
k
 
easy k-player protocol
of cost  = k.log(p)
 
Bad
                       
Shifted Basis
 
 
Example:
 
Fact: 
B
u
 is a basis for every 
u
 
2
 {
0,1}
k
 
u
 = 
0
k
 gives standard basis
 
u
-shifted
 
A
 
Def: 
u 
is good for A if for all column C of A, 
u 
and C agree on
some co-ordinate.
 
good
 
bad
 
no agreement
                       
Good is Really Good
 
(SYM 
±
 
g) 
(
C
1
,
C
2
,
,
C
n
) =
 
Fact: 
P
high
(
C
) = 0 for all 
C
  if 
u
 is good for A.
easy k-player protocol
of cost log(p)    
Bad
 
u
 
Apply 
u
 -shift
 
u
 
u
 
Zeroed out!
Good Shifts Are Aplenty
Observation: 
If 
k
 
À
 log 
n
 + 1, Player 
k
 spots many
good shifts.
 
Protocol:
Player 
k
 announces a good shift 
u
.
All players compute their portions using 
u
.
 
Simultaneous!
 
Cost =
 
k
 - 1
 
Cost =
 
k
¢
 log(p)
 
 = 
O(
k
¢
 log 
n
)
 
Extends to r = O(log log n).
Future Direction
Can we go to r = O(log n)?
Is                                                                      ?
 
                          
Thank You!
Slide Note
Embed
Share

Explore advanced complexity conjectures and protocol designs in the realm of computational theory, discussing topics such as the power of super-log number of players, block composition, low-degree polynomials, and polynomial fantasies. Delve into the complexities of MAJ.MAJ, SYM, and more, while considering upper bounds and key results from notable researchers.

  • Computational Theory
  • Protocol Design
  • Complexity Conjectures
  • Protocol Complexity
  • Advanced Computations

Uploaded on Oct 01, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. The Power of Super-Log Number of Players Arkadev Chattopadhyay (TIFR, Mumbai) Joint with: Michael Saks (Rutgers)

  2. A Conjecture g:{0,1}k! {0,1} . f:{0,1}n! {0,1} (f g) (X1,X2, ,Xk) = f(g(C1),g(C2), ,g(Cn)) 0 0 1 0 1 1 0 Question: Complexity of (MAJ MAJ)? 0 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 1 0 0 . . . . . . . . 1 1 1 1 1 1 0 X1 X2 Observation: X3 ) MAJ MAJ ACC0 a la Beigel-Tarui 91 . . . . . . ) MAJ ACC0 Xk Proposed by Babai-Kimmel-Lokam 95 n

  3. Some Upper Bounds k 3 Popular Names Deterministic (n/2k + k log n ). {GIP, Disj, } SYM AND Grolmusz 91, Pudlak Almost- Simultaneous O(k.(log n)2), k log n + 2. {GIP, MAJ MAJ, Disj } SYM g g: compressible and symmetric Babai-Gal-Kimmel-Lokam 02 Simultaneous O(k.(log n)2), k log n + 4. SYM ANY Ada-C-Fawzi-Nguyen 12 Simultaneous

  4. Block Composition g:{0,1}k r! {0,1}. f:{0,1}n! {0,1} (fn gr) (X1,X2, ,Xk) = f(g(A1),g(A2), ,g(An)) n = 2 r = 3 Conjecture: A1 A2 0 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 . . . . . . 1 1 1 1 1 0 X1 X2 Fact: X3 ) MAJ ACC0 . . . . . . Babai-Gal-Kimmel-Lokam 02 Xk Still Open! Even for interactive protocols

  5. Our Result Theorem: SYMn ANYr has a 2-round k-party deterministic protocol of cost r = O(log log n) when, Remark 1: First protocol for r > 1. Remark 2: Corollary: MAJ MAJr has efficient protocol when r is poly-log and k is a sufficiently large poly-log.

  6. Main Ingredients Computing k-1 degree polynomials is easy for k- players. (Goldman-Hastad 90 s) Degree reduction by basis change. (New Idea)

  7. Low degree Polynomials Bob, Charlie Bob, Alex Alex Alice Alice, Charlie x3x5x7 x6x10x11 x2x8x9 x1x4x12 Alice Bob Cost = O(k k log|F F|) Simultaneous k k-party deterministic protocol deg(P P) = 3 k k = 4 > deg(P P) Charlie Alex

  8. A Polynomial Fantasy g:{0,1}k! {0,1} Fp. Prime p > n n f:{0,1}n! {0,1} g(X) P(X1, ,Xk) deg(P) k k P Phigh(X) + Plow(X) deg < k k deg = k k (SYM g) (C1,C2, ,Cn) = easy k-player protocol of cost = k.log(p) Bad Fantasy: Phigh(Ci) = 0 for all i !!

  9. Shifted Basis u-shifted u u = 0k k gives standard basis Fact: Bu is a basis for every u2 {0,1}k Def: u is good for A if for all column C of A, u and C agree on some co-ordinate. no agreement 0 1 0 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 0 0 A 1 0 0 0 Example: bad good

  10. Good is Really Good u u u u (SYM g) (C1,C2, ,Cn) = easy k-player protocol of cost log(p) Bad Zeroed out! Apply u u -shift u u Fact: Phigh(C) = 0 for all C if u u is good for A.

  11. Good Shifts Are Aplenty Observation: If k log n + 1, Player k spots many good shifts. Protocol: Player k announces a good shift u u. Cost = k - 1 Simultaneous! All players compute their portions using u u. Cost = k log(p) = O(k log n) Extends to r = O(log log n).

  12. Future Direction Can we go to r = O(log n)? Is ? Thank You!

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#