Lewis, Laura; Zhu, Daiwei; et el. (2024) Experimental
implementation of an efficient test of quantumness ; Physical Review
A; Vol. 109; No. 1; 012610; 10.1103/physreva.109.012610
Mahadev, Urmila; Vazirani, Umesh; et el. (2022) Efficient
Certifiable Randomness from a Single Quantum Device ; 10.48550/arXiv.2204.11353
Lewis, Laura; Zhu, Daiwei; et el. (2022) Experimental
Implementation of an Efficient Test of Quantumness ; 10.48550/arXiv.2209.14316
Dinur, Irit; Hsieh, Min-Hsiu; et el. (2022) Good
Quantum LDPC Codes with Linear Time Decoders ; 10.48550/arXiv.2206.07750
Culf, Eric; Vidick, Thomas; et el. (2022) Group
coset monogamy games and an application to device-independent
continuous-variable QKD ; 10.48550/arXiv.2212.03935
Bartusek, James; Kalai, Yael Tauman; et el. (2022) Succinct
Classical Verification of Quantum Computation ; 10.48550/arXiv.2206.14929
Culf, Eric and Vidick, Thomas (2022) A
monogamy-of-entanglement game for subspace coset states ; Quantum;
Vol. 6; Art. No. 791; 10.22331/q-2022-09-01-791
Bavarian, Mohammad; Vidick, Thomas; et el. (2022) Anchored
Parallel Repetition for Nonlocal Games ; SIAM Journal on Computing;
Vol. 51; No. 2; 214-253; 10.1137/21m1405927
Ji, Zhengfeng; Natarajan, Anand; et el. (2022) Quantum
soundness of testing tensor codes ; ISBN 978-1-6654-2056-3; 2021 IEEE
62nd Annual Symposium on Foundations of Computer Science (FOCS); IEEE:
Piscataway, NJ; 586-597; 10.1109/FOCS52979.2021.00064
Zhu, Daiwei; Kahanamoku-Meyer, Gregory D.; et el. (2022) Interactive
Protocols for Classically-Verifiable Quantum Advantage ; 10.48550/arXiv.2112.05156
Vidick, Thomas (2022) Almost
synchronous quantum correlations ; Journal of Mathematical Physics;
Vol. 63; No. 2; Art. No. 022201; 10.1063/5.0056512
Ji, Zhengfeng; Natarajan, Anand; et el. (2021) MIP*
= RE ; Communications of the ACM; Vol. 64; No. 11; 131-138; 10.1145/3485628
Culf, Eric and Vidick, Thomas (2021) A
monogamy-of-entanglement game for subspace coset states ; 10.48550/arXiv.2107.13324
Ji, Zhengfeng; Natarajan, Anand; et el. (2021) Quantum
soundness of the classical low individual degree test ; 10.48550/arXiv.2009.12982
Metger, Tony and Vidick, Thomas (2021) Self-testing
of a single quantum device under computational assumptions ; Quantum;
Vol. 5; Art. No. 544; 10.22331/q-2021-09-16-544
Brakerski, Zvika; Christiano, Paul; et el. (2021) A
Cryptographic Test of Quantumness and Certifiable Randomness from a
Single Quantum Device ; Journal of the ACM; Vol. 68; No. 5; Art.
No. 31; 10.1145/3441309
Vidick, Thomas and Zhang, Tina (2021) Classical
Proofs of Quantum Knowledge ; ISBN 9783030778859; Advances in
Cryptology – EUROCRYPT 2021; Springer: Cham; 630-660; 10.1007/978-3-030-77886-6_22
Coudron, Matthew; Stark, Jalex; et el. (2021) Trading
Locality for Time: Certifiable Randomness from Low-Depth Circuits ;
Communications in Mathematical Physics; Vol. 382; No. 1; 49-86; 10.1007/s00220-021-03963-w
Ji, Zhengfeng; Leung, Debbie; et el. (2020) A
three-player coherent state embezzlement game ; Quantum; Vol. 4; Art.
No. 349; 10.22331/q-2020-10-26-349
Vidick, Thomas and Zhang, Tina (2020) Classical
proofs of quantum knowledge ; 10.48550/arXiv.2005.01691
Regev, Oded and Vidick, Thomas (2020) Bounds
on Dimension Reduction in the Nuclear Norm ; ISBN 978-3-030-46761-6;
Geometric Aspects of Functional Analysis: Israel Seminar (GAFA)
2017-2019 Volume II; Springer: Cham; 279-299; 10.1007/978-3-030-46762-3_13
Brakerski, Zvika; Koppula, Venkata; et el. (2020) Simpler
Proofs of Quantumness ; 10.4230/LIPIcs.TQC.2020.8
Vidick, Thomas and Zhang, Tina (2020) Classical
zero-knowledge arguments for quantum computations ; Quantum; Vol. 4;
Art. No. 266; 10.22331/q-2020-05-14-266
Coladangelo, Andrea; Vidick, Thomas; et el. (2020) Non-interactive
zero-knowledge arguments for QMA, with preprocessing ; 10.48550/arXiv.1911.07546
Vidick, Thomas (2020) Verifying
quantum computations at scale: A cryptographic leash on quantum
devices ; Bulletin of the American Mathematical Society; Vol. 57;
No. 1; 39-76; 10.1090/bull/1678
Gheorghiu, Alexandru and Vidick, Thomas (2019) Computationally-Secure
and Composable Remote State Preparation ; ISBN 9781728149523; 2019
IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS);
IEEE: Piscataway, NJ; 1024-1033; 10.1109/focs.2019.00066
Vidick, Thomas (2019) From
Operator Algebras to Complexity Theory and Back ; Notices of the
American Mathematical Society; Vol. 66; No. 10; 1618-1627; 10.1090/noti1980
Fitzsimons, Joseph; Ji, Zhengfeng; et el. (2019) Quantum
proof systems for iterated exponential time, and beyond ; ISBN
978-1-4503-6705-9; Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing (STOC ’19); Association for Computing Machinery:
New York, NY; 473-480; 10.1145/3313276.3316343
Aggarwal, Divesh; Chung, Kai-Min; et el. (2019) A
Quantum-Proof Non-Malleable Extractor, With Application to Privacy
Amplification against Active Quantum Adversaries ; ISBN
978-3-030-17655-6; Advances in Cryptology - EUROCRYPT 2019; Springer:
Cham; 442-469; 10.1007/978-3-030-17656-3_16
Coladangelo, Andrea; Grilo, Alex B.; et el. (2019) Verifier-on-a-Leash:
new schemes for verifiable delegated quantum computation, with
quasilinear resources ; ISBN 978-3-030-17658-7; Advances in
Cryptology - EUROCRYPT 2019; Springer: Cham; 247-277; 10.1007/978-3-030-17659-4_9
Vazirani, Umesh and Vidick, Thomas (2019) Fully
device independent quantum key distribution ; Communications of the
ACM; Vol. 62; No. 4; 133-133; 10.1145/3310974
Heilman, Steven and Vidick, Thomas (2019) A
Moment Majorization principle for random matrix ensembles with
applications to hardness of the noncommutative Grothendieck problem ;
10.48550/arXiv.1603.05620
Vidick, Thomas and Yuen, Henry (2019) A
simple proof of Renner’s exponential de Finetti theorem ; 10.48550/arXiv.1608.04814
Vazirani, Umesh and Vidick, Thomas (2019) Certifiable
Quantum Dice - Or, testable exponential randomness expansion ; 10.48550/arXiv.1111.6054
Briët, Jop; Buhrman, Harry; et el. (2019) Multiplayer
XOR games and quantum communication complexity with clique-wise
entanglement ; 10.48550/arXiv.0911.4007v1
Molina, Abel; Vidick, Thomas; et el. (2019) Optimal
counterfeiting attacks and generalizations for Wiesner’s quantum
money ; 10.48550/arXiv.1202.4010
Vidick, Thomas (2019) Parallel
DIQKD from parallel repetition ; 10.48550/arXiv.1703.08508
Arnon-Friedman, Rotem; Renner, Renato; et el. (2019) Simple
and tight device-independent security proofs ; SIAM Journal on
Computing; Vol. 48; No. 1; 181-225; 10.1137/18M1174726
Brakerski, Zvika; Christiano, Paul; et el. (2018) A
Cryptographic Test of Quantumness and Certifiable Randomness from a
Single Quantum Device ; ISBN 9781538642306; 2018 IEEE 59th Annual
Symposium on Foundations of Computer Science (FOCS); IEEE: Piscataway,
NJ; 320-331; 10.1109/focs.2018.00038
Slofstra, William and Vidick, Thomas (2018) Entanglement
in Non-local Games and the Hyperlinear Profile of Groups ; Annales
Henri Poincaré; Vol. 19; No. 10; 2979-3005; 10.1007/s00023-018-0718-y
Natarajan, Anand and Vidick, Thomas (2018) Low-Degree
Testing for Quantum States, and a Quantum Entangled Games PCP for
QMA ; ISBN 9781538642306; 2018 IEEE 59th Annual Symposium on
Foundations of Computer Science (FOCS); IEEE: Piscataway, NJ; 731-742;
10.1109/focs.2018.00075
Chao, Rui; Reichardt, Ben W.; et el. (2018) Test
for a large amount of entanglement, using few measurements ; Quantum;
Vol. 2; Art. No. 92; 10.22331/q-2018-09-03-92
Ostrev, Dimiter and Vidick, Thomas (2018) Entanglement
of approximate quantum strategies in XOR games ; Quantum Information
and Computation; Vol. 18; No. 7-8; 617-631; 10.48550/arXiv.1609.01652
Natarajan, Anand and Vidick, Thomas (2018) Two-Player
Entangled Games are NP-Hard ; ISBN 978-3-95977-069-9; 33rd
Computational Complexity Conference (CCC 2018); Schloss Dagstuhl –
Leibniz-Zentrum für Informatik: Wadern, Germany; Art. No. 20; 10.4230/LIPIcs.CCC.2018.20
Arnon-Friedman, Rotem; Dupuis, Frédéric; et el. (2018) Practical
device-independent quantum cryptography via entropy accumulation ;
Nature Communications; Vol. 9; Art. No. 459; PMCID PMC5792631; 10.1038/s41467-017-02307-4
Roberts, Brenden; Vidick, Thomas; et el. (2017) Implementation
of rigorous renormalization group method for ground space and low-energy
states of local Hamiltonians ; Physical Review B; Vol. 96; No. 21;
Art. No. 214203; 10.1103/PhysRevB.96.214203
Bavarian, Mohammad; Vidick, Thomas; et el. (2017) Parallel
repetition via fortification: analytic view and the quantum case ;
ISBN 9783959770293; 8th Innovations in Theoretical Computer Science
Conference; Dagstuhl Publishing; Art. No. 22; 10.4230/LIPIcs.ITCS.2017.22
Arad, Itai; Landau, Zeph; et el. (2017) Rigorous
Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D ; 10.4230/LIPIcs.ITCS.2017.46
Arad, Itai; Landau, Zeph; et el. (2017) Rigorous
RG algorithms and area laws for low energy eigenstates in 1D ;
Communications in Mathematical Physics; Vol. 356; No. 1; 65-105; 10.1007/s00220-017-2973-z
Gosset, David; Mehta, Jenish C.; et el. (2017) QCMA
hardness of ground space connectivity for commuting Hamiltonians ;
Quantum; Vol. 1; 16; 10.22331/q-2017-07-14-16
Natarajan, Anand and Vidick, Thomas (2017) A
quantum linearity test for robustly verifying entanglement ; ISBN
978-1-4503-4528-6; Proceedings of the 49th Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2017; ACM: New York, NY; 1003-1015; 10.1145/3055399.3055468
Bavarian, Mohammad; Vidick, Thomas; et el. (2017) Hardness
amplification for entangled games via anchoring ; ISBN
978-1-4503-4528-6; Proceedings of the 49th Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2017; ACM: New York, NY; 303-316; 10.1145/3055399.3055433
Chao, Rui; Reichardt, Ben W.; et el. (2017) Overlapping
Qubits ; ISBN 9783959770293; 8th Innovations in Theoretical Computer
Science Conference (ITCS 2017); Dagstuhl Publishing: Wadern, Germany;
Art. No. 48; 10.4230/LIPIcs.ITCS.2017.48
Pironio, S.; Scarani, V.; et el. (2016) Focus
on device independent quantum information ; New Journal of Physics;
Vol. 18; No. 10; Art. No. 100202; 10.1088/1367-2630/18/10/100202
Vidick, Thomas (2016) Three-Player
Entangled XOR Games are NP-Hard to Approximate ; SIAM Journal on
Computing; Vol. 45; No. 3; 1007-1063; 10.1137/140956622
Anshu, Anurag; Arad, Itai; et el. (2016) A
simple proof of the detectability lemma and spectral gap
amplification ; Physical Review B; Vol. 93; No. 20; Art. No. 205142;
10.1103/PhysRevB.93.205142
Chung, Kai-Min; Cohen, Gil; et el. (2016) Quantum-Proof
Extractors: Optimal up to Constant Factors ; 10.48550/arXiv.1605.04194
Vidick, Thomas and Watrous, John (2016) Quantum
Proofs ; ISBN 978-1-68083-126-9; Foundations and Trends in
Theoretical Computer Science; Now Publishers: Boston, MA; 1-215; 10.1561/0400000068
Kempe, Julia and Vidick, Thomas (2016) On
the Power of Entangled Quantum Provers ; 10.48550/arXiv.0612063
Bavarian, Mohammad; Vidick, Thomas; et el. (2016) Anchoring
games for parallel repetition ; 10.48550/arXiv.1509.07466
Natarajan, Anand and Vidick, Thomas (2016) Constant-Soundness
Interactive Proofs for Local Hamiltonians ; 10.48550/arXiv.1512.02090
Arnon-Friedman, Rotem; Renner, Renato; et el. (2016) Non-Signaling
Parallel Repetition Using de Finetti Reductions ; IEEE Transactions
on Information Theory; Vol. 62; No. 3; 1440-1457; 10.1109/TIT.2016.2516022
Palazuelos, Carlos and Vidick, Thomas (2016) Survey
on nonlocal games and operator space theory ; Journal of Mathematical
Physics; Vol. 57; No. 1; Art. No. 015220; 10.1063/1.4938052
Mančinska, Laura and Vidick, Thomas (2015) Unbounded
entanglement in nonlocal games ; Quantum Information and Computation;
Vol. 15; No. 15-16; 1317-1332; 10.48550/arXiv.1402.4145
Regev, Oded and Vidick, Thomas (2015) Quantum
XOR Games ; ACM Transactions on Computation Theory; Vol. 7; No. 4;
Art. No. 15; 10.1145/2799560
Landau, Zeph; Vazirani, Umesh; et el. (2015) A
polynomial time algorithm for the ground state of one-dimensional gapped
local Hamiltonians ; Nature Physics; Vol. 11; No. 7; 566-569; 10.1038/nphys3345
Coudron, Matthew and Vidick, Thomas (2015) Interactive
Proofs with Approximately Commuting Provers ; ISBN 978-3-662-47671-0;
Automata, Languages, and Programming; Springer: Heidelberg; 355-366; 10.1007/978-3-662-47672-7_29
Dinur, Irit; Steurer, David; et el. (2015) A
parallel repetition theorem for entangled projection games ;
Computational Complexity; Vol. 24; No. 2; 201-254; 10.1007/s00037-015-0098-3
Fitzsimons, Joseph and Vidick, Thomas (2015) A
Multiprover Interactive Proof System for the Local Hamiltonian
Problem ; ISBN 978-1-4503-3333-7; ITCS’15 Innovations in Theoretical
Computer Science; Association for Computing Machinery: New York, NY;
103-112; 10.1145/2688073.2688094
Vazirani, Umesh and Vidick, Thomas (2014) Fully
Device-Independent Quantum Key Distribution ; Physical Review
Letters; Vol. 113; No. 14; Art. No. 140501; 10.1103/PhysRevLett.113.140501
Naor, Assaf; Regev, Oded; et el. (2014) Efficient
Rounding for the Noncommutative Grothendieck Inequality ; Theory of
Computing; Vol. 10; No. 1; 257-295; 10.4086/toc.2014.v010a011
Regev, Oded and Vidick, Thomas (2014) Elementary
Proofs of Grothendieck Theorems for Completely Bounded Norms ;
Journal of Operator Theory; Vol. 71; No. 2; 491-506; 10.7900/jot.2012jul02.1947
Dinur, Irit; Steurer, David; et el. (2014) A
parallel repetition theorem for entangled projection games ; ISBN
978-1-4799-3626-7; Proceedings of the Annual IEEE Conference on
Computational Complexity; IEEE: Piscataway, NJ; 197-208; 10.1109/CCC.2014.28
Landau, Zeph; Vazirani, Umesh; et el. (2014) An
efficient algorithm for finding the ground state of 1D gapped local
hamiltonians ; ISBN 978-1-4503-2698-8; Proceedings of the 5th
conference on Innovations in theoretical computer science; Association
for Computing Machinery: New York; 301; 10.1145/2554797.2554825
Vazirani, Umesh and Vidick, Thomas (2014) Robust
device independent quantum key distribution ; ISBN 978-1-4503-2698-8;
Proceedings of the 5th conference on Innovations in theoretical computer
science; Association for Computing Machinery: New York; 35-36; 10.1145/2554797.2554802
Mančinska, Laura and Vidick, Thomas (2014) Unbounded
Entanglement Can Be Needed to Achieve the Optimal Success
Probability ; ISBN 978-3-662-43947-0; Automata, Languages, and
Programming; Springer: Berlin; 835-846; 10.1007/978-3-662-43948-7_69
Vidick, Thomas (2013) Three-player
entangled XOR games are NP-hard to approximate ; ISBN
978-0-7695-5135-7; IEEE 54th Annual Symposium on Foundations of Computer
Science (FOCS); IEEE: Piscataway, NJ; 766-775; 10.1109/FOCS.2013.87
Briët, Jop and Vidick, Thomas (2013) Explicit
Lower and Upper Bounds on the Entangled Value of Multiplayer XOR
Games ; Communications in Mathematical Physics; Vol. 321; No. 1;
181-207; 10.1007/s00220-012-1642-5
Naor, Assaf; Regev, Oded; et el. (2013) Efficient
Rounding for the Noncommutative Grothendieck Inequality ; ISBN
978-1-4503-2029-0; Proceedings of the forty-fifth annual ACM symposium
on Theory of computing; ACM: New York, NY; 71-80; 10.1145/2488608.2488618
Aharonov, Dorit; Arad, Itai; et el. (2013) Guest
Column: The Quantum PCP Conjecture ; ACM SIGACT News; Vol. 44; No. 2;
47-79; 10.1145/2491533.2491549
Regev, Oded and Vidick, Thomas (2013) Quantum
XOR Games ; ISBN 978-0-7695-4997-2; 28th Annual IEEE Conference on
Computational Complexity (CCC); IEEE: Piscataway, NJ; 144-155; 10.1109/CCC.2013.23
Briët, Jop; Buhrman, Harry; et el. (2013) Multipartite
entanglement in XOR games ; Quantum Information and Computation; Vol.
13; No. 3-4; 334-360; 10.48550/arXiv.0911.4007
Molina, Abel; Vidick, Thomas; et el. (2013) Optimal
Counterfeiting Attacks and Generalizations for Wiesner’s Quantum
Money ; ISBN 978-3-642-35655-1; Theory of Quantum Computation,
Communication, and Cryptography; Springer: Berlin; 45-64; 10.1007/978-3-642-35656-8_4
Coudron, Matthew; Vidick, Thomas; et el. (2013) Robust
Randomness Amplifiers: Upper and Lower Bounds ; ISBN
978-3-642-40327-9; Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques; Springer: Berlin; 468-483; 10.1007/978-3-642-40328-6_33
Ito, Tsuyoshi and Vidick, Thomas (2012) A
Multi-prover Interactive Proof for NEXP Sound against Entangled
Provers ; ISBN 978-1-4673-4383-1; IEEE 53rd Annual Symposium on
Foundations of Computer Science (FOCS); IEEE: Piscataway, NJ; 243-252;
10.1109/FOCS.2012.11
De, Anindya; Portmann, Christopher; et el. (2012) Trevisan’s
Extractor in the Presence of Quantum Side Information ; SIAM Journal
on Computing; Vol. 41; No. 4; 915-940; 10.1137/100813683
Vazirani, Umesh and Vidick, Thomas (2012) Certifiable
quantum dice ; Philosophical Transactions A: Mathematical, Physical
and Engineering Sciences; Vol. 370; No. 1971; 3432-3448; 10.1098/rsta.2011.0336
Vidick, Thomas (2012) A
concentration inequality for the overlap of a vector on a large set,
with application to the communication complexity of the
Gap-Hamming-Distance problem ; Chicago Journal of Theoretical
Computer Science; Vol. 18; No. 1; 1-12; 10.4086/cjtcs.2012.001
Vazirani, Umesh and Vidick, Thomas (2012) Certifiable
Quantum Dice Or, True Random Number Generation Secure Against Quantum
Adversaries ; ISBN 978-1-4503-1245-5; STOC’12 Symposium on Theory of
Computing Conference; ACM: New York, NY; 61-76; 10.1145/2213977.2213984
Briët, Jop; Buhrman, Harry; et el. (2012) All
Schatten spaces endowed with the Schur product are Q-algebras ;
Journal of Functional Analysis; Vol. 262; No. 1; 1-9; 10.1016/j.jfa.2011.09.001
Vidick, Thomas and Wehner, Stephanie (2011) Does
Ignorance of the Whole Imply Ignorance of the Parts? Large Violations of
Noncontextuality in Quantum Theory ; Physical Review Letters; Vol.
107; No. 3; Art. No. 030402; 10.1103/PhysRevLett.107.030402
Kempe, Julia; Kobayashi, Hirotada; et el. (2011) Entangled
Games Are Hard to Approximate ; SIAM Journal on Computing; Vol. 40;
No. 3; 848-877; 10.1137/090751293
Kempe, Julia and Vidick, Thomas (2011) Parallel
Repetition of Entangled Games ; ISBN 978-1-4503-0691-1; Proceedings
of the 43rd annual ACM symposium on Theory of computing; ACM: New York,
NY; 353-362; 10.1145/1993636.1993684
Vidick, Thomas and Wehner, Stephanie (2011) More
nonlocality with less entanglement ; Physical Review A; Vol. 83;
No. 5; Art. No. 052310; 10.1103/PhysRevA.83.052310
De, Anindya and Vidick, Thomas (2010) Near-Optimal
Extractors Against Quantum Storage ; ISBN 978-1-4503-0050-6;
Proceedings of the 42nd ACM symposium on Theory of computing; ACM: New
York, NY; 161-170; 10.1145/1806689.1806713
Kempe, J. and Vidick, T. (2010) Quantum
Algorithms ; ISBN 978-3-642-11913-2; Quantum Information, Computation
and Cryptography: An Introductory Survey of Theory, Technology and
Experiments; Springer: Berlin; 309-342; 10.1007/978-3-642-11914-9_10
Brody, Joshua; Chakrabarti, Amit; et el. (2010) Better
Gap-Hamming Lower Bounds via Better Round Elimination ; ISBN
978-3-642-15368-6; Approximation, Randomization, and Combinatorial
Optimization. Algorithms and Techniques; Springer: Berlin; 476-489; 10.1007/978-3-642-15369-3_36
Kempe, Julia; Kobayashi, Hirotada; et el. (2009) Using
Entanglement in Quantum Multi-Prover Interactive Proofs ;
Computational Complexity; Vol. 18; No. 2; 273-307; 10.1007/s00037-009-0275-3
Ricotta, Guillaume and Vidick, Thomas (2008) Hauteur
asymptotique des points de Heegner ; Canadian Journal of Mathematics;
Vol. 60; No. 6; 1406-1436; 10.4153/CJM-2008-059-4
Kempe, Julia; Kobayashi, Hirotada; et el. (2008) Entangled
games are hard to approximate ; ISBN 978-0-7695-3436-7; 49th Annual
Symposium on Foundations-of-Computer-Science (FOCS); IEEE Computer
Society: Los Alamitos, CA; 447-456; 10.1109/FOCS.2008.8
Nguyen, Phong Q. and Vidick, Thomas (2008) Sieve
algorithms for the shortest vector problem are practical ; Journal of
Mathematical Cryptology; Vol. 2; No. 2; 181-207; 10.1515/jmc.2008.009
Kempe, Julia; Kobayashi, Hirotada; et el. (2008) Using
Entanglement in Quantum Multi-Prover Interactive Proofs ; ISBN
978-0-7695-3169-4; 23rd Annual IEEE Conference on Computational
Complexity; IEEE: Piscataway, NJ; 211-222; 10.1109/CCC.2008.6