SlideShare a Scribd company logo
1 of 13
Download to read offline
Circuit complexity of shuffle
Michael Soltys
July 10, 2013
Shuffle - Soltys IWOCA 2013 Title - 1/12
Shuffle
w is a shuffle of x and y: Shuffle(x, y, w)
x = 01101110
y = 10101000
w = 0110110011101000
Shuffle - Soltys IWOCA 2013 Definition - 2/12
Shuffle
w is a shuffle of x and y: Shuffle(x, y, w)
x = 01101110
y = 10101000
w = 0110110011101000
w is a shuffle of x and y provided:
x = x1x2 · · · xk and y = y1y2 · · · yk
and w obtained by “interleaving”:
w = x1y1x2y2 · · · xkyk.
Shuffle - Soltys IWOCA 2013 Definition - 2/12
Motivation
Modelling and verification of concurrent systems
Used in XML database systems for schema definitions
Plan recognition
Natural language processing
See http://bit.ly/17OD2md for more details
Shuffle - Soltys IWOCA 2013 Motivation - 3/12
Square Shuffle
w is a square provided it is equal to a shuffle of a x with itself, i.e.,
∃x s.t. Shuffle(x, x, w).
The string w = 0110110011101000 is a square:
w = 0110110011101000
and
x = 01101100 = 01101100
Shuffle - Soltys IWOCA 2013 Square Shuffle - 4/12
given an alphabet Σ, |Σ| ≥ 7,
Square = {w : ∃x Shuffle(x, x, w)}
is NP-complete; see http://arxiv.org/abs/1211.7161
What we leave open:
What about |Σ| = 2 (for |Σ| = 1, Square is just the set of
even length strings)
What about if |Σ| = ∞ but each symbol cannot occur more
often than, say, 6 times (if each symbol occurs at most 4
times, Square can be reduced to 2-Sat – see P. Austrin
Stack Exchange post http://bit.ly/WATco3)
Shuffle - Soltys IWOCA 2013 Square Shuffle - 5/12
Upper Bound
Shuffle(000, 111, 010101)
Shuffle(011, 011, 001111)
Based on Mansfield’s algorithm, Shuffle ∈ NL
Shuffle - Soltys IWOCA 2013 Upper bound - 6/12
Circuits
5.1. BASIC RESULTS AND DEFINITIONS 67
¬
OO
_
OO
^
OO
^
OO
GG
¬
??
¬
__
>> `` OO
66
OO
KK
Figure 1. Using de Morgan and replicating gates.
_
OO
_
OO
?? __GG WWShuffle - Soltys IWOCA 2013 Upper bound - 7/12
Suppose that we want a family of circuits that recognize
{1n : n ∈ N} ⊆ {0, 1}∗.
4x x x x x x x x x x1 21 1 12 23 3
I.e., it can be done with a ciruit family {Ci } where |Ci | ≤ 1 (and
depth 1), and hence in AC0
.
Shuffle - Soltys IWOCA 2013 Upper bound - 8/12
By results of Sudborough & Venkateswaran:
NL ⊆ SAC1
⊆ AC1
Shuffle - Soltys IWOCA 2013 Upper bound - 9/12
Lower Bound
#(x)s be the number of occurrences of a symbol s in the string x.
Shuffle(0#(x)0 , 1#(x)1 , x) is always true.
Parity(x) =
0 ≤ i ≤ |x|
i is odd
Shuffle(0|x|−i
, 1i
, x),
Shuffle - Soltys IWOCA 2013 Lower bound - 10/12
n−i
i=1 i=3 i=5 i=n
0 x 1 1 10 0 0x x x1
ii n−i i in−i n−i
Shuffle - Soltys IWOCA 2013 Lower bound - 11/12
By the famous result of Furst, Saxe, Sipser, Parity ∈ AC0
.
Therefore Shuffle ∈ AC0
.
Shuffle - Soltys IWOCA 2013 Lower bound - 12/12

More Related Content

Viewers also liked

Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009Michael Soltys
 
Games on Posets - CiE 2008
Games on Posets - CiE 2008Games on Posets - CiE 2008
Games on Posets - CiE 2008Michael Soltys
 
Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System - Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System - Michael Soltys
 
The proof complexity of matrix algebra - Newton Institute, Cambridge 2006
The proof complexity of matrix algebra - Newton Institute, Cambridge 2006The proof complexity of matrix algebra - Newton Institute, Cambridge 2006
The proof complexity of matrix algebra - Newton Institute, Cambridge 2006Michael Soltys
 
La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004Michael Soltys
 
Fair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysisFair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysisMichael Soltys
 
Feasible Combinatorial Matrix Theory - MFCS2013
Feasible Combinatorial Matrix Theory - MFCS2013Feasible Combinatorial Matrix Theory - MFCS2013
Feasible Combinatorial Matrix Theory - MFCS2013Michael Soltys
 
The proof theoretic strength of the Steinitz exchange theorem - EACA 2006
The proof theoretic strength of the Steinitz exchange theorem - EACA 2006The proof theoretic strength of the Steinitz exchange theorem - EACA 2006
The proof theoretic strength of the Steinitz exchange theorem - EACA 2006Michael Soltys
 
Feasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentationFeasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentationMichael Soltys
 
A formal framework for Stringology
A formal framework for StringologyA formal framework for Stringology
A formal framework for StringologyMichael Soltys
 
Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012Michael Soltys
 
FITT Toolbox: Tools for Internal Collaboration
FITT Toolbox: Tools for Internal CollaborationFITT Toolbox: Tools for Internal Collaboration
FITT Toolbox: Tools for Internal CollaborationFITT
 
Forced repetitions over alphabet lists
Forced repetitions over alphabet listsForced repetitions over alphabet lists
Forced repetitions over alphabet listsMichael Soltys
 
How Safe is your Data?
How Safe is your Data?How Safe is your Data?
How Safe is your Data?Michael Soltys
 
An algorithmic view of Computer Science
An algorithmic view of Computer ScienceAn algorithmic view of Computer Science
An algorithmic view of Computer ScienceMichael Soltys
 
Iso 14001 environmental management system
Iso 14001 environmental management systemIso 14001 environmental management system
Iso 14001 environmental management systemTechnoSysCon
 
Story Mapping in a Nutshell
Story Mapping in a NutshellStory Mapping in a Nutshell
Story Mapping in a NutshellVersionOne
 
20 Ideas for your Website Homepage Content
20 Ideas for your Website Homepage Content20 Ideas for your Website Homepage Content
20 Ideas for your Website Homepage ContentBarry Feldman
 

Viewers also liked (20)

Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009Unambiguous functions in logarithmic space - CiE 2009
Unambiguous functions in logarithmic space - CiE 2009
 
Games on Posets - CiE 2008
Games on Posets - CiE 2008Games on Posets - CiE 2008
Games on Posets - CiE 2008
 
Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System - Boolean Programs and Quantified Propositional Proof System -
Boolean Programs and Quantified Propositional Proof System -
 
Intro to Cryptography
Intro to CryptographyIntro to Cryptography
Intro to Cryptography
 
Algorithms on Strings
Algorithms on StringsAlgorithms on Strings
Algorithms on Strings
 
The proof complexity of matrix algebra - Newton Institute, Cambridge 2006
The proof complexity of matrix algebra - Newton Institute, Cambridge 2006The proof complexity of matrix algebra - Newton Institute, Cambridge 2006
The proof complexity of matrix algebra - Newton Institute, Cambridge 2006
 
La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004La, permutations, and the hajós calculus - ICALP 2004
La, permutations, and the hajós calculus - ICALP 2004
 
Fair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysisFair ranking in competitive bidding procurement: a case analysis
Fair ranking in competitive bidding procurement: a case analysis
 
Feasible Combinatorial Matrix Theory - MFCS2013
Feasible Combinatorial Matrix Theory - MFCS2013Feasible Combinatorial Matrix Theory - MFCS2013
Feasible Combinatorial Matrix Theory - MFCS2013
 
The proof theoretic strength of the Steinitz exchange theorem - EACA 2006
The proof theoretic strength of the Steinitz exchange theorem - EACA 2006The proof theoretic strength of the Steinitz exchange theorem - EACA 2006
The proof theoretic strength of the Steinitz exchange theorem - EACA 2006
 
Feasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentationFeasible Combinatorial Matrix Theory - LICS2013 presentation
Feasible Combinatorial Matrix Theory - LICS2013 presentation
 
A formal framework for Stringology
A formal framework for StringologyA formal framework for Stringology
A formal framework for Stringology
 
Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012Perceptions of Foundational Knowledge by CS students - WCCCE 2012
Perceptions of Foundational Knowledge by CS students - WCCCE 2012
 
FITT Toolbox: Tools for Internal Collaboration
FITT Toolbox: Tools for Internal CollaborationFITT Toolbox: Tools for Internal Collaboration
FITT Toolbox: Tools for Internal Collaboration
 
Forced repetitions over alphabet lists
Forced repetitions over alphabet listsForced repetitions over alphabet lists
Forced repetitions over alphabet lists
 
How Safe is your Data?
How Safe is your Data?How Safe is your Data?
How Safe is your Data?
 
An algorithmic view of Computer Science
An algorithmic view of Computer ScienceAn algorithmic view of Computer Science
An algorithmic view of Computer Science
 
Iso 14001 environmental management system
Iso 14001 environmental management systemIso 14001 environmental management system
Iso 14001 environmental management system
 
Story Mapping in a Nutshell
Story Mapping in a NutshellStory Mapping in a Nutshell
Story Mapping in a Nutshell
 
20 Ideas for your Website Homepage Content
20 Ideas for your Website Homepage Content20 Ideas for your Website Homepage Content
20 Ideas for your Website Homepage Content
 

Similar to Circuit Complexity of Shuffle - IWOCA 2013

MMsemester project
MMsemester projectMMsemester project
MMsemester projectPreeti Sahu
 
Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...
Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...
Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...Crimsonpublishers-Mechanicalengineering
 
Two algorithms to accelerate training of back-propagation neural networks
Two algorithms to accelerate training of back-propagation neural networksTwo algorithms to accelerate training of back-propagation neural networks
Two algorithms to accelerate training of back-propagation neural networksESCOM
 
Dynamic response of structures with uncertain properties
Dynamic response of structures with uncertain propertiesDynamic response of structures with uncertain properties
Dynamic response of structures with uncertain propertiesUniversity of Glasgow
 
Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)
Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)
Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)Joke Hadermann
 
2d beam element with combined loading bending axial and torsion
2d beam element with combined loading bending axial and torsion2d beam element with combined loading bending axial and torsion
2d beam element with combined loading bending axial and torsionrro7560
 
Mathcad - CMS (Component Mode Synthesis) Analysis.pdf
Mathcad - CMS (Component Mode Synthesis) Analysis.pdfMathcad - CMS (Component Mode Synthesis) Analysis.pdf
Mathcad - CMS (Component Mode Synthesis) Analysis.pdfJulio Banks
 
Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)Maamoun Hennache
 
Artificial neural netwoks2
Artificial neural netwoks2Artificial neural netwoks2
Artificial neural netwoks2yosser atassi
 
Lecture 5: Stochastic Hydrology
Lecture 5: Stochastic Hydrology Lecture 5: Stochastic Hydrology
Lecture 5: Stochastic Hydrology Amro Elfeki
 
about power system operation and control13197214.ppt
about power system operation and control13197214.pptabout power system operation and control13197214.ppt
about power system operation and control13197214.pptMohammedAhmed66819
 
Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)Maamoun Hennache
 
Engineering circuit-analysis solutions 7ed hayt
Engineering circuit-analysis solutions 7ed haytEngineering circuit-analysis solutions 7ed hayt
Engineering circuit-analysis solutions 7ed haytCristian Del Rio Martinez
 
Engineering circuit-analysis-solutions-7ed-hayt
Engineering circuit-analysis-solutions-7ed-haytEngineering circuit-analysis-solutions-7ed-hayt
Engineering circuit-analysis-solutions-7ed-haytAracely Guerrero
 
Engineering circuit-analysis-solutions-7ed-hayt [upload by r1-lher
Engineering circuit-analysis-solutions-7ed-hayt [upload by r1-lherEngineering circuit-analysis-solutions-7ed-hayt [upload by r1-lher
Engineering circuit-analysis-solutions-7ed-hayt [upload by r1-lherRick Cevallos
 

Similar to Circuit Complexity of Shuffle - IWOCA 2013 (20)

MMsemester project
MMsemester projectMMsemester project
MMsemester project
 
Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...
Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...
Anomalous Diffusion Through Homopolar Membrane: One-Dimensional Model_ Crimso...
 
Two algorithms to accelerate training of back-propagation neural networks
Two algorithms to accelerate training of back-propagation neural networksTwo algorithms to accelerate training of back-propagation neural networks
Two algorithms to accelerate training of back-propagation neural networks
 
Dynamic response of structures with uncertain properties
Dynamic response of structures with uncertain propertiesDynamic response of structures with uncertain properties
Dynamic response of structures with uncertain properties
 
Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)
Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)
Electron diffraction: Tutorial with exercises and solutions (EMAT Workshop 2017)
 
2d beam element with combined loading bending axial and torsion
2d beam element with combined loading bending axial and torsion2d beam element with combined loading bending axial and torsion
2d beam element with combined loading bending axial and torsion
 
Mathcad - CMS (Component Mode Synthesis) Analysis.pdf
Mathcad - CMS (Component Mode Synthesis) Analysis.pdfMathcad - CMS (Component Mode Synthesis) Analysis.pdf
Mathcad - CMS (Component Mode Synthesis) Analysis.pdf
 
Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 15 solutions_to_exercises(engineering circuit analysis 7th)
 
Fi nal
Fi nalFi nal
Fi nal
 
Backpropagation for Neural Networks
Backpropagation for Neural NetworksBackpropagation for Neural Networks
Backpropagation for Neural Networks
 
Section 11.9
Section 11.9Section 11.9
Section 11.9
 
Artificial neural netwoks2
Artificial neural netwoks2Artificial neural netwoks2
Artificial neural netwoks2
 
alt klausur
alt klausuralt klausur
alt klausur
 
Analytic dynamics
Analytic dynamicsAnalytic dynamics
Analytic dynamics
 
Lecture 5: Stochastic Hydrology
Lecture 5: Stochastic Hydrology Lecture 5: Stochastic Hydrology
Lecture 5: Stochastic Hydrology
 
about power system operation and control13197214.ppt
about power system operation and control13197214.pptabout power system operation and control13197214.ppt
about power system operation and control13197214.ppt
 
Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)
Chapter 16 solutions_to_exercises(engineering circuit analysis 7th)
 
Engineering circuit-analysis solutions 7ed hayt
Engineering circuit-analysis solutions 7ed haytEngineering circuit-analysis solutions 7ed hayt
Engineering circuit-analysis solutions 7ed hayt
 
Engineering circuit-analysis-solutions-7ed-hayt
Engineering circuit-analysis-solutions-7ed-haytEngineering circuit-analysis-solutions-7ed-hayt
Engineering circuit-analysis-solutions-7ed-hayt
 
Engineering circuit-analysis-solutions-7ed-hayt [upload by r1-lher
Engineering circuit-analysis-solutions-7ed-hayt [upload by r1-lherEngineering circuit-analysis-solutions-7ed-hayt [upload by r1-lher
Engineering circuit-analysis-solutions-7ed-hayt [upload by r1-lher
 

Recently uploaded

SERPENT COIL: THE AWAKENING OF KUNDALINI
SERPENT COIL: THE AWAKENING OF KUNDALINISERPENT COIL: THE AWAKENING OF KUNDALINI
SERPENT COIL: THE AWAKENING OF KUNDALINISantanu Das
 
DP & Nostradamus-Fatima-Bailey-Branham-Ford - Short vers
DP & Nostradamus-Fatima-Bailey-Branham-Ford - Short versDP & Nostradamus-Fatima-Bailey-Branham-Ford - Short vers
DP & Nostradamus-Fatima-Bailey-Branham-Ford - Short versBengt & Maarit de Paulis
 
Free eBook ~Short Inspirational Stories - The Benefits.pdf
Free eBook ~Short Inspirational Stories - The Benefits.pdfFree eBook ~Short Inspirational Stories - The Benefits.pdf
Free eBook ~Short Inspirational Stories - The Benefits.pdfOH TEIK BIN
 
Old Age but fruitful and meaningful.pptx
Old Age but fruitful and meaningful.pptxOld Age but fruitful and meaningful.pptx
Old Age but fruitful and meaningful.pptxInnovator Marbun
 
The_Chronological_Life_of_Christ_Part_93_Fear God
The_Chronological_Life_of_Christ_Part_93_Fear GodThe_Chronological_Life_of_Christ_Part_93_Fear God
The_Chronological_Life_of_Christ_Part_93_Fear GodNetwork Bible Fellowship
 
Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]
Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]
Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]iqra tube
 
Deerfoot Church of Christ Bulletin 3 24 24
Deerfoot Church of Christ Bulletin 3 24 24Deerfoot Church of Christ Bulletin 3 24 24
Deerfoot Church of Christ Bulletin 3 24 24deerfootcoc
 
DP & Jesus Marriage - 2 potential candidates
DP & Jesus Marriage - 2 potential candidatesDP & Jesus Marriage - 2 potential candidates
DP & Jesus Marriage - 2 potential candidatesBengt & Maarit de Paulis
 
Easter Apocalypse_Palm Sunday_Rev. 7.pptx
Easter Apocalypse_Palm Sunday_Rev. 7.pptxEaster Apocalypse_Palm Sunday_Rev. 7.pptx
Easter Apocalypse_Palm Sunday_Rev. 7.pptxStephen Palm
 
April 2024 Calendar of Events Hope Lutheran Church Floodwood
April 2024 Calendar of Events Hope Lutheran Church FloodwoodApril 2024 Calendar of Events Hope Lutheran Church Floodwood
April 2024 Calendar of Events Hope Lutheran Church FloodwoodFloodwoodvern
 
Indications of Rebirth ~ My Reflections (English & Chinese).pptx
Indications of  Rebirth ~ My Reflections (English & Chinese).pptxIndications of  Rebirth ~ My Reflections (English & Chinese).pptx
Indications of Rebirth ~ My Reflections (English & Chinese).pptxOH TEIK BIN
 
All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...
All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...
All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...iqra tube
 
365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...
365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...
365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...Eizijesu Obahaiye
 
The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...
The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...
The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...Cometan
 

Recently uploaded (15)

SERPENT COIL: THE AWAKENING OF KUNDALINI
SERPENT COIL: THE AWAKENING OF KUNDALINISERPENT COIL: THE AWAKENING OF KUNDALINI
SERPENT COIL: THE AWAKENING OF KUNDALINI
 
DP & Nostradamus-Fatima-Bailey-Branham-Ford - Short vers
DP & Nostradamus-Fatima-Bailey-Branham-Ford - Short versDP & Nostradamus-Fatima-Bailey-Branham-Ford - Short vers
DP & Nostradamus-Fatima-Bailey-Branham-Ford - Short vers
 
Free eBook ~Short Inspirational Stories - The Benefits.pdf
Free eBook ~Short Inspirational Stories - The Benefits.pdfFree eBook ~Short Inspirational Stories - The Benefits.pdf
Free eBook ~Short Inspirational Stories - The Benefits.pdf
 
Old Age but fruitful and meaningful.pptx
Old Age but fruitful and meaningful.pptxOld Age but fruitful and meaningful.pptx
Old Age but fruitful and meaningful.pptx
 
The_Chronological_Life_of_Christ_Part_93_Fear God
The_Chronological_Life_of_Christ_Part_93_Fear GodThe_Chronological_Life_of_Christ_Part_93_Fear God
The_Chronological_Life_of_Christ_Part_93_Fear God
 
Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]
Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]
Islamic Finance 101 - Dr. Main Alqudah [https://www.guidancecollege.org/]
 
Deerfoot Church of Christ Bulletin 3 24 24
Deerfoot Church of Christ Bulletin 3 24 24Deerfoot Church of Christ Bulletin 3 24 24
Deerfoot Church of Christ Bulletin 3 24 24
 
DP & Jesus Marriage - 2 potential candidates
DP & Jesus Marriage - 2 potential candidatesDP & Jesus Marriage - 2 potential candidates
DP & Jesus Marriage - 2 potential candidates
 
Easter Apocalypse_Palm Sunday_Rev. 7.pptx
Easter Apocalypse_Palm Sunday_Rev. 7.pptxEaster Apocalypse_Palm Sunday_Rev. 7.pptx
Easter Apocalypse_Palm Sunday_Rev. 7.pptx
 
April 2024 Calendar of Events Hope Lutheran Church Floodwood
April 2024 Calendar of Events Hope Lutheran Church FloodwoodApril 2024 Calendar of Events Hope Lutheran Church Floodwood
April 2024 Calendar of Events Hope Lutheran Church Floodwood
 
English - The 1st Book of Adam and Eve.pdf
English - The 1st Book of Adam and Eve.pdfEnglish - The 1st Book of Adam and Eve.pdf
English - The 1st Book of Adam and Eve.pdf
 
Indications of Rebirth ~ My Reflections (English & Chinese).pptx
Indications of  Rebirth ~ My Reflections (English & Chinese).pptxIndications of  Rebirth ~ My Reflections (English & Chinese).pptx
Indications of Rebirth ~ My Reflections (English & Chinese).pptx
 
All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...
All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...
All About Zakah for Muslim Americans - Dr. Main Alqudah [https://www.guidance...
 
365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...
365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...
365 Days of Thanking God_ Cultivating a Heart of Thanksgiving Everyday (Revis...
 
The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...
The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...
The Mormon & Quaker Moons of Lancashire: Stories of Religious Conversion & Mi...
 

Circuit Complexity of Shuffle - IWOCA 2013

  • 1. Circuit complexity of shuffle Michael Soltys July 10, 2013 Shuffle - Soltys IWOCA 2013 Title - 1/12
  • 2. Shuffle w is a shuffle of x and y: Shuffle(x, y, w) x = 01101110 y = 10101000 w = 0110110011101000 Shuffle - Soltys IWOCA 2013 Definition - 2/12
  • 3. Shuffle w is a shuffle of x and y: Shuffle(x, y, w) x = 01101110 y = 10101000 w = 0110110011101000 w is a shuffle of x and y provided: x = x1x2 · · · xk and y = y1y2 · · · yk and w obtained by “interleaving”: w = x1y1x2y2 · · · xkyk. Shuffle - Soltys IWOCA 2013 Definition - 2/12
  • 4. Motivation Modelling and verification of concurrent systems Used in XML database systems for schema definitions Plan recognition Natural language processing See http://bit.ly/17OD2md for more details Shuffle - Soltys IWOCA 2013 Motivation - 3/12
  • 5. Square Shuffle w is a square provided it is equal to a shuffle of a x with itself, i.e., ∃x s.t. Shuffle(x, x, w). The string w = 0110110011101000 is a square: w = 0110110011101000 and x = 01101100 = 01101100 Shuffle - Soltys IWOCA 2013 Square Shuffle - 4/12
  • 6. given an alphabet Σ, |Σ| ≥ 7, Square = {w : ∃x Shuffle(x, x, w)} is NP-complete; see http://arxiv.org/abs/1211.7161 What we leave open: What about |Σ| = 2 (for |Σ| = 1, Square is just the set of even length strings) What about if |Σ| = ∞ but each symbol cannot occur more often than, say, 6 times (if each symbol occurs at most 4 times, Square can be reduced to 2-Sat – see P. Austrin Stack Exchange post http://bit.ly/WATco3) Shuffle - Soltys IWOCA 2013 Square Shuffle - 5/12
  • 7. Upper Bound Shuffle(000, 111, 010101) Shuffle(011, 011, 001111) Based on Mansfield’s algorithm, Shuffle ∈ NL Shuffle - Soltys IWOCA 2013 Upper bound - 6/12
  • 8. Circuits 5.1. BASIC RESULTS AND DEFINITIONS 67 ¬ OO _ OO ^ OO ^ OO GG ¬ ?? ¬ __ >> `` OO 66 OO KK Figure 1. Using de Morgan and replicating gates. _ OO _ OO ?? __GG WWShuffle - Soltys IWOCA 2013 Upper bound - 7/12
  • 9. Suppose that we want a family of circuits that recognize {1n : n ∈ N} ⊆ {0, 1}∗. 4x x x x x x x x x x1 21 1 12 23 3 I.e., it can be done with a ciruit family {Ci } where |Ci | ≤ 1 (and depth 1), and hence in AC0 . Shuffle - Soltys IWOCA 2013 Upper bound - 8/12
  • 10. By results of Sudborough & Venkateswaran: NL ⊆ SAC1 ⊆ AC1 Shuffle - Soltys IWOCA 2013 Upper bound - 9/12
  • 11. Lower Bound #(x)s be the number of occurrences of a symbol s in the string x. Shuffle(0#(x)0 , 1#(x)1 , x) is always true. Parity(x) = 0 ≤ i ≤ |x| i is odd Shuffle(0|x|−i , 1i , x), Shuffle - Soltys IWOCA 2013 Lower bound - 10/12
  • 12. n−i i=1 i=3 i=5 i=n 0 x 1 1 10 0 0x x x1 ii n−i i in−i n−i Shuffle - Soltys IWOCA 2013 Lower bound - 11/12
  • 13. By the famous result of Furst, Saxe, Sipser, Parity ∈ AC0 . Therefore Shuffle ∈ AC0 . Shuffle - Soltys IWOCA 2013 Lower bound - 12/12