×

Journal of the ACM

Short Title: J. ACM
Publisher: Association for Computing Machinery (ACM), New York, NY
ISSN: 0004-5411; 1557-735X/e
Online: https://dl.acm.org/loi/jacm
http://dl.acm.org/pub.cfm?id=J401
Predecessor: Journal of the Association for Computing Machinery
Comments: Indexed cover-to-cover
Documents Indexed: 871 Publications (since 1996)
References Indexed: 65 Publications with 2,684 References.
all top 5

Latest Issues

69, No. 2 (2022)
69, No. 1 (2022)
67, No. 5 (2020)
67, No. 4 (2020)
67, No. 3 (2020)
67, No. 2 (2020)
67, No. 1 (2020)
66, No. 6 (2019)
66, No. 5 (2019)
66, No. 4 (2019)
66, No. 3 (2019)
66, No. 2 (2019)
66, No. 1 (2019)
65, No. 6 (2018)
65, No. 5 (2018)
65, No. 4 (2018)
65, No. 3 (2018)
65, No. 2 (2018)
65, No. 1 (2018)
64, No. 6 (2017)
64, No. 5 (2017)
64, No. 4 (2017)
64, No. 3 (2017)
64, No. 2 (2017)
64, No. 1 (2017)
63, No. 6 (2017)
63, No. 5 (2016)
63, No. 4 (2016)
63, No. 3 (2016)
63, No. 2 (2016)
63, No. 1 (2016)
62, No. 6 (2015)
62, No. 5 (2015)
62, No. 4 (2015)
62, No. 3 (2015)
62, No. 2 (2015)
62, No. 1 (2015)
61, No. 6 (2014)
61, No. 5 (2014)
61, No. 4 (2014)
61, No. 3 (2014)
61, No. 2 (2014)
61, No. 1 (2014)
60, No. 6 (2013)
60, No. 5 (2013)
60, No. 4 (2013)
60, No. 3 (2013)
60, No. 2 (2013)
60, No. 1 (2013)
59, No. 6 (2012)
59, No. 5 (2012)
59, No. 4 (2012)
59, No. 3 (2012)
59, No. 2 (2012)
59, No. 1 (2012)
58, No. 6 (2011)
58, No. 5 (2011)
58, No. 4 (2011)
58, No. 3 (2011)
58, No. 2 (2011)
58, No. 1 (2010)
57, No. 6 (2010)
57, No. 5 (2010)
57, No. 4 (2010)
57, No. 3 (2010)
57, No. 2 (2010)
57, No. 1 (2009)
56, No. 6 (2009)
56, No. 5 (2009)
56, No. 4 (2009)
56, No. 3 (2009)
56, No. 2 (2009)
56, No. 1 (2009)
55, No. 6 (2008)
55, No. 5 (2008)
55, No. 4 (2008)
55, No. 3 (2008)
55, No. 2 (2008)
55, No. 1 (2008)
54, No. 6 (2007)
54, No. 5 (2007)
54, No. 4 (2007)
54, No. 3 (2007)
54, No. 2 (2007)
54, No. 1 (2007)
53, No. 6 (2006)
53, No. 5 (2006)
53, No. 4 (2006)
53, No. 3 (2006)
53, No. 2 (2006)
53, No. 1 (2006)
52, No. 6 (2005)
52, No. 5 (2005)
52, No. 4 (2005)
52, No. 3 (2005)
52, No. 2 (2005)
52, No. 1 (2005)
51, No. 6 (2004)
51, No. 5 (2004)
51, No. 4 (2004)
...and 49 more Volumes
all top 5

Authors

12 Libkin, Leonid O.
11 Gottlob, Georg
10 Thorup, Mikkel
8 Attiya, Hagit
8 Goldreich, Oded
8 Kleinberg, Jon Michael
8 Sudan, Madhu
7 Censor-Hillel, Keren
7 Ostrovsky, Rafail
7 Raz, Ran
7 Roughgarden, Tim
7 Vazirani, Vijay V.
6 Arora, Sanjeev
6 Aspnes, James
6 Elkin, Michael
6 Fomin, Fedor V.
6 Grohe, Martin
6 Kleinberg, Robert D.
6 Naor, Joseph Seffi
6 Naor, Moni
6 Papadimitriou, Christos Harilaos
6 Pettie, Seth
6 Schwentick, Thomas
6 Srinivasan, Aravind
6 Vempala, Santosh S.
5 Andrews, Matthew T.
5 Benedikt, Michael A.
5 Blum, Avrim L.
5 Chazelle, Bernard
5 Chen, Xi
5 Chuzhoy, Julia
5 Fagin, Ronald
5 Ferragina, Paolo
5 Goldberg, Leslie Ann
5 Guerraoui, Rachid
5 Jerrum, Mark R.
5 Lenzen, Christoph
5 Segoufin, Luc
5 Suciu, Dan Mircea
5 Van den Bussche, Jan
5 Vazirani, Umesh V.
5 Vianu, Victor
5 Vitányi, Paul M. B.
5 Yannakakis, Mihalis
4 Abadi, Martín
4 Achlioptas, Dimitris
4 Agarwal, Pankaj Kumar
4 Alon, Noga M.
4 Alur, Rajeev
4 Ambainis, Andris
4 Awerbuch, Baruch
4 Babaioff, Moshe
4 Barenboim, Leonid
4 Bro Miltersen, Peter
4 Dwork, Cynthia
4 Goldwasser, Shafi
4 Gupta, Anupam
4 Guruswami, Venkatesan
4 Haeupler, Bernhard
4 Har-Peled, Sariel
4 Henzinger, Thomas A.
4 Italiano, Giuseppe Francesco
4 Kaplan, Haim
4 Kolaitis, Phokion G.
4 Kopparty, Swastik
4 Lokshtanov, Daniel
4 Manzini, Giovanni
4 Peleg, David
4 Rajsbaum, Sergio
4 Regev, Oded
4 Sahai, Amit
4 Saks, Michael E.
4 Saurabh, Saket
4 Schieber, Baruch
4 Schulman, Leonard J.
4 Servedio, Rocco A.
4 Sharir, Micha
4 Shavit, Nir N.
4 Slivkins, Aleksandrs
4 Tardos, Gábor
4 Teng, Shang-Hua
4 Upfal, Eli
4 Woodruff, David P.
4 Zhang, Lisa
4 Zwick, Uri
3 Arenas, Marcelo
3 Atserias, Albert
3 Balcan, Maria-Florina
3 Banerjee, Anindya
3 Bansal, Nikhil
3 Barak, Boaz
3 Beame, Paul W.
3 Ben-Sasson, Eli
3 Bilardi, Gianfranco
3 Bodirsky, Manuel
3 Bshouty, Nader H.
3 Bulatov, Andrei A.
3 Cesa-Bianchi, Nicolò
3 Chan, T.-H. Hubert
3 Chan, Timothy Moon-Yew
...and 1,477 more Authors

Publications by Year

Citations contained in zbMATH Open

793 Publications have been cited 17,286 times in 13,507 Documents Cited by Year
A threshold of \(\ln n\) for approximating set cover. Zbl 1065.68573
Feige, Uriel
447
1998
Approximation algorithms for metric facility location and \(k\)-median problems using the primal-dual schema and Lagrangian relaxation. Zbl 1138.90417
Jain, Kamal; Vazirani, Vijay V.
341
2001
Robust principal component analysis? Zbl 1327.62369
Candès, Emmanuel J.; Li, Xiaodong; Ma, Yi; Wright, John
322
2011
How bad is selfish routing? Zbl 1323.90011
Roughgarden, Tim; Tardos, Éva
267
2002
Alternating-time temporal logic. Zbl 1326.68181
Alur, Rajeev; Henzinger, Thomas A.; Kupferman, Orna
259
2002
Some optimal inapproximability results. Zbl 1127.68405
Håstad, Johan
252
2001
Proof verification and the hardness of approximation problems. Zbl 1065.68570
Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario
224
1998
Property testing and its connection to learning and approximation. Zbl 1065.68575
Goldreich, Oded; Goldwasser, Shafi; Ron, Dana
216
1998
On lattices, learning with errors, random linear codes, and cryptography. Zbl 1325.68101
Regev, Oded
193
2009
Most tensor problems are NP-hard. Zbl 1281.68126
Hillar, Christopher J.; Lim, Lek-Heng
192
2013
Approximate distance oracles. Zbl 1175.68303
Thorup, Mikkel; Zwick, Uri
189
2005
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Zbl 1064.90566
Arora, Sanjeev
177
1998
Authoritative sources in a hyperlinked environment. Zbl 1065.68660
Kleinberg, Jon M.
158
1999
Branching time and abstraction in bisimulation semantics. Zbl 0882.68085
van Glabbeek, Rob J.; Weijland, W. Peter
157
1996
Probabilistic checking of proofs: a new characterization of NP. Zbl 0903.68076
Arora, Sanjeev; Safra, Shmuel
145
1998
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Zbl 1204.65044
Jerrum, Mark; Sinclair, Alistair; Vigoda, Eric.
142
2004
Solving SAT and SAT modulo theories, from an abstract Davis-Putnam-Logemann-Loveland procedure to \(\operatorname{DPLL}(T)\). Zbl 1326.68164
Nieuwenhuis, Robert; Oliveras, Albert; Tinelli, Cesare
141
2006
Unreliable failure detectors for reliable distributed systems. Zbl 0885.68021
Chandra, Tushar Deepak; Toueg, Sam
133
1996
An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Zbl 1065.68650
Arya, Sunil; Mount, David M.; Netanyahu, Nathan S.; Silverman, Ruth; Wu, Angela Y.
127
1998
A combinatorial strongly polynomial algorithm for minimizing submodular functions. Zbl 1127.90402
Iwata, Satoru; Fleischer, Lisa; Fujishige, Satoru
126
2001
Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Zbl 1192.90120
Spielman, Daniel A.; Teng, Shang-Hua
122
2004
Closure properties of constraints. Zbl 0890.68064
Jeavons, Peter; Cohen, David; Gyssens, Marc
121
1997
Unconditional security in quantum cryptography. Zbl 1323.94128
Mayers, Dominic
113
2001
Indexing compressed text. Zbl 1323.68261
Ferragina, Paolo; Manzini, Giovanni
112
2005
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Zbl 1065.68666
Leighton, Tom; Rao, Satish
107
1999
An automata-theoretic approach to branching-time model checking. Zbl 1133.68376
Kupferman, Orna; Vardi, Moshe Y.; Wolper, Pierre
106
2000
The random oracle methodology, revisited. Zbl 1204.94063
Canetti, Ran; Goldreich, Oded; Halevi, Shai
104
2004
Short proofs are narrow – resolution made simple. Zbl 1089.03507
Ben-Sasson, Eli; Wigderson, Avi
103
2001
Undirected connectivity in log-space. Zbl 1315.68156
Reingold, Omer
101
2008
Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. Zbl 1325.90060
Jain, Kamal; Mahdian, Mohammad; Markakis, Evangelos; Saberi, Amin; Vazirani, Vijay V.
100
2003
Quantum lower bounds by polynomials. Zbl 1127.68404
Beals, Robert; Buhrman, Harry; Cleve, Richard; Mosca, Michele; de Wolf, Ronald
93
2001
Settling the complexity of computing two-player Nash equilibria. Zbl 1325.68095
Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua
93
2009
The topological structure of asynchronous computability. Zbl 1161.68469
Herlihy, Maurice; Shavit, Nir
92
1999
A constructive proof of the general Lovász local lemma. Zbl 1300.60024
Moser, Robin A.; Tardos, Gábor
92
2010
Semiring-based constraint satisfaction and optimization. Zbl 0890.68032
Bistarelli, Stefano; Montanari, Ugo; Rossi, Francesca
91
1997
Fast Monte-Carlo algorithms for finding low-rank approximations. Zbl 1125.65005
Frieze, Alan; Kannan, Ravi; Vempala, Santosh
91
2004
A dichotomy theorem for constraint satisfaction problems on a 3-element set. Zbl 1316.68057
Bulatov, Andrei A.
89
2006
Counterexample-guided abstraction refinement for symbolic model checking. Zbl 1325.68145
Clarke, Edmund; Grumberg, Orna; Jha, Somesh; Lu, Yuan; Veith, Helmut
89
2003
The benefits of relaxing punctuality. Zbl 0882.68021
Alur, Rajeev; Feder, Tomás; Henzinger, Thomas A.
88
1996
Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. Zbl 1064.92510
Hannenhalli, Sridhar; Pevzner, Pavel A.
87
1999
On the combinatorial and algebraic complexity of quantifier elimination. Zbl 0885.68070
Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise
85
1996
Speed is as powerful as clairvoyance. Zbl 1094.68529
Kalyanasundaram, Bala; Pruhs, Kirk
84
2000
Approximate graph coloring by semidefinite programming. Zbl 0904.68116
Karger, David; Motwani, Rajeev; Sudan, Madhu
83
1998
Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs. Zbl 1326.05152
Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammadtaghi; Thilikos, Dimitrios M.
81
2005
On the (im)possibility of obfuscating programs. Zbl 1281.68118
Barak, Boaz; Goldreich, Oded; Impagliazzo, Russell; Rudich, Steven; Sahai, Amit; Vadhan, Salil; Yang, Ke
81
2012
The weakest failure detector for solving Consensus. Zbl 0885.68022
Chandra, Tushar Deepak; Hadzilacos, Vassos; Toueg, Sam
79
1996
Simplify: a theorem prover for program checking. Zbl 1323.68462
Detlefs, David; Nelson, Greg; Saxe, James B.
78
2005
Aggregating inconsistent information: ranking and clustering. Zbl 1325.68102
Ailon, Nir; Charikar, Moses; Newman, Alantha
77
2008
On-line routing of virtual circuits with applications to load balancing and machine scheduling. Zbl 0890.68014
Aspnes, James; Azar, Yossi; Fiat, Amos; Plotkin, Serge; Waarts, Orli
75
1997
The complexity of homomorphism and constraint satisfaction problems seen from the other side. Zbl 1312.68101
Grohe, Martin
75
2007
On the online bin packing problem. Zbl 1326.68337
Seiden, Steven S.
75
2002
Adding nesting structure to words. Zbl 1325.68138
Alur, Rajeev; Madhusudan, P.
74
2009
Linear work suffix array construction. Zbl 1326.68111
Kärkkäinen, Juha; Sanders, Peter; Burkhardt, Stefan
74
2006
AdWords and generalized online matching. Zbl 1312.68239
Mehta, Aranyak; Saberi, Amin; Vazirani, Umesh V.; Vazirani, Vijay V.
72
2007
An analysis of the Burrows-Wheeler transform. Zbl 1323.68262
Manzini, Giovanni
70
2001
Software protection and simulation on oblivious RAMs. Zbl 0885.68041
Goldreich, Oded; Ostrovsky, Rafail
68
1996
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Zbl 1127.68408
Holm, Jacob; de Lichtenberg, Kristian; Thorup, Mikkel
68
2001
Beyond the flow decomposition barrier. Zbl 1064.90567
Goldberg, Andrew V.; Rao, Satish
67
1998
A measure & conquer approach for the analysis of exact algorithms. Zbl 1325.68311
Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter
67
2009
Truth revelation in approximately efficient combinatorial auctions. Zbl 1326.91011
Lehmann, Daniel; O’Callaghan, Liadan Ita; Shoham, Yoav
67
2002
On clusterings: good, bad and spectral. Zbl 1192.05160
Kannan, Ravi; Vempala, Santosh; Vetta, Adrian
67
2004
Polynomial-time data reduction for dominating set. Zbl 1192.68337
Alber, Jochen; Fellows, Michael R.; Niedermeier, Rolf
66
2004
Private information retrieval. Zbl 1065.68524
Chor, Benny; Goldreich, Oded; Kushilevitz, Eyal; Sudan, Madhu
65
1998
Steiner tree approximation via iterative randomized rounding. Zbl 1281.68234
Byrka, Jarosław; Grandoni, Fabrizio; Rothvoss, Thomas; Sanità, Laura
65
2013
Interactive proofs and the hardness of approximating cliques. Zbl 0882.68129
Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario
64
1996
A simple min-cut algorithm. Zbl 0891.68071
Stoer, Mechthild; Wagner, Frank
64
1997
Scale-sensitive dimensions, uniform convergence, and learnability. Zbl 0891.68086
Alon, Noga; Ben-David, Shai; Cesa-Bianchi, Nicolò; Haussler, David
64
1997
The PCP theorem by gap amplification. Zbl 1292.68074
Dinur, Irit
63
2007
When are elections with few candidates hard to manipulate? Zbl 1292.91062
Conitzer, Vincent; Sandholm, Tuomas; Lang, Jérôme
62
2007
Expander flows, geometric embeddings and graph partitioning. Zbl 1325.68255
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh
61
2009
New lattice-based cryptographic constructions. Zbl 1125.94026
Regev, Oded
60
2004
Speed scaling to manage energy and temperature. Zbl 1326.68043
Bansal, Nikhil; Kimbrel, Tracy; Pruhs, Kirk
60
2007
How to use expert advice. Zbl 0890.68066
Cesa-Bianchi, Nicolò; Freund, Yoav; Haussler, David; Helmbold, David P.; Schapire, Robert E.; Warmuth, Manfred K.
59
1997
Efficient noise-tolerant learning from statistical queries. Zbl 1065.68605
Kearns, Michael
58
1998
A new approach to the minimum cut problem. Zbl 0882.68103
Karger, David R.; Stein, Clifford
58
1996
Randomized algorithms for estimating the trace of an implicit symmetric positive semi-definite matrix. Zbl 1327.68331
Avron, Haim; Toledo, Sivan
58
2011
A unified approach to approximating resource allocation and scheduling. Zbl 1323.68564
Bar-Noy, Amotz; Bar-Yehuda, Reuven; Freund, Ari; Naor, Joseph (Seffi); Schieber, Baruch
58
2001
All pairs shortest paths using bridging sets and rectangular matrix multiplication. Zbl 1326.05157
Zwick, Uri
58
2002
Number-theoretic constructions of efficient pseudo-random functions. Zbl 1248.94086
Naor, Moni; Reingold, Omer
57
2004
Noise-tolerant learning, the parity problem, and the statistical query model. Zbl 1325.68114
Blum, Avrim; Kalai, Adam; Wasserman, Hal
56
2003
Separators for sphere-packings and nearest neighbor graphs. Zbl 0883.68100
Miller, Gary L.; Teng, Shang-Hua; Thurston, William; Vavasis, Stephen A.
53
1997
Compact oracles for reachability and approximate distances in planar digraphs. Zbl 1125.68394
Thorup, Mikkel
53
2004
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses. Zbl 1321.68274
Dell, Holger; Van Melkebeek, Dieter
52
2014
Learning without concentration. Zbl 1333.68232
Mendelson, Shahar
52
2015
Constraint satisfaction problems solvable by local consistency methods. Zbl 1295.68126
Barto, Libor; Kozik, Marcin
51
2014
Approximating extent measures of points. Zbl 1204.68240
Agarwal, Pankaj K.; Har-Peled, Sariel; Varadarajan, Kasturi R.
51
2004
An improved exponential-time algorithm for \(k\)-SAT. Zbl 1297.68217
Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis
50
2005
A modal analysis of staged computation. Zbl 1323.68107
Davies, Rowan; Pfenning, Frank
50
2001
On the impact of combinatorial structure on congestion games. Zbl 1325.91010
Ackermann, Heiner; Röglin, Heiko; Vöcking, Berthold
50
2008
A differential approach to inference in Bayesian networks. Zbl 1325.68226
Darwiche, Adnan
49
2003
The computational complexity of knot and link problems. Zbl 1065.68667
Hass, Joel; Lagarias, Jeffrey C.; Pippenger, Nicholas
48
1999
On the sorting-complexity of suffix tree construction. Zbl 1094.68694
Farach-Colton, Martin; Ferragina, Paolo; Muthukrishnan, S.
48
2000
A theory of goal-oriented communication. Zbl 1281.94004
Goldreich, Oded; Juba, Brendan; Sudan, Madhu
48
2012
Efficient computation of representative families with applications in parameterized and exact algorithms. Zbl 1410.05212
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket
48
2016
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Zbl 1325.68169
Guruswami, Venkatesan; Umans, Christopher; Vadhan, Salil
47
2009
Sparsification – a technique for speeding up dynamic graph algorithms. Zbl 0891.68072
Eppstein, David; Galil, Zvi; Italiano, Giuseppe F.; Nissenzweig, Amnon
46
1997
Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields. Zbl 1326.68336
Kleinberg, Jon; Tardos, Éva
46
2002
Exponential lower bounds for polytopes in combinatorial optimization. Zbl 1333.90107
Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald
46
2015
Undirected single-source shortest paths with positive integer weights in linear time. Zbl 1065.68597
Thorup, Mikkel
45
1999
Exact analysis of Dodgson elections: Lewis Carroll’s 1876 voting system is complete for parallel access to NP. Zbl 0904.68111
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Rothe, Jörg
43
1997
Spatial isolation implies zero knowledge even in a quantum world. Zbl 07500721
Chiesa, Alessandro; Forbes, Michael A.; Gur, Tom; Spooner, Nicholas
1
2022
A framework for adversarially robust streaming algorithms. Zbl 07500723
Ben-Eliezer, Omri; Jayaram, Rajesh; Woodruff, David P.; Yogev, Eylon
1
2022
Planar graphs have bounded queue-number. Zbl 1466.05047
Dujmović, Vida; Joret, Gwenaël; Micek, Piotr; Morin, Pat; Ueckerdt, Torsten; Wood, David R.
18
2020
A proof of the CSP dichotomy conjecture. Zbl 1491.68128
Zhuk, Dmitriy
16
2020
Fully functional suffix trees and optimal text searching in BWT-runs bounded space. Zbl 1491.68067
Gagie, Travis; Navarro, Gonzalo; Prezza, Nicola
10
2020
A simple and approximately optimal mechanism for an additive buyer. Zbl 07273095
Babaioff, Moshe; Immorlica, Nicole; Lucier, Brendan; Weinberg, S. Matthew
10
2020
Representative sets and irrelevant vertices: new tools for kernelization. Zbl 1491.68092
Kratsch, Stefan; Wahlström, Magnus
7
2020
Frege systems for quantified Boolean logic. Zbl 07273080
Beyersdorff, Olaf; Bonacina, Ilario; Chew, Leroy; Pich, Jan
5
2020
Differential equation invariance axiomatization. Zbl 07273077
Platzer, André; Tan, Yong Kiam
4
2020
Planar graph perfect matching is in NC. Zbl 1491.68131
Anari, Nima; Vazirani, Vijay V.
4
2020
Automating resolution is NP-hard. Zbl 1491.68078
Atserias, Albert; Müller, Moritz
4
2020
Detecting an odd hole. Zbl 1491.68141
Chudnovsky, Maria; Scott, Alex; Seymour, Paul; Spirkl, Sophie
2
2020
Fully online matching. Zbl 1491.68271
Huang, Zhiyi; Kang, Ning; Tang, Zhihao Gavin; Wu, Xiaowei; Zhang, Yuhao; Zhu, Xue
2
2020
The log-approximate-rank conjecture is false. Zbl 1491.68073
Chattopadhyay, Arkadev; Mande, Nikhil S.; Sherif, Suhail
2
2020
Forcing and calculi for hybrid logics. Zbl 07273096
Găină, Daniel
2
2020
Universally composable security. Zbl 1491.68036
Canetti, Ran
2
2020
Silence. Zbl 1491.68025
Goren, Guy; Moses, Yoram
1
2020
Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations. Zbl 1473.68121
Kowalski, Dariusz R.; Mosteiro, Miguel A.
1
2020
The power of shunning: efficient asynchronous Byzantine agreement revisited. Zbl 1491.68024
Bangalore, Laasya; Choudhury, Ashish; Patra, Arpita
1
2020
Distributed exact shortest paths in sublinear time. Zbl 1491.68266
Elkin, Michael
1
2020
Embeddability in \(R^3\) is NP-hard. Zbl 1491.68079
de Mesmay, Arnaud; Rieck, Yo’av; Sedgwick, Eric; Tancer, Martin
1
2020
Oracle-efficient online learning and auction design. Zbl 1491.68093
Dudík, Miroslav; Haghtalab, Nika; Luo, Haipeng; Schapire, Robert E.; Syrgkanis, Vasilis; Vaughan, Jennifer Wortman
1
2020
Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Zbl 1427.91142
Devanur, Nikhil R.; Jain, Kamal; Sivan, Balasubramanian; Wilkens, Christopher A.
12
2019
Pseudorandomness from shrinkage. Zbl 1427.68096
Impagliazzo, Russell; Meka, Raghu; Zuckerman, David
9
2019
The salesman’s improved paths through forests. Zbl 1479.90180
Sebő, András; Zuylen, Anke Van
7
2019
Approaching 3/2 for the \(s\)-\(t\)-path TSP. Zbl 1427.90246
Traub, Vera; Vygen, Jens
7
2019
Uniform sampling through the Lovász local lemma. Zbl 1425.68451
Guo, Heng; Jerrum, Mark; Liu, Jingcheng
7
2019
Computing the homology of basic semialgebraic sets in weak exponential time. Zbl 1426.14016
Bürgisser, Peter; Cucker, Felipe; Lairez, Pierre
7
2019
The Weisfeiler-Leman dimension of planar graphs is at most 3. Zbl 1483.05048
Kiefer, Sandra; Ponomarenko, Ilia; Schweitzer, Pascal
6
2019
Tight bounds for undirected graph exploration with pebbles and multiple agents. Zbl 1473.68119
Disser, Yann; Hackfeld, Jan; Klimm, Max
5
2019
Hierarchical clustering. Objective functions and algorithms. Zbl 1473.62213
Cohen-Addad, Vincent; Kanade, Varun; Mallmann-trenn, Frederik; Mathieu, Claire
4
2019
Infinite-duration bidding games. Zbl 1448.91060
Avni, Guy; Henzinger, Thomas A.; Chonev, Ventsislav
4
2019
The Moser-Tardos framework with partial resampling. Zbl 1476.05197
Harris, David G.; Srinivasan, Aravind
4
2019
An unrestricted learning procedure. Zbl 1473.68156
Mendelson, Shahar
4
2019
Exact algorithms via monotone local search. Zbl 1427.68119
Fomin, Fedor V.; Gaspers, Serge; Lokshtanov, Daniel; Saurabh, Saket
4
2019
On the parameterized complexity of approximating dominating set. Zbl 1473.68099
Karthik, C. S.; Laekhanukit, Bundit; Manurangsi, Pasin
3
2019
Deterministic edge connectivity in near-linear time. Zbl 1426.68217
Kawarabayashi, Ken-Ichi; Thorup, Mikkel
3
2019
Shellability is NP-complete. Zbl 1473.68198
Goaoc, Xavier; Paták, Pavel; Patáková, Zuzana; Tancer, Martin; Wagner, Uli
2
2019
On the computability of conditional probability. Zbl 1477.03171
Ackerman, Nathanael L.; Freer, Cameron E.; Roy, Daniel M.
2
2019
White-box vs. black-box complexity of search problems: Ramsey and graph property testing. Zbl 1473.68096
Komargodski, Ilan; Naor, Moni; Yogev, Eylon
2
2019
Approximate counting, the Lovász local lemma, and inference in graphical models. Zbl 1427.68128
Moitra, Ankur
2
2019
Going higher in first-order quantifier alternation hierarchies on words. Zbl 1427.03050
Place, Thomas; Zeitoun, Marc
2
2019
Near-optimal linear decision trees for \(k\)-SUM and related problems. Zbl 1427.68060
Kane, Daniel M.; Lovett, Shachar; Moran, Shay
2
2019
Fast learning requires good memory: a time-space lower bound for parity learning. Zbl 1426.68240
Raz, Ran
2
2019
Scaling exponential backoff: constant throughput, polylogarithmic channel-access attempts, and robustness. Zbl 1426.68021
Bender, Michael A.; Fineman, Jeremy T.; Gilbert, Seth; Young, Maxwell
2
2019
On the decidability of membership in matrix-exponential semigroups. Zbl 1481.20197
Ouaknine, Joël; Pouly, Amaury; Sousa-Pinto, João; Worrell, James
1
2019
From real-time logic to timed automata. Zbl 1473.68107
Ferrère, Thomas; Maler, Oded; Ničković, Dejan; Pnueli, Amir
1
2019
Nonhomogeneous place-dependent Markov chains, unsynchronised AIMD, and optimisation. Zbl 1479.90162
Wirth, Fabian R.; Stüdli, Sonja; Yu, Jia Yuan; Corless, Martin; Shorten, Robert
1
2019
On the complexity of hazard-free circuits. Zbl 1473.94170
Ikenmeyer, Christian; Komarath, Balagopal; Lenzen, Christoph; Lysikov, Vladimir; Mokhov, Andrey; Sreenivasaiah, Karteek
1
2019
Bandits and experts in metric spaces. Zbl 1476.91073
Kleinberg, Robert; Slivkins, Aleksandrs; Upfal, Eli
1
2019
Online bipartite matching with amortized \(O(\log^2 n)\) replacements. Zbl 1473.68217
Bernstein, Aaron; Holm, Jacob; Rotenberg, Eva
1
2019
An operational characterization of mutual information in algorithmic information theory. Zbl 1473.68100
Romashchenko, Andrei; Zimand, Marius
1
2019
Deciding context unification. Zbl 1473.68103
Jeż, Artur
1
2019
Computing the geometric intersection number of curves. Zbl 1473.68197
Despré, Vincent; Lazarus, Francis
1
2019
Capacity upper bounds for deletion-type channels. Zbl 1471.94018
Cheraghchi, Mahdi
1
2019
Bar induction is compatible with constructive type theory. Zbl 1427.03066
Rahli, Vincent; Bickford, Mark; Cohen, Liron; Constable, Robert L.
1
2019
Parallel Bayesian search with no coordination. Zbl 1427.68359
Fraigniaud, Pierre; Korman, Amos; Rodeh, Yoav
1
2019
Indistinguishability obfuscation from functional encryption. Zbl 1407.94087
Bitansky, Nir; Vaikuntanathan, Vinod
30
2018
Fair enough: guaranteeing approximate maximin shares. Zbl 1410.91314
Kurokawa, David; Procaccia, Ariel D.; Wang, Junxing
29
2018
Non-malleable codes. Zbl 1409.94869
Dziembowski, Stefan; Pietrzak, Krzysztof; Wichs, Daniel
21
2018
Subcubic equivalences between path, matrix, and triangle problems. Zbl 1426.68133
Williams, Virginia Vassilevska; Williams, R. Ryan
19
2018
Bandits with knapsacks. Zbl 1425.68340
Badanidiyuru, Ashwinkumar; Kleinberg, Robert; Slivkins, Aleksandrs
14
2018
Full abstraction for probabilistic PCF. Zbl 1426.68035
Ehrhard, Thomas; Pagani, Michele; Tasson, Christine
12
2018
Fast Hamiltonicity checking via bases of perfect matchings. Zbl 1426.68117
Cygan, Marek; Kratsch, Stefan; Nederlof, Jesper
11
2018
Path ORAM: an extremely simple oblivious RAM protocol. Zbl 1426.68008
Stefanov, Emil; Van Dijk, Marten; Shi, Elaine; Chan, T.-H. Hubert; Fletcher, Christopher; Ren, Ling; Yu, Xiangyao; Devadas, Srinivas
11
2018
Threesomes, degenerates, and love triangles. Zbl 1422.68112
Grønlund, Allan; Pettie, Seth
10
2018
Matroid secretary problems. Zbl 1425.68461
Babaioff, Moshe; Immorlica, Nicole; Kempe, David; Kleinberg, Robert
10
2018
The applied pi calculus, mobile values, new names, and secure communication. Zbl 1426.68037
Abadi, Martín; Blanchet, Bruno; Fournet, Cédric
9
2018
Spectral properties of hypergraph Laplacian and approximation algorithms. Zbl 1426.05163
Chan, T.-H. Hubert; Louis, Anand; Tang, Zhihao Gavin; Zhang, Chenzi
8
2018
Proving the incompatibility of efficiency and strategyproofness via SMT solving. Zbl 1425.68385
Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian
6
2018
Weakest precondition reasoning for expected runtimes of randomized algorithms. Zbl 1426.68298
Kaminski, Benjamin Lucien; Katoen, Joost-Pieter; Matheja, Christoph; Olmedo, Federico
6
2018
Decremental single-source shortest paths on undirected graphs in near-linear total update time. Zbl 1426.68215
Henzinger, Monika; Krinninger, Sebastian; Nanongkai, Danupon
6
2018
The parameterized complexity of the \(k\)-biclique problem. Zbl 1426.68131
Lin, Bingkai
5
2018
Solving optimization problems with diseconomies of scale via decoupling. Zbl 1426.90261
Makarychev, Konstantin; Sviridenko, Maxim
5
2018
Coin flipping of any constant bias implies one-way functions. Zbl 1426.94083
Berman, Itay; Haitner, Iftach; Tentes, Aris
4
2018
Worst-case optimal join algorithms. Zbl 1426.68081
Ngo, Hung Q.; Porat, Ely; Ré, Christopher; Rudra, Atri
4
2018
Optimal multi-way number partitioning. Zbl 1426.68313
Schreiber, Ethan L.; Korf, Richard E.; Moffitt, Michael D.
4
2018
Ontology-mediated queries. Combined complexity and succinctness of rewritings via circuit complexity. Zbl 1426.68075
Bienvenu, Meghyn; Kikot, Stanislav; Kontchakov, Roman; Podolskii, Vladimir V.; Zakharyaschev, Michael
4
2018
Reachability is in DynFO. Zbl 1426.68107
Datta, Samir; Kulkarni, Raghav; Mukherjee, Anish; Schwentick, Thomas; Zeume, Thomas
4
2018
Shuffles and circuits (on lower bounds for modern parallel computation). Zbl 1426.68105
Roughgarden, Tim; Vassilvitskii, Sergei; Wang, Joshua R.
4
2018
Excluded grid minors and efficient polynomial-time approximation schemes. Zbl 1426.68303
Fomin, Fedorr V.; Lokshtanov, Daniel; Saurabh, Saket
3
2018
Distributed \((\Delta+1)\)-coloring in sublogarithmic rounds. Zbl 1426.68214
Harris, David G.; Schneider, Johannes; Su, Hsin-Hao
3
2018
Equivalence of deterministic top-down tree-to-string transducers is decidable. Zbl 1426.68154
Seidl, Helmut; Maneth, Sebastian; Kemper, Gregor
3
2018
On algebraic branching programs of small width. Zbl 1426.68089
Bringmann, Karl; Ikenmeyer, Christian; Zuiddam, Jeroen
3
2018
Parallel metric tree embedding based on an algebraic view on Moore-Bellman-Ford. Zbl 1426.68211
Friedrichs, Stephan; Lenzen, Christoph
3
2018
Discrete temporal constraint satisfaction problems. Zbl 1425.68135
Bodirsky, Manuel; Martin, Barnaby; Mottet, Antoine
2
2018
Analysing snapshot isolation. Zbl 1425.68094
Cerone, Andrea; Gotsman, Alexey
2
2018
Rumor spreading and conductance. Zbl 1426.68022
Chierichetti, Flavio; Giakkoupis, George; Lattanzi, Silvio; Panconesi, Alessandro
2
2018
The cost of unknown diameter in dynamic networks. Zbl 1426.68228
Yu, Haifeng; Zhao, Yuda; Jahja, Irvan
2
2018
Circuit complexity, proof complexity, and polynomial identity testing. The ideal proof system. Zbl 1426.68097
Grochow, Joshua A.; Pitassi, Toniann
2
2018
Unifying concurrent objects and distributed tasks. Interval-linearizability. Zbl 1426.68181
Castañeda, Armando; Rajsbaum, Sergio; Raynal, Michel
2
2018
Competitive algorithms from competitive equilibria, non-clairvoyant scheduling under polyhedral constraints. Zbl 1426.68309
Im, Sungjin; Kulkarni, Janardhan; Munagala, Kamesh
1
2018
Constant-rate coding for multiparty interactive communication is impossible. Zbl 1426.68016
Braverman, Mark; Efremenko, Klim; Gelles, Ran; Haeupler, Bernhard
1
2018
Embeddability in the 3-sphere is decidable. Zbl 1426.68276
Matoušek, Jiří; Sedgwick, Eric; Tancer, Martin; Wagner, Uli
1
2018
The freezing threshold for \(k\)-colourings of a random graph. Zbl 1426.05150
Molloy, Michael
1
2018
Minimization of tree patterns. Zbl 1426.68076
Czerwiński, Wojciech; Martens, Wim; Niewerth, Matthias; Parys, Paweł
1
2018
Settling the query complexity of non-adaptive junta testing. Zbl 1426.68295
Chen, Xi; Servedio, Rocco A.; Tan, Li-Yang; Waingarten, Erik; Xie, Jinyu
1
2018
Deciding first-order properties of nowhere dense graphs. Zbl 1426.68172
Grohe, Martin; Kreutzer, Stephan; Siebertz, Sebastian
23
2017
A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Zbl 1426.68311
Safey El Din, Mohab; Schost, Éric
19
2017
The matching polytope has exponential extension complexity. Zbl 1426.90255
Rothvoss, Thomas
19
2017
...and 693 more Documents
all top 5

Cited by 16,560 Authors

72 Xu, Dachuan
67 Saurabh, Saket
56 Fomin, Fedor V.
52 Epstein, Leah
50 Navarro, Gonzalo
44 Raynal, Michel
43 Goldreich, Oded
38 Lokshtanov, Daniel
37 Chatterjee, Krishnendu
35 Thilikos, Dimitrios M.
34 Rajsbaum, Sergio
33 Pilipczuk, Marcin L.
33 Pilipczuk, Michał
31 Du, Donglei
31 Kupferman, Orna
31 Paschos, Vangelis Th.
31 Wu, Chenchen
30 Niedermeier, Rolf
29 Živný, Stanislav
27 Jonsson, Peter A.
27 Levin, Asaf
27 Spirakis, Paul G.
26 Guerraoui, Rachid
26 Murano, Aniello
26 Rauch Henzinger, Monika
26 Rothe, Jörg-Matthias
26 Thankachan, Sharma V.
25 Fraigniaud, Pierre
25 Henzinger, Thomas A.
25 Servedio, Rocco A.
24 Chan, Timothy Moon-Yew
24 Guruswami, Venkatesan
24 Jansen, Bart M. P.
24 Panolan, Fahad
24 Ron, Dana
24 Zehavi, Meirav
23 Bodirsky, Manuel
23 Feige, Uriel
23 Gagie, Travis
23 Goldberg, Leslie Ann
23 Pelc, Andrzej
23 Roughgarden, Tim
23 Sau, Ignasi
23 Sharir, Micha
23 Vaikuntanathan, Vinod
23 Zhang, Dongmei
22 Fernau, Henning
22 Grohe, Martin
22 Guo, Jiong
22 Gupta, Anupam
22 Kowalski, Dariusz R.
22 Manthey, Bodo
22 Marx, Dániel
22 Neiman, Ofer
21 Cai, Jin-Yi
21 Caragiannis, Ioannis
21 Censor-Hillel, Keren
21 Cygan, Marek
21 Golovach, Petr A.
21 Hajiaghayi, Mohammad Taghi
21 Halldórsson, Magnús Mar
21 Ishai, Yuval
21 Kaplan, Haim
21 Mehlhorn, Kurt
21 Pass, Rafael
21 Pettie, Seth
20 Alon, Noga M.
20 Bergstra, Jan A.
20 Krokhin, Andrei A.
20 Martin, Barnaby D.
20 Raman, Venkatesh
20 Vempala, Santosh S.
20 Yoshida, Yuichi
19 Bulatov, Andrei A.
19 Chen, Hubie
19 Czumaj, Artur
19 Fox, Jacob
19 Gottlob, Georg
19 Libkin, Leonid O.
19 Lingas, Andrzej
19 Mendelson, Shahar
19 Nagarajan, Viswanath
19 Naor, Assaf
19 Pruhs, Kirk R.
19 Ravi, Ramamoorthi
19 Sahai, Amit
18 Albers, Susanne
18 Bansal, Nikhil
18 Bozzelli, Laura
18 Cooper, Martin C.
18 Eiter, Thomas
18 Kratsch, Stefan
18 Papadimitriou, Christos Harilaos
18 Peleg, David
18 Qiu, Daowen
18 Scarcello, Francesco
18 Sgall, Jiří
18 Shah, Rahul
18 Vardi, Moshe Ya’akov
18 Woodruff, David P.
...and 16,460 more Authors
all top 5

Cited in 628 Journals

1,228 Theoretical Computer Science
552 Algorithmica
404 Journal of Computer and System Sciences
347 SIAM Journal on Computing
329 Information and Computation
300 Information Processing Letters
298 Discrete Applied Mathematics
257 Theory of Computing Systems
244 Artificial Intelligence
203 Distributed Computing
180 Journal of Combinatorial Optimization
152 Mathematical Programming. Series A. Series B
132 SIAM Journal on Discrete Mathematics
115 European Journal of Operational Research
110 Computational Complexity
108 Journal of Cryptology
102 Journal of Discrete Algorithms
100 Operations Research Letters
95 Discrete & Computational Geometry
93 Computational Geometry
93 Logical Methods in Computer Science
89 Information Sciences
78 Annals of Mathematics and Artificial Intelligence
77 Mathematics of Operations Research
74 Journal of Automated Reasoning
73 Formal Methods in System Design
64 Acta Informatica
63 Journal of Symbolic Computation
63 Games and Economic Behavior
63 Theory and Practice of Logic Programming
61 Operations Research
61 Discrete Optimization
60 Quantum Information Processing
59 Discrete Mathematics
59 Machine Learning
59 International Journal of Foundations of Computer Science
57 Random Structures & Algorithms
57 Linear Algebra and its Applications
57 Journal of Machine Learning Research (JMLR)
55 Computers & Operations Research
54 The Annals of Statistics
51 Annals of Operations Research
50 International Journal of Approximate Reasoning
48 International Journal of Theoretical Physics
45 Journal of Scheduling
44 European Journal of Combinatorics
44 Journal of Logical and Algebraic Methods in Programming
43 SIAM Journal on Matrix Analysis and Applications
43 International Journal of Computational Geometry & Applications
43 Foundations of Computational Mathematics
40 Computer Science Review
39 MSCS. Mathematical Structures in Computer Science
39 Journal of Global Optimization
39 SIAM Journal on Scientific Computing
38 Journal of Complexity
38 Formal Aspects of Computing
38 Designs, Codes and Cryptography
38 The Electronic Journal of Combinatorics
38 Optimization Letters
35 Journal of the ACM
34 ACM Transactions on Computational Logic
33 Journal of Parallel and Distributed Computing
33 Combinatorics, Probability and Computing
31 Combinatorica
31 Computational Optimization and Applications
30 Journal of Combinatorial Theory. Series B
30 Neural Computation
29 Applied Mathematics and Computation
29 Constraints
28 Israel Journal of Mathematics
28 Journal of Computational and Applied Mathematics
27 Networks
27 Pattern Recognition
27 The Journal of Logic and Algebraic Programming
27 Algorithms
26 International Journal of Computer Vision
25 Automatica
25 SIAM Journal on Optimization
25 Data Mining and Knowledge Discovery
25 ACM Journal of Experimental Algorithmics
24 Physica A
24 Annals of Pure and Applied Logic
24 Applied and Computational Harmonic Analysis
24 Journal of Applied Logic
23 Journal of Mathematical Imaging and Vision
22 Journal of Functional Programming
22 INFORMS Journal on Computing
21 Journal of Computational Physics
21 The Journal of Artificial Intelligence Research (JAIR)
20 Fuzzy Sets and Systems
20 Journal of Scientific Computing
20 Electronic Journal of Statistics
19 Mathematics of Computation
19 Studia Logica
19 Real-Time Systems
19 The Annals of Applied Probability
18 Computing
18 Journal of Graph Algorithms and Applications
18 International Journal of Quantum Information
17 Communications in Mathematical Physics
...and 528 more Journals
all top 5

Cited in 62 Fields

9,064 Computer science (68-XX)
2,533 Operations research, mathematical programming (90-XX)
2,257 Combinatorics (05-XX)
1,216 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
1,195 Information and communication theory, circuits (94-XX)
1,050 Mathematical logic and foundations (03-XX)
699 Numerical analysis (65-XX)
618 Statistics (62-XX)
405 Probability theory and stochastic processes (60-XX)
399 Quantum theory (81-XX)
365 Linear and multilinear algebra; matrix theory (15-XX)
265 Biology and other natural sciences (92-XX)
201 Convex and discrete geometry (52-XX)
133 Number theory (11-XX)
107 Systems theory; control (93-XX)
106 Algebraic geometry (14-XX)
103 Statistical mechanics, structure of matter (82-XX)
94 Order, lattices, ordered algebraic structures (06-XX)
83 General algebraic systems (08-XX)
75 Group theory and generalizations (20-XX)
69 Commutative algebra (13-XX)
68 Functional analysis (46-XX)
67 Calculus of variations and optimal control; optimization (49-XX)
61 Manifolds and cell complexes (57-XX)
58 Partial differential equations (35-XX)
49 Algebraic topology (55-XX)
46 Dynamical systems and ergodic theory (37-XX)
43 Field theory and polynomials (12-XX)
42 Geometry (51-XX)
34 Operator theory (47-XX)
33 Approximations and expansions (41-XX)
30 Category theory; homological algebra (18-XX)
27 General topology (54-XX)
24 History and biography (01-XX)
24 Functions of a complex variable (30-XX)
24 Differential geometry (53-XX)
22 General and overarching topics; collections (00-XX)
21 Associative rings and algebras (16-XX)
19 Ordinary differential equations (34-XX)
19 Fluid mechanics (76-XX)
16 Mechanics of deformable solids (74-XX)
14 Real functions (26-XX)
14 Measure and integration (28-XX)
14 Global analysis, analysis on manifolds (58-XX)
13 Geophysics (86-XX)
12 Harmonic analysis on Euclidean spaces (42-XX)
7 Topological groups, Lie groups (22-XX)
7 Mechanics of particles and systems (70-XX)
6 Optics, electromagnetic theory (78-XX)
5 Several complex variables and analytic spaces (32-XX)
4 Difference and functional equations (39-XX)
3 Nonassociative rings and algebras (17-XX)
3 Abstract harmonic analysis (43-XX)
3 Integral transforms, operational calculus (44-XX)
3 Relativity and gravitational theory (83-XX)
2 Potential theory (31-XX)
2 Special functions (33-XX)
2 Sequences, series, summability (40-XX)
2 Classical thermodynamics, heat transfer (80-XX)
2 Astronomy and astrophysics (85-XX)
2 Mathematics education (97-XX)
1 Integral equations (45-XX)

Citations by Year