×

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

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

Publications by Year

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 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