Chicago Journal of Theoretical Computer Science Short Title: Chic. J. Theor. Comput. Sci. Publisher: University of Chicago, Department of Computer Science, Chicago, IL ISSN: 1073-0486/e Online: http://cjtcs.cs.uchicago.edu/index.html Comments: Journal; Indexed cover-to-cover; Published electronic only as of 1995. This journal is available open access. Documents Indexed: 143 Publications (since 1995) References Indexed: 41 Publications with 833 References. all top 5 Latest Issues 2023 (2023) 2022 (2022) 2020 (2020) 2019 (2019) 2018 (2018) 2017 (2017) 2016 (2016) 2015 (2015) 2014 (2014) 2013 (2013) 2012 (2012) 2011, Spec. Iss. (2011) 2010, Spec. Iss. (2010) 2009 (2009) 2008 (2008) 2007 (2007) 2006 (2006) 2005 (2005) 2002 (2002) 2000 (2000) 1999 (1999) 1998 (1998) 1997 (1997) 1996 (1996) 1995 (1995) all top 5 Authors 5 Mahajan, Meena 3 Allender, Eric W. 3 Arvind, Vikraman 3 Haviv, Ishay 3 Lindell, Yehuda 3 Montanaro, Ashley 3 Regev, Oded 3 Thierauf, Thomas 3 Vardi, Moshe Ya’akov 3 Watrous, John 2 Arora, Anish 2 Cameron, Peter Jephson 2 Chattopadhyay, Arkadev 2 de Wolf, Ronald Michiel 2 Diakonikolas, Ilias 2 Dujmović, Vida 2 Fairbairn, Ben Thomas 2 Feigenbaum, Joan 2 Gadouleau, Maxmilien 2 Gavinsky, Dmitry 2 Green, Frederic 2 Gur, Tom 2 Gutoski, Gus 2 Kobayashi, Hirotada 2 Kulkarni, Raghav 2 Le Gall, François 2 Malod, Guillaume 2 Manyem, Prabhu 2 Matsumoto, Keiji 2 Santha, Miklos 2 Saurabh, Nitin 2 Sikora, Jamie 2 Tani, Seiichiro 2 Vollmer, Heribert 1 Aaronson, Scott 1 Afek, Yehuda 1 Agarwal, Naman 1 Aggarwal, Divesh 1 Agrawal, Manindra 1 Agrawal, Rohit 1 Aiello, William A. 1 Ailon, Nir 1 Ajtai, Miklós 1 Amano, Kazuyuki 1 Bacon, Dave Morris 1 Bazzi, Louay M. J. 1 Beals, Robert M. 1 Beauquier, Joffroy 1 Ben-Amram, Amir M. 1 Ben-Aroya, Avraham 1 Bläser, Markus 1 Borchert, Bernd 1 Brakensiek, Joshua 1 Bremler, Anat 1 Buhrman, Harry 1 Buntrock, Gerhard 1 Busch, Costas 1 Çapuni, Ilir 1 Chailloux, André 1 Chalermsook, Parinya 1 Chan, Sze-Hang 1 Chang, Richard 1 Chatterjee, Abhranil 1 Chiesa, Alessandro 1 Childs, Andrew M. 1 Christandl, Matthias 1 Christensen, Niels H. 1 Chubb, Christopher T. 1 Cidon, Israel 1 Collin, Zeev 1 Condon, Anne E. 1 Datta, Ajoy Kumar 1 Datta, Rajit 1 Datta, Samir 1 Davie, George 1 Davis, Joshua R. 1 Day, Adam R. 1 de Beaudrap, Niel 1 de Rugy-Altherre, Nicolas 1 Dechter, Rina 1 Dolev, Shlomi 1 Downey, Rodney Graham 1 Durand, Arnaud 1 Erickson, Jeff 1 Faragó, András 1 Farzad, Babak 1 Feige, Uriel 1 Fenner, Stephen A. 1 Filmus, Yuval 1 Flammia, Steven T. 1 Forbes, Michael A. 1 Friedman, Luke 1 Gacs, Peter 1 Galbraith, Steven D. 1 Ganguly, Sumit 1 García-Soriano, David 1 Gasarch, William Ian 1 Gerstel, Ornan 1 Goldreich, Oded 1 Golovkins, Marats ...and 176 more Authors all top 5 Fields 125 Computer science (68-XX) 19 Combinatorics (05-XX) 17 Information and communication theory, circuits (94-XX) 11 Quantum theory (81-XX) 7 Order, lattices, ordered algebraic structures (06-XX) 6 Operations research, mathematical programming (90-XX) 6 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 5 Mathematical logic and foundations (03-XX) 5 Linear and multilinear algebra; matrix theory (15-XX) 3 Group theory and generalizations (20-XX) 3 Probability theory and stochastic processes (60-XX) 2 General and overarching topics; collections (00-XX) 2 Numerical analysis (65-XX) 1 General algebraic systems (08-XX) 1 Number theory (11-XX) 1 Measure and integration (28-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Statistics (62-XX) 1 Statistical mechanics, structure of matter (82-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 98 Publications have been cited 647 times in 612 Documents Cited by ▼ Year ▼ Fast C-K-R partitions of sparse graphs. Zbl 1286.68373 Mendel, Manor; Schwob, Chaya 96 2009 Superstabilizing protocols for dynamic systems. Zbl 0924.68005 Dolev, Shlomi; Herman, Ted 34 1997 Satisfiability coding lemma. Zbl 0940.68049 Paturi, Ramamohan; Pudlak, Pavel; Zane, Francis 32 1999 Determinant: Combinatorics, algorithms, and complexity. Zbl 0924.68088 Mahajan, Meena; Vinay, V. 32 1997 Quantum Boolean functions. Zbl 1286.68161 Montanaro, Ashley; Osborne, Tobias J. 18 2010 Notes on large angle crossing graphs. Zbl 1286.05034 Dujmović, Vida; Gudmundsson, Joachim; Morin, Pat; Wolle, Thomas 18 2011 Friedgut-Kalai-Naor theorem for slices of the Boolean cube. Zbl 1401.06014 Filmus, Yuval 18 2016 On the hardness of approximating Max \(k\)-Cut and its dual. Zbl 0924.68013 Kann, Viggo; Khanna, Sanjeev; Lagergren, Jens; Panconesi, Alessandro 17 1997 The permanent requires large uniform threshold circuits. Zbl 0924.68091 Allender, Eric 16 1999 A priority-based model of routing. Zbl 1286.68227 Farzad, Babak; Olver, Neil; Vetta, Adrian 14 2008 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. Zbl 1286.68364 Vidick, Thomas 13 2012 The non-adaptive query complexity of testing \(k\)-parities. Zbl 1286.68487 Buhrman, Harry; García-Soriano, David; Matsliah, Arie; de Wolf, Ronald 11 2013 Coherent state exchange in multi-prover quantum interactive proof systems. Zbl 1286.68157 Leung, Debbie; Toner, Ben; Watrous, John 10 2013 Self-stabilization unidirectional network algorithms by power supply. Zbl 0924.68093 Afek, Yehuda; Bremler, Anat 10 1998 Simpler semidefinite programs for completely bounded norms. Zbl 1286.81036 Watrous, John 9 2013 On fractional block sensitivity. Zbl 1365.68288 Kulkarni, Raghav; Tal, Avishay 9 2016 Probabilistically checkable debate systems and nonapproximability of PSPACE hard functions. Zbl 0924.68177 Condon, Anne; Feigenbaum, Joan; Lund, Carsten; Shor, Peter W. 9 1995 On limited versus polynomial nondeterminism. Zbl 0924.68080 Feige, Uriel; Kilian, Joe 9 1997 Best effort and priority queuing policies for buffered crossbar switches. Zbl 1286.68009 Kesselman, Alex; Kogan, Kirill; Segal, Michael 8 2012 Complexity of problems on graphs represented as OBDDs. Zbl 0924.68097 Feigenbaum, Joan; Kannan, Sampath; Vardi, Moshe Y.; Viswanathan, Mahesh 8 1999 Lower bounds for linear satisfiability problems. Zbl 0924.68001 Erickson, Jeff 8 1999 Universal locally testable codes. Zbl 1426.94159 Goldreich, Oded; Gur, Tom 8 2018 Some lower bound results for set-multilinear arithmetic computations. Zbl 1358.68109 Arvind, V.; Raja, S. 8 2016 Hardness of the covering radius problem on lattices. Zbl 1286.68192 Haviv, Ishay; Regev, Oded 7 2012 Computing the degenerate ground space of gapped spin chains in polynomial time. Zbl 1369.68211 Chubb, Christopher T.; Flammia, Steven T. 7 2016 Time bounds for strong and hybrid consistency for arbitrary abstract data types. Zbl 0924.68081 Kosa, Martha J. 7 1999 Collision-based testers are optimal for uniformity and closeness. Zbl 1441.62068 Diakonikolas, Ilias; Gouleakis, Themis; Peebles, John; Price, Eric 7 2019 Layouts of expander graphs. Zbl 1347.68282 Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. 6 2016 Computing in permutation groups without memory. Zbl 1319.68090 Cameron, Peter J.; Fairbairn, Ben; Gadouleau, Maxmilien 6 2014 Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction. Zbl 1390.91030 Lancien, Cécilia; Winter, Andreas 6 2016 Optimal measurements for the dihedral hidden subgroup problem. Zbl 1117.81010 Bacon, Dave; Childs, Andrew M.; van Dam, Wim 6 2006 Self-stabilizing local mutual exclusion and daemon refinement. Zbl 1025.68110 Beauquier, Joffroy; Datta, Ajoy K.; Gradinariu, Maria; Magniette, Frederic 6 2002 Nonnegative rank vs. binary rank. Zbl 1356.68085 Watson, Thomas 6 2016 On the weak \(\text{mod } m\) representation of Boolean functions. Zbl 0922.06014 Grolmusz, Vince 6 1995 \(d\)-collapsibility is NP-complete for \(d \geq 4\). Zbl 1286.68210 Tancer, Martin 5 2010 Optimal bounds for semi-honest quantum oblivious transfer. Zbl 1388.94039 Chailloux, André; Gutoski, Gus; Sikora, Jamie 5 2016 Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. Zbl 1337.68119 Varma, Girish 5 2015 On deciding the existence of perfect entangled strategies for nonlocal games. Zbl 1341.91021 Mančinska, Laura; Roberson, David E.; Varvisotis, Antonios 5 2016 Non-commutative computations: lower bounds and polynomial identity testing. Zbl 1422.68070 Lagarde, Guillaume; Malod, Guillaume; Perifel, Sylvain 5 2019 The isomorphism problem for read-once branching programs and arithmetic circuits. Zbl 0924.68096 Thierauf, Thomas 5 1998 Some perfect matchings and perfect half-integral matchings in NC. Zbl 1286.05052 Kulkarni, Raghav; Mahajan, Meena; Varadarajan, Kasturi R. 4 2008 Efficient fully-simulatable oblivious transfer. Zbl 1286.68020 Lindell, Yehuda 4 2008 Learning graph based quantum query algorithms for finding constant-size subgraphs. Zbl 1286.68155 Lee, Troy; Magniez, Frédéric; Santha, Miklos 4 2012 A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy. Zbl 1286.68171 Ailon, Nir 4 2013 A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062 Aggarwal, Divesh; Regev, Oded 4 2016 Supporting increment and decrement operations in balancing networks. Zbl 0969.68004 Aiello, William; Busch, Costas; Herlihy, Maurice; Mavronicolas, Marios; Shavit, Nir; Touitou, Dan 4 2000 Orthogonal accuracy clock synchronization. Zbl 0970.68191 Schmid, Ulrich 4 2000 Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019 Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald 3 2008 Varieties generated by certain models of reversible finite automata. Zbl 1286.68333 Golovkins, Marats; Pin, Jean-Eric 3 2010 On process complexity. Zbl 1286.68250 Day, Adam R. 3 2010 Longest paths in planar DAGs in unambiguous log-space. Zbl 1286.68240 Limaye, Nutan; Mahajan, Meena; Nimbhorkar, Prajakta 3 2010 Interactive proofs with efficient quantum prover for recursive Fourier sampling. Zbl 1286.68158 McKague, Matthew 3 2012 Improved soundness for QMA with multiple provers. Zbl 1286.68150 Chiesa, Alessandro; Forbes, Michael A. 3 2013 A note on subspace evasive sets. Zbl 1396.05111 Ben-Aroya, Avraham; Shinkar, Igor 3 2014 Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent. Zbl 1388.68138 Yao, Penghui 3 2016 Self-stabilizing distributed constraint satisfaction. Zbl 0940.68002 Collin, Zeev; Dechter, Rina; Katz, Shmuel 3 1999 Unique reconstruction threshold for random jigsaw puzzles. Zbl 1375.05176 Nenadov, Rajko; Pfister, Pascal; Steger, Angelika 3 2017 Homomorphism polynomials complete for VP. Zbl 1356.68080 Durand, Arnaud; Mahajan, Meena; Malod, Guillaume; De Rugy-Altherre, Nicolas; Saurabh, Nitin 3 2016 QMA with subset state witnesses. Zbl 1356.68081 Grilo, Alex Bredariol; Kerenidis, Iordanis; Sikora, Jamie 3 2016 Optimal virtual path layout in ATM networks with shared routing tables switches. Zbl 0924.68003 Gerstel, Ornan; Cidon, Israel; Zaks, Shmuel 3 1996 Verification of fair transition systems. Zbl 0924.68124 Kupferman, Orna; Vardi, Moshe Y. 3 1998 On finding the number of graph automorphisms. Zbl 0924.68098 Beals, Robert; Chang, Richard; Gasarch, William; Torán, Jacobo 3 1999 A composition theorem for decision tree complexity. Zbl 1372.68102 Montanaro, Ashley 3 2014 Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations. Zbl 1472.94051 Galbraith, Steven D.; Laity, Joel; Shani, Barak 2 2018 Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur? Zbl 1286.68154 Kobayashi, Hirotada; Matsumoto, Keiji; Yamakami, Tomoyuki 2 2009 An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs. Zbl 1286.68531 Matsubara, Wataru; Inenaga, Shunsuke; Shinohara, Ayumi 2 2010 Single-query learning from abelian and non-abelian Hamming distance oracles. Zbl 1286.68159 Meyer, David A.; Pommersheim, James 2 2010 \(k\)-cographs are Kruskalian. Zbl 1286.05143 Hung, Ling-Ju; Kloks, Ton 2 2011 A Turing machine resisting isolated bursts of faults. Zbl 1286.68121 Çapuni, Ilir; Gács, Peter 2 2013 Computing in matrix groups without memory. Zbl 1319.68091 Cameron, Peter J.; Fairbairn, Ben; Gadouleau, Maxmilien 2 2014 Unique games on the hypercube. Zbl 1336.68092 Agarwal, Naman; Kindler, Guy; Kolla, Alexandra; Trevisan, Luca 2 2015 Hopfield neural networks and self-stabilization. Zbl 0924.68156 Jagota, Arun 2 1999 Lower bounds for linear decision lists. Zbl 1503.68076 Chattopadhyay, Arkadev; Mahajan, Meena; Mande, Nikhil; Saurabh, Nitin 2 2020 On monotone circuits with local oracles and clique lower bounds. Zbl 1398.68163 Krajíček, Jan; Oliveira, Igor C. 2 2018 Symmetric Logspace is closed under complement. Zbl 0924.68039 Nisan, Noam; Ta-Shma, Amnon 2 1995 Rabin measures. Zbl 0924.68142 Klarlund, Nils; Kozen, Dexter 2 1995 Manhattan channel routing is NP-complete under truly restricted settings. Zbl 0924.68087 Middendorf, Martin 2 1996 Multitolerance in distributed reset. Zbl 0924.68006 Kulkarni, Sandeep S.; Arora, Anish 2 1998 Complements of multivalued functions. Zbl 0924.68089 Fenner, Stephen; Green, Frederic; Homer, Steven; Selman, Alan L.; Thierauf, Thomas; Vollmer, Heribert 2 1999 Lift-and-project integrality gaps for the traveling salesperson problem. Zbl 1366.90187 Watson, Thomas 2 2014 Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace. Zbl 1391.68061 Thierauf, Thomas; Wagner, Fabian 2 2014 Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction. Zbl 1372.68293 Huber, Mark 2 2014 Quantum adversary lower bound for element distinctness with small range. Zbl 1372.68108 Rosmanis, Ansis 2 2014 Approximating the orthogonality imension of graphs and hypergraphs. Zbl 07639160 Haviv, Ishay 2 2022 \(H\)-wise independence. Zbl 1436.68395 Haviv, Ishay; Langberg, Michael 1 2019 Computation at a distance. Zbl 1286.68202 Kutin, Samuel A.; Moulton, David Petrie; Smithline, Lawren M. 1 2007 Syntactic characterizations of polynomial time optimization classes. Zbl 1286.68216 Manyem, Prabhu 1 2008 On the structure of classes of random graphs. Zbl 1286.68371 Faragó, András 1 2010 Edge-selection heuristics for computing Tutte polynomials. Zbl 1286.05073 Pearce, David J.; Haggard, Gary; Royle, Gordon 1 2010 An algorithm for affine approximation of binary decision diagrams. Zbl 1286.06024 Henshall, Kevin; Schachte, Peter; Søndergaard, Harald; Whiting, Leigh 1 2010 On quantum interactive proofs with short messages. Zbl 1286.68162 Pereszlényi, Attila 1 2012 Complexity of the homomorphism extension problem in the random case. Zbl 1286.68198 Kazda, Alexandr 1 2013 Testing Booleanity and the uncertainty principle. Zbl 1286.68490 Gur, Tom; Tamuz, Omer 1 2013 On Ajtai’s lower bound technique for \(R\)-way branching programs and the Hamming distance problem. Zbl 1119.68085 Pagter, Jakob 1 2005 Protocols for bounded-concurrent secure two-party computation in the plain model. Zbl 1176.94068 Lindell, Yehuda 1 2006 The communication complexity of the inevitable intersection problem. Zbl 1503.68073 Gavinsky, Dmitry 1 2020 Quantum algorithms for matrix products over semirings. Zbl 1375.68056 Le Gall, François; Nishimura, Harumichi 1 2017 Sparse hard sets for \(P\) yield space-efficient algorithms. Zbl 0924.68092 Ogihara, Mitsunori 1 1996 Approximating the orthogonality imension of graphs and hypergraphs. Zbl 07639160 Haviv, Ishay 2 2022 Lower bounds for linear decision lists. Zbl 1503.68076 Chattopadhyay, Arkadev; Mahajan, Meena; Mande, Nikhil; Saurabh, Nitin 2 2020 The communication complexity of the inevitable intersection problem. Zbl 1503.68073 Gavinsky, Dmitry 1 2020 Collision-based testers are optimal for uniformity and closeness. Zbl 1441.62068 Diakonikolas, Ilias; Gouleakis, Themis; Peebles, John; Price, Eric 7 2019 Non-commutative computations: lower bounds and polynomial identity testing. Zbl 1422.68070 Lagarde, Guillaume; Malod, Guillaume; Perifel, Sylvain 5 2019 \(H\)-wise independence. Zbl 1436.68395 Haviv, Ishay; Langberg, Michael 1 2019 Universal locally testable codes. Zbl 1426.94159 Goldreich, Oded; Gur, Tom 8 2018 Finding significant Fourier coefficients: clarifications, simplifications, applications and limitations. Zbl 1472.94051 Galbraith, Steven D.; Laity, Joel; Shani, Barak 2 2018 On monotone circuits with local oracles and clique lower bounds. Zbl 1398.68163 Krajíček, Jan; Oliveira, Igor C. 2 2018 Unique reconstruction threshold for random jigsaw puzzles. Zbl 1375.05176 Nenadov, Rajko; Pfister, Pascal; Steger, Angelika 3 2017 Quantum algorithms for matrix products over semirings. Zbl 1375.68056 Le Gall, François; Nishimura, Harumichi 1 2017 Friedgut-Kalai-Naor theorem for slices of the Boolean cube. Zbl 1401.06014 Filmus, Yuval 18 2016 On fractional block sensitivity. Zbl 1365.68288 Kulkarni, Raghav; Tal, Avishay 9 2016 Some lower bound results for set-multilinear arithmetic computations. Zbl 1358.68109 Arvind, V.; Raja, S. 8 2016 Computing the degenerate ground space of gapped spin chains in polynomial time. Zbl 1369.68211 Chubb, Christopher T.; Flammia, Steven T. 7 2016 Layouts of expander graphs. Zbl 1347.68282 Dujmović, Vida; Sidiropoulos, Anastasios; Wood, David R. 6 2016 Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction. Zbl 1390.91030 Lancien, Cécilia; Winter, Andreas 6 2016 Nonnegative rank vs. binary rank. Zbl 1356.68085 Watson, Thomas 6 2016 Optimal bounds for semi-honest quantum oblivious transfer. Zbl 1388.94039 Chailloux, André; Gutoski, Gus; Sikora, Jamie 5 2016 On deciding the existence of perfect entangled strategies for nonlocal games. Zbl 1341.91021 Mančinska, Laura; Roberson, David E.; Varvisotis, Antonios 5 2016 A note on discrete Gaussian combinations of lattice vectors. Zbl 1375.60062 Aggarwal, Divesh; Regev, Oded 4 2016 Parity decision tree complexity and 4-party communication complexity of XOR-functions are polynomially equivalent. Zbl 1388.68138 Yao, Penghui 3 2016 Homomorphism polynomials complete for VP. Zbl 1356.68080 Durand, Arnaud; Mahajan, Meena; Malod, Guillaume; De Rugy-Altherre, Nicolas; Saurabh, Nitin 3 2016 QMA with subset state witnesses. Zbl 1356.68081 Grilo, Alex Bredariol; Kerenidis, Iordanis; Sikora, Jamie 3 2016 Reducing uniformity in Khot-Saket hypergraph coloring hardness reductions. Zbl 1337.68119 Varma, Girish 5 2015 Unique games on the hypercube. Zbl 1336.68092 Agarwal, Naman; Kindler, Guy; Kolla, Alexandra; Trevisan, Luca 2 2015 Computing in permutation groups without memory. Zbl 1319.68090 Cameron, Peter J.; Fairbairn, Ben; Gadouleau, Maxmilien 6 2014 A note on subspace evasive sets. Zbl 1396.05111 Ben-Aroya, Avraham; Shinkar, Igor 3 2014 A composition theorem for decision tree complexity. Zbl 1372.68102 Montanaro, Ashley 3 2014 Computing in matrix groups without memory. Zbl 1319.68091 Cameron, Peter J.; Fairbairn, Ben; Gadouleau, Maxmilien 2 2014 Lift-and-project integrality gaps for the traveling salesperson problem. Zbl 1366.90187 Watson, Thomas 2 2014 Reachability in \(K_{3,3}\)-free and \(K_5\)-free graphs is in unambiguous logspace. Zbl 1391.68061 Thierauf, Thomas; Wagner, Fabian 2 2014 Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction. Zbl 1372.68293 Huber, Mark 2 2014 Quantum adversary lower bound for element distinctness with small range. Zbl 1372.68108 Rosmanis, Ansis 2 2014 The non-adaptive query complexity of testing \(k\)-parities. Zbl 1286.68487 Buhrman, Harry; García-Soriano, David; Matsliah, Arie; de Wolf, Ronald 11 2013 Coherent state exchange in multi-prover quantum interactive proof systems. Zbl 1286.68157 Leung, Debbie; Toner, Ben; Watrous, John 10 2013 Simpler semidefinite programs for completely bounded norms. Zbl 1286.81036 Watrous, John 9 2013 A lower bound for Fourier transform computation in a linear model over \(2\times 2\) unitary gates using matrix entropy. Zbl 1286.68171 Ailon, Nir 4 2013 Improved soundness for QMA with multiple provers. Zbl 1286.68150 Chiesa, Alessandro; Forbes, Michael A. 3 2013 A Turing machine resisting isolated bursts of faults. Zbl 1286.68121 Çapuni, Ilir; Gács, Peter 2 2013 Complexity of the homomorphism extension problem in the random case. Zbl 1286.68198 Kazda, Alexandr 1 2013 Testing Booleanity and the uncertainty principle. Zbl 1286.68490 Gur, Tom; Tamuz, Omer 1 2013 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. Zbl 1286.68364 Vidick, Thomas 13 2012 Best effort and priority queuing policies for buffered crossbar switches. Zbl 1286.68009 Kesselman, Alex; Kogan, Kirill; Segal, Michael 8 2012 Hardness of the covering radius problem on lattices. Zbl 1286.68192 Haviv, Ishay; Regev, Oded 7 2012 Learning graph based quantum query algorithms for finding constant-size subgraphs. Zbl 1286.68155 Lee, Troy; Magniez, Frédéric; Santha, Miklos 4 2012 Interactive proofs with efficient quantum prover for recursive Fourier sampling. Zbl 1286.68158 McKague, Matthew 3 2012 On quantum interactive proofs with short messages. Zbl 1286.68162 Pereszlényi, Attila 1 2012 Notes on large angle crossing graphs. Zbl 1286.05034 Dujmović, Vida; Gudmundsson, Joachim; Morin, Pat; Wolle, Thomas 18 2011 \(k\)-cographs are Kruskalian. Zbl 1286.05143 Hung, Ling-Ju; Kloks, Ton 2 2011 Quantum Boolean functions. Zbl 1286.68161 Montanaro, Ashley; Osborne, Tobias J. 18 2010 \(d\)-collapsibility is NP-complete for \(d \geq 4\). Zbl 1286.68210 Tancer, Martin 5 2010 Varieties generated by certain models of reversible finite automata. Zbl 1286.68333 Golovkins, Marats; Pin, Jean-Eric 3 2010 On process complexity. Zbl 1286.68250 Day, Adam R. 3 2010 Longest paths in planar DAGs in unambiguous log-space. Zbl 1286.68240 Limaye, Nutan; Mahajan, Meena; Nimbhorkar, Prajakta 3 2010 An efficient algorithm to test square-freeness of strings compressed by balanced straight line programs. Zbl 1286.68531 Matsubara, Wataru; Inenaga, Shunsuke; Shinohara, Ayumi 2 2010 Single-query learning from abelian and non-abelian Hamming distance oracles. Zbl 1286.68159 Meyer, David A.; Pommersheim, James 2 2010 On the structure of classes of random graphs. Zbl 1286.68371 Faragó, András 1 2010 Edge-selection heuristics for computing Tutte polynomials. Zbl 1286.05073 Pearce, David J.; Haggard, Gary; Royle, Gordon 1 2010 An algorithm for affine approximation of binary decision diagrams. Zbl 1286.06024 Henshall, Kevin; Schachte, Peter; Søndergaard, Harald; Whiting, Leigh 1 2010 Fast C-K-R partitions of sparse graphs. Zbl 1286.68373 Mendel, Manor; Schwob, Chaya 96 2009 Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur? Zbl 1286.68154 Kobayashi, Hirotada; Matsumoto, Keiji; Yamakami, Tomoyuki 2 2009 A priority-based model of routing. Zbl 1286.68227 Farzad, Babak; Olver, Neil; Vetta, Adrian 14 2008 Some perfect matchings and perfect half-integral matchings in NC. Zbl 1286.05052 Kulkarni, Raghav; Mahajan, Meena; Varadarajan, Kasturi R. 4 2008 Efficient fully-simulatable oblivious transfer. Zbl 1286.68020 Lindell, Yehuda 4 2008 Simultaneous communication protocols with quantum and classical messages. Zbl 1286.68019 Gavinsky, Dmitry; Regev, Oded; de Wolf, Ronald 3 2008 Syntactic characterizations of polynomial time optimization classes. Zbl 1286.68216 Manyem, Prabhu 1 2008 Computation at a distance. Zbl 1286.68202 Kutin, Samuel A.; Moulton, David Petrie; Smithline, Lawren M. 1 2007 Optimal measurements for the dihedral hidden subgroup problem. Zbl 1117.81010 Bacon, Dave; Childs, Andrew M.; van Dam, Wim 6 2006 Protocols for bounded-concurrent secure two-party computation in the plain model. Zbl 1176.94068 Lindell, Yehuda 1 2006 On Ajtai’s lower bound technique for \(R\)-way branching programs and the Hamming distance problem. Zbl 1119.68085 Pagter, Jakob 1 2005 Self-stabilizing local mutual exclusion and daemon refinement. Zbl 1025.68110 Beauquier, Joffroy; Datta, Ajoy K.; Gradinariu, Maria; Magniette, Frederic 6 2002 Supporting increment and decrement operations in balancing networks. Zbl 0969.68004 Aiello, William; Busch, Costas; Herlihy, Maurice; Mavronicolas, Marios; Shavit, Nir; Touitou, Dan 4 2000 Orthogonal accuracy clock synchronization. Zbl 0970.68191 Schmid, Ulrich 4 2000 Satisfiability coding lemma. Zbl 0940.68049 Paturi, Ramamohan; Pudlak, Pavel; Zane, Francis 32 1999 The permanent requires large uniform threshold circuits. Zbl 0924.68091 Allender, Eric 16 1999 Complexity of problems on graphs represented as OBDDs. Zbl 0924.68097 Feigenbaum, Joan; Kannan, Sampath; Vardi, Moshe Y.; Viswanathan, Mahesh 8 1999 Lower bounds for linear satisfiability problems. Zbl 0924.68001 Erickson, Jeff 8 1999 Time bounds for strong and hybrid consistency for arbitrary abstract data types. Zbl 0924.68081 Kosa, Martha J. 7 1999 Self-stabilizing distributed constraint satisfaction. Zbl 0940.68002 Collin, Zeev; Dechter, Rina; Katz, Shmuel 3 1999 On finding the number of graph automorphisms. Zbl 0924.68098 Beals, Robert; Chang, Richard; Gasarch, William; Torán, Jacobo 3 1999 Hopfield neural networks and self-stabilization. Zbl 0924.68156 Jagota, Arun 2 1999 Complements of multivalued functions. Zbl 0924.68089 Fenner, Stephen; Green, Frederic; Homer, Steven; Selman, Alan L.; Thierauf, Thomas; Vollmer, Heribert 2 1999 Self-stabilization unidirectional network algorithms by power supply. Zbl 0924.68093 Afek, Yehuda; Bremler, Anat 10 1998 The isomorphism problem for read-once branching programs and arithmetic circuits. Zbl 0924.68096 Thierauf, Thomas 5 1998 Verification of fair transition systems. Zbl 0924.68124 Kupferman, Orna; Vardi, Moshe Y. 3 1998 Multitolerance in distributed reset. Zbl 0924.68006 Kulkarni, Sandeep S.; Arora, Anish 2 1998 Superstabilizing protocols for dynamic systems. Zbl 0924.68005 Dolev, Shlomi; Herman, Ted 34 1997 Determinant: Combinatorics, algorithms, and complexity. Zbl 0924.68088 Mahajan, Meena; Vinay, V. 32 1997 On the hardness of approximating Max \(k\)-Cut and its dual. Zbl 0924.68013 Kann, Viggo; Khanna, Sanjeev; Lagergren, Jens; Panconesi, Alessandro 17 1997 On limited versus polynomial nondeterminism. Zbl 0924.68080 Feige, Uriel; Kilian, Joe 9 1997 Optimal virtual path layout in ATM networks with shared routing tables switches. Zbl 0924.68003 Gerstel, Ornan; Cidon, Israel; Zaks, Shmuel 3 1996 Manhattan channel routing is NP-complete under truly restricted settings. Zbl 0924.68087 Middendorf, Martin 2 1996 Sparse hard sets for \(P\) yield space-efficient algorithms. Zbl 0924.68092 Ogihara, Mitsunori 1 1996 Probabilistically checkable debate systems and nonapproximability of PSPACE hard functions. Zbl 0924.68177 Condon, Anne; Feigenbaum, Joan; Lund, Carsten; Shor, Peter W. 9 1995 On the weak \(\text{mod } m\) representation of Boolean functions. Zbl 0922.06014 Grolmusz, Vince 6 1995 Symmetric Logspace is closed under complement. Zbl 0924.68039 Nisan, Noam; Ta-Shma, Amnon 2 1995 Rabin measures. Zbl 0924.68142 Klarlund, Nils; Kozen, Dexter 2 1995 all cited Publications top 5 cited Publications all top 5 Cited by 1,079 Authors 10 Gur, Tom 8 Datta, Samir 8 Devismes, Stéphane 8 Filmus, Yuval 7 Limaye, Nutan 7 Lovett, Shachar 7 Tixeuil, Sébastien 6 Datta, Ajoy Kumar 6 Didimo, Walter 6 Dolev, Shlomi 6 Srinivasan, Srikanth 5 Ambainis, Andris 5 Dujmović, Vida 5 Göös, Mika 5 Impagliazzo, Russell 5 Larmore, Lawrence L. 5 Le Gall, François 5 Liotta, Giuseppe 5 Palazuelos, Carlos 5 Paturi, Ramamohan 5 Raghavendra Rao, B. V. 5 Rothblum, Ron D. 5 Santha, Miklos 5 Vidick, Thomas 5 Watson, Thomas 5 Williams, Richard Ryan 5 Wood, David Ronald 4 Ailon, Nir 4 Allender, Eric W. 4 Bshouty, Nader H. 4 Eppstein, David Arthur 4 Gadouleau, Maximilien 4 Gavinsky, Dmitry 4 Goldreich, Oded 4 Guruswami, Venkatesan 4 Harsha, Prahladh 4 Haviv, Ishay 4 Hirsch, Edward A. 4 Kaufmann, Michael 4 Kogan, Kirill 4 Kumar, Mrinal 4 Lee, Troy 4 Lipton, Richard Jay 4 Mahajan, Meena 4 Meka, Raghu 4 Mirrokni, Vahab S. 4 Nikolenko, Sergey I. 4 Okamoto, Yoshio 4 Schmid, Ulrich 4 Sirotkin, Aleksandr Vladimirovich 4 Talebanfard, Navid 4 Talmage, Edward 4 Volk, Ben Lee 4 Yaroslavtsev, Grigory 3 Altisen, Karine 3 Andoni, Alexandr 3 Ben-David, Shalev 3 Busch, Costas 3 Calabro, Chris 3 Chattopadhyay, Arkadev 3 Das, Shagnik 3 de Jong, Jasper 3 Di Giacomo, Emilio 3 Dinur, Irit 3 Flammia, Steven T. 3 Ghosh, Sukumar 3 Harrow, Aram Wettroth 3 Herman, Ted 3 Huang, Xiuzhen 3 Kamei, Sayaka 3 Kanj, Iyad A. 3 Kawarabayashi, Ken-ichi 3 Kheddouci, Hamamache 3 Kobayashi, Koji M. 3 Kontinen, Juha 3 Kulkarni, Raghav 3 Lagarde, Guillaume 3 Mavronicolas, Marios 3 Morin, Pat 3 Nishimura, Harumichi 3 O’Donnell, Ryan 3 Petit, Franck 3 Ramya, C. 3 Razenshteyn, Ilya P. 3 Regev, Oded 3 Richard, Adrien 3 Sanyal, Swagato 3 Scheideler, Christian 3 Schröder, Marc 3 Sikora, Jamie 3 Tamaki, Suguru 3 Thierauf, Thomas 3 Thorup, Mikkel 3 Uetz, Marc 3 Vaikuntanathan, Vinod 3 Vihrovs, Jevgēnijs 3 Welch, Jennifer Lundelius 3 Wigderson, Avi 2 Aaronson, Scott 2 Aggarwal, Divesh ...and 979 more Authors all top 5 Cited in 107 Journals 63 Theoretical Computer Science 23 Algorithmica 23 Computational Complexity 20 SIAM Journal on Computing 20 Theory of Computing Systems 19 Information Processing Letters 18 Journal of Computer and System Sciences 13 Information and Computation 13 Distributed Computing 12 Discrete Applied Mathematics 12 Journal of Mathematical Physics 10 Quantum Information Processing 7 Communications in Mathematical Physics 6 Theory of Computing 5 Combinatorica 5 Discrete & Computational Geometry 5 SIAM Journal on Discrete Mathematics 4 Mathematical Programming. Series A. Series B 4 The Electronic Journal of Combinatorics 3 Artificial Intelligence 3 Discrete Mathematics 3 Journal of Parallel and Distributed Computing 3 Random Structures & Algorithms 3 Combinatorics, Probability and Computing 3 Journal of Graph Algorithms and Applications 3 Journal of the ACM 3 New Journal of Physics 3 Journal of Physics A: Mathematical and Theoretical 3 Algorithms 2 Israel Journal of Mathematics 2 Journal of Combinatorial Theory. Series A 2 Journal of Combinatorial Theory. Series B 2 Operations Research Letters 2 Annals of Pure and Applied Logic 2 Order 2 Journal of Cryptology 2 Machine Learning 2 Designs, Codes and Cryptography 2 Games and Economic Behavior 2 Linear Algebra and its Applications 2 Archive for Mathematical Logic 2 SIAM Journal on Optimization 2 Advances in Mathematics of Communications 2 Logical Methods in Computer Science 2 Cryptography and Communications 2 ACM Transactions on Computation Theory 1 ACM Computing Surveys 1 Journal of Computational Physics 1 Journal of Statistical Physics 1 Mathematics of Computation 1 The Annals of Statistics 1 Applied Mathematics and Computation 1 Computing 1 International Journal of Game Theory 1 Journal of Functional Analysis 1 Journal of Graph Theory 1 Journal of Pure and Applied Algebra 1 Journal of Statistical Planning and Inference 1 Mathematics of Operations Research 1 Operations Research 1 European Journal of Combinatorics 1 Acta Mathematica Hungarica 1 Acta Mathematicae Applicatae Sinica. English Series 1 Optimization 1 Graphs and Combinatorics 1 Journal of Theoretical Probability 1 Journal of the American Mathematical Society 1 Annals of Operations Research 1 Neural Computation 1 MSCS. Mathematical Structures in Computer Science 1 Discrete Event Dynamic Systems 1 SIAM Review 1 Indagationes Mathematicae. New Series 1 Journal of Logic, Language and Information 1 The Journal of Artificial Intelligence Research (JAIR) 1 Annals of Mathematics and Artificial Intelligence 1 Electronic Journal of Probability 1 Electronic Communications in Probability 1 The Journal of Fourier Analysis and Applications 1 Constraints 1 ELA. The Electronic Journal of Linear Algebra 1 Journal of Automata, Languages and Combinatorics 1 Optimization Methods & Software 1 Journal of Combinatorial Optimization 1 Chicago Journal of Theoretical Computer Science 1 Journal of Scheduling 1 Revista Matemática Complutense 1 Journal of Mathematical Logic 1 Probability in the Engineering and Informational Sciences 1 Fundamenta Informaticae 1 Optimization and Engineering 1 Lobachevskii Journal of Mathematics 1 Annales Henri Poincaré 1 Journal of Systems Science and Complexity 1 Journal of Machine Learning Research (JMLR) 1 Journal of Discrete Algorithms 1 Discrete Optimization 1 Journal of Industrial and Management Optimization 1 Mathematics in Computer Science 1 Foundations and Trends in Communications and Information Theory ...and 7 more Journals all top 5 Cited in 40 Fields 466 Computer science (68-XX) 111 Combinatorics (05-XX) 80 Information and communication theory, circuits (94-XX) 74 Quantum theory (81-XX) 44 Operations research, mathematical programming (90-XX) 32 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 20 Mathematical logic and foundations (03-XX) 17 Linear and multilinear algebra; matrix theory (15-XX) 16 Probability theory and stochastic processes (60-XX) 16 Numerical analysis (65-XX) 15 Order, lattices, ordered algebraic structures (06-XX) 14 Number theory (11-XX) 14 Functional analysis (46-XX) 11 Group theory and generalizations (20-XX) 7 Statistics (62-XX) 5 Commutative algebra (13-XX) 5 Convex and discrete geometry (52-XX) 5 Statistical mechanics, structure of matter (82-XX) 4 Operator theory (47-XX) 3 Harmonic analysis on Euclidean spaces (42-XX) 2 Field theory and polynomials (12-XX) 2 Algebraic geometry (14-XX) 2 Associative rings and algebras (16-XX) 2 Measure and integration (28-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Abstract harmonic analysis (43-XX) 2 Geometry (51-XX) 2 Algebraic topology (55-XX) 1 General and overarching topics; collections (00-XX) 1 General algebraic systems (08-XX) 1 Nonassociative rings and algebras (17-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-XX) 1 Functions of a complex variable (30-XX) 1 Integral equations (45-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Differential geometry (53-XX) 1 Manifolds and cell complexes (57-XX) 1 Biology and other natural sciences (92-XX) 1 Systems theory; control (93-XX) Citations by Year