Rahman, Md Lutfar; Watson, Thomas 6-uniform Maker-Breaker game is PSPACE-complete. (English) Zbl 07745890 Combinatorica 43, No. 3, 595-612 (2023). Reviewer: Luigi Palopoli (Rende) MSC: 68Q17 68Q15 PDFBibTeX XMLCite \textit{M. L. Rahman} and \textit{T. Watson}, Combinatorica 43, No. 3, 595--612 (2023; Zbl 07745890) Full Text: DOI
Kalai, Yael Tauman; Komargodski, Ilan; Raz, Ran A lower bound for adaptively-secure collective coin flipping protocols. (English) Zbl 1488.68030 Combinatorica 41, No. 1, 75-98 (2021). MSC: 68Q10 68Q11 68Q17 68Q25 PDFBibTeX XMLCite \textit{Y. T. Kalai} et al., Combinatorica 41, No. 1, 75--98 (2021; Zbl 1488.68030) Full Text: DOI Link
Karthik, C. S.; Manurangsi, Pasin On closest pair in Euclidean metric: monochromatic is as hard as bichromatic. (English) Zbl 1474.68424 Combinatorica 40, No. 4, 539-573 (2020). MSC: 68U05 68Q17 68Q25 PDFBibTeX XMLCite \textit{C. S. Karthik} and \textit{P. Manurangsi}, Combinatorica 40, No. 4, 539--573 (2020; Zbl 1474.68424) Full Text: DOI arXiv Link
Alon, Noga; Kumar, Mrinal; Volk, Ben Lee Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits. (English) Zbl 1488.68027 Combinatorica 40, No. 2, 149-178 (2020). MSC: 68Q06 05D05 68Q17 PDFBibTeX XMLCite \textit{N. Alon} et al., Combinatorica 40, No. 2, 149--178 (2020; Zbl 1488.68027) Full Text: DOI Link
Mustafa, Nabil H.; Dutta, Kunal; Ghosh, Arijit A simple proof of optimal epsilon nets. (English) Zbl 1424.52020 Combinatorica 38, No. 5, 1269-1277 (2018). Reviewer: Ko-Wei Lih (Taipei) MSC: 52C45 05D15 52B55 PDFBibTeX XMLCite \textit{N. H. Mustafa} et al., Combinatorica 38, No. 5, 1269--1277 (2018; Zbl 1424.52020) Full Text: DOI HAL
Saraf, Shubhangi; Volkovich, Ilya Black-box identity testing of depth-4 multilinear circuits. (English) Zbl 1424.68078 Combinatorica 38, No. 5, 1205-1238 (2018). MSC: 68Q25 12Y05 94C10 94C12 PDFBibTeX XMLCite \textit{S. Saraf} and \textit{I. Volkovich}, Combinatorica 38, No. 5, 1205--1238 (2018; Zbl 1424.68078) Full Text: DOI
Jerrum, Mark; Meeks, Kitty The parameterised complexity of counting even and odd induced subgraphs. (English) Zbl 1413.68063 Combinatorica 37, No. 5, 965-990 (2017). MSC: 68Q25 05C30 68Q17 PDFBibTeX XMLCite \textit{M. Jerrum} and \textit{K. Meeks}, Combinatorica 37, No. 5, 965--990 (2017; Zbl 1413.68063) Full Text: DOI arXiv Link
Lauria, Massimo; Pudlák, Pavel; Rödl, Vojtěch; Thapen, Neil The complexity of proving that a graph is Ramsey. (English) Zbl 1399.03021 Combinatorica 37, No. 2, 253-268 (2017). MSC: 03F20 05C55 05C80 68Q17 PDFBibTeX XMLCite \textit{M. Lauria} et al., Combinatorica 37, No. 2, 253--268 (2017; Zbl 1399.03021) Full Text: DOI arXiv
Király, Tamás; Lau, Lap Chi; Singh, Mohit Degree bounded matroids and submodular flows. (English) Zbl 1299.90432 Combinatorica 32, No. 6, 703-720 (2012). Reviewer: Günther Schmidt (München) MSC: 90C60 90C27 68W25 68Q25 PDFBibTeX XMLCite \textit{T. Király} et al., Combinatorica 32, No. 6, 703--720 (2012; Zbl 1299.90432) Full Text: DOI Link
Briët, Jop; Chakraborty, Sourav; García-Soriano, David; Matsliah, Arie Monotonicity testing and shortest-path routing on the cube. (English) Zbl 1265.68079 Combinatorica 32, No. 1, 35-53 (2012). Reviewer: Zhizhang Shen (Plymouth) MSC: 68Q17 68R05 PDFBibTeX XMLCite \textit{J. Briët} et al., Combinatorica 32, No. 1, 35--53 (2012; Zbl 1265.68079) Full Text: DOI
Sherstov, Alexander A. The unbounded-error communication complexity of symmetric functions. (English) Zbl 1265.03035 Combinatorica 31, No. 5, 583-614 (2011). Reviewer: Cristian S. Calude (Bucuresti) MSC: 03D15 68Q17 PDFBibTeX XMLCite \textit{A. A. Sherstov}, Combinatorica 31, No. 5, 583--614 (2011; Zbl 1265.03035) Full Text: DOI
Karnin, Zohar S.; Shpilka, Amir Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. (English) Zbl 1274.68133 Combinatorica 31, No. 3, 333-364 (2011). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{Z. S. Karnin} and \textit{A. Shpilka}, Combinatorica 31, No. 3, 333--364 (2011; Zbl 1274.68133) Full Text: DOI
Korneffel, Torsten; Triesch, Eberhard An asymptotic bound for the complexity of monotone graph properties. (English) Zbl 1231.05222 Combinatorica 30, No. 6, 735-743 (2010). Reviewer: Ioan Tomescu (Bucharest) MSC: 05C75 05C99 68R10 68Q17 68Q25 PDFBibTeX XMLCite \textit{T. Korneffel} and \textit{E. Triesch}, Combinatorica 30, No. 6, 735--743 (2010; Zbl 1231.05222) Full Text: DOI
O’Donnell, Ryan; Servedio, Rocco A. New degree bounds for polynomial threshold functions. (English) Zbl 1240.05303 Combinatorica 30, No. 3, 327-358 (2010). Reviewer: Jörg Desel (Hagen) MSC: 05E99 68Q99 68Q17 68Q32 PDFBibTeX XMLCite \textit{R. O'Donnell} and \textit{R. A. Servedio}, Combinatorica 30, No. 3, 327--358 (2010; Zbl 1240.05303) Full Text: DOI
Kolountzakis, Mihail N.; Lipton, Richard J.; Markakis, Evangelos; Mehta, Aranyak; Vishnoi, Nisheeth K. On the Fourier spectrum of symmetric Boolean functions. (English) Zbl 1212.42017 Combinatorica 29, No. 3, 363-387 (2009). Reviewer: Alexander Ulanovskii (Stavanger) MSC: 42B05 68Q32 PDFBibTeX XMLCite \textit{M. N. Kolountzakis} et al., Combinatorica 29, No. 3, 363--387 (2009; Zbl 1212.42017) Full Text: DOI
Halldórsson, Magnús M.; Kortsarz, Guy; Radhakrishnan, Jaikumar; Sivasubramanian, Sivaramakrishnan Complete partitions of graphs. (English) Zbl 1164.68038 Combinatorica 27, No. 5, 519-550 (2007). Reviewer: Gunther Schmidt (München) MSC: 68W25 05C70 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{M. M. Halldórsson} et al., Combinatorica 27, No. 5, 519--550 (2007; Zbl 1164.68038) Full Text: DOI
Linial, Nati; Mendelson, Shahar; Schechtman, Gideon; Shraibman, Adi Complexity measures of sign matrices. (English) Zbl 1164.68006 Combinatorica 27, No. 4, 439-463 (2007). MSC: 68Q15 46B07 68Q17 68Q32 PDFBibTeX XMLCite \textit{N. Linial} et al., Combinatorica 27, No. 4, 439--463 (2007; Zbl 1164.68006) Full Text: DOI
Fellows, Michael R.; Gramm, Jens; Niedermeier, Rolf On the parameterized intractability of motif search problems. (English) Zbl 1109.68049 Combinatorica 26, No. 2, 141-167 (2006). Reviewer: Reinhard Pichler (Purkersdorf) MSC: 68Q17 03D15 68Q25 92B99 PDFBibTeX XMLCite \textit{M. R. Fellows} et al., Combinatorica 26, No. 2, 141--167 (2006; Zbl 1109.68049) Full Text: DOI arXiv
Matoušek, Jiří The number of unique-sink orientations of the hypercube. (English) Zbl 1106.05048 Combinatorica 26, No. 1, 91-99 (2006). Reviewer: Ismail Naci Canquel (Bursa) MSC: 05C30 90C60 PDFBibTeX XMLCite \textit{J. Matoušek}, Combinatorica 26, No. 1, 91--99 (2006; Zbl 1106.05048) Full Text: DOI
Dinur, Irit; Regev, Oded; Smyth, Clifford The hardness of 3-uniform hypergraph coloring. (English) Zbl 1106.68080 Combinatorica 25, No. 5, 519-535 (2005). Reviewer: Josef Vyskoc (Bratislava) MSC: 68R10 68Q17 05C65 05C15 PDFBibTeX XMLCite \textit{I. Dinur} et al., Combinatorica 25, No. 5, 519--535 (2005; Zbl 1106.68080) Full Text: DOI
Ben-Sasson, Eli; Impagliazzo, Russell; Wigderson, Avi Near optimal seperation of tree-like and general resolution. (English) Zbl 1063.03043 Combinatorica 24, No. 4, 585-603 (2004). MSC: 03F20 03B35 68Q17 PDFBibTeX XMLCite \textit{E. Ben-Sasson} et al., Combinatorica 24, No. 4, 585--603 (2004; Zbl 1063.03043) Full Text: DOI
Pitassi, Toniann; Raz, Ran Regular resolution lower bounds for the weak pigeonhole principle. (English) Zbl 1063.03044 Combinatorica 24, No. 3, 503-524 (2004). Reviewer: Roman Murawski (Poznan) MSC: 03F20 68Q17 PDFBibTeX XMLCite \textit{T. Pitassi} and \textit{R. Raz}, Combinatorica 24, No. 3, 503--524 (2004; Zbl 1063.03044) Full Text: DOI
Dinur, I.; Kindler, G.; Raz, R.; Safra, S. Approximating CVP to within almost-polynomial factors is NP-hard. (English) Zbl 1049.68072 Combinatorica 23, No. 2, 205-243 (2003). Reviewer: Heribert Vollmer (Hannover) MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{I. Dinur} et al., Combinatorica 23, No. 2, 205--243 (2003; Zbl 1049.68072) Full Text: DOI
Eisenbrand, F.; Schulz, A. S. Bounds on the Chvatal rank of polytopes in the 0/1-cube. (English) Zbl 1027.52005 Combinatorica 23, No. 2, 245-261 (2003). MSC: 52B05 90C57 90C60 90C10 90C27 PDFBibTeX XMLCite \textit{F. Eisenbrand} and \textit{A. S. Schulz}, Combinatorica 23, No. 2, 245--261 (2003; Zbl 1027.52005) Full Text: DOI
Razborov, Alexander; Wigderson, Avi; Yao, Andrew Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. (English) Zbl 1027.03043 Combinatorica 22, No. 4, 555-574 (2002). Reviewer: Krassimir Altanassov (Sofia) MSC: 03F20 68Q17 PDFBibTeX XMLCite \textit{A. Razborov} et al., Combinatorica 22, No. 4, 555--574 (2002; Zbl 1027.03043) Full Text: DOI
Petrank, Erez; Tardos, Gábor On the knowledge complexity of \(\mathcal N\mathcal P\). (English) Zbl 0997.68062 Combinatorica 22, No. 1, 83-121 (2002). Reviewer: Reinhard Pichler (Purkersdorf) MSC: 68Q15 68Q17 PDFBibTeX XMLCite \textit{E. Petrank} and \textit{G. Tardos}, Combinatorica 22, No. 1, 83--121 (2002; Zbl 0997.68062) Full Text: DOI
Khanna, Sanjeev; Linial, Nathan; Safra, Shmuel On the hardness of approximating the chromatic number. (English) Zbl 0964.68065 Combinatorica 20, No. 3, 393-415 (2000). Reviewer: Uwe Schöning (Ulm) MSC: 68Q25 68Q17 68R10 05C15 PDFBibTeX XMLCite \textit{S. Khanna} et al., Combinatorica 20, No. 3, 393--415 (2000; Zbl 0964.68065) Full Text: DOI
Jukna, Stasys Combinatorics of monotone computations. (English) Zbl 0962.03030 Combinatorica 19, No. 1, 65-85 (1999). MSC: 03D15 68Q17 94C10 05D15 68R05 03F07 03B05 68Q05 PDFBibTeX XMLCite \textit{S. Jukna}, Combinatorica 19, No. 1, 65--85 (1999; Zbl 0962.03030) Full Text: DOI
Babai, László; Gál, Anna; Wigderson, Avi Superpolynomial lower bounds for monotone span programs. (English) Zbl 0990.68077 Combinatorica 19, No. 3, 301-319 (1999). Reviewer: Marius Zimand (Towson) MSC: 68Q17 68Q05 05D05 68Q15 PDFBibTeX XMLCite \textit{L. Babai} et al., Combinatorica 19, No. 3, 301--319 (1999; Zbl 0990.68077) Full Text: DOI
Eisenbrand, Friedrich On the membership problem for the elementary closure of a polyhedron. (English) Zbl 0947.90071 Combinatorica 19, No. 2, 297-300 (1999). MSC: 90C10 90C60 68Q25 PDFBibTeX XMLCite \textit{F. Eisenbrand}, Combinatorica 19, No. 2, 297--300 (1999; Zbl 0947.90071) Full Text: DOI
Ibaraki, Toshihide; Karzanov, Alexander V.; Nagamochi, Hiroshi A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons. (English) Zbl 0914.90110 Combinatorica 18, No. 1, 61-83 (1998). Reviewer: F.Luban (Bucuresti) MSC: 90B10 90C35 90C27 90C60 PDFBibTeX XMLCite \textit{T. Ibaraki} et al., Combinatorica 18, No. 1, 61--83 (1998; Zbl 0914.90110) Full Text: DOI
Coullard, Collette R.; Hellerstein, Lisa Independence and port oracles for matroids, with an application to computational learning theory. (English) Zbl 0860.05019 Combinatorica 16, No. 2, 189-208 (1996). Reviewer: J.Libicher (Ostrava) MSC: 05B35 68T05 68W10 68Q25 PDFBibTeX XMLCite \textit{C. R. Coullard} and \textit{L. Hellerstein}, Combinatorica 16, No. 2, 189--208 (1996; Zbl 0860.05019) Full Text: DOI
Aronov, B.; Edelsbrunner, H.; Guibas, L. J.; Sharir, M. The number of edges of many faces in a line segment arrangement. (English) Zbl 0768.52003 Combinatorica 12, No. 3, 261-274 (1992). Reviewer: E.Schulte (Boston) MSC: 52A37 51A10 68U05 PDFBibTeX XMLCite \textit{B. Aronov} et al., Combinatorica 12, No. 3, 261--274 (1992; Zbl 0768.52003) Full Text: DOI
Knuth, Donald E. Efficient representation of perm groups. (English) Zbl 0803.20005 Combinatorica 11, No. 1, 33-43 (1991). Reviewer: K.G.Brokate (Leonberg) MSC: 20B40 68Q25 20-04 20C40 20F05 PDFBibTeX XMLCite \textit{D. E. Knuth}, Combinatorica 11, No. 1, 33--43 (1991; Zbl 0803.20005) Full Text: DOI arXiv
Lagarias, J. C.; Lenstra, H. W. jun.; Schnorr, C. P. Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice. (English) Zbl 0723.11029 Combinatorica 10, No. 4, 333-348 (1990). Reviewer: M.Pohst (Düsseldorf) MSC: 11H55 11H06 68Q25 11H50 PDFBibTeX XMLCite \textit{J. C. Lagarias} et al., Combinatorica 10, No. 4, 333--348 (1990; Zbl 0723.11029) Full Text: DOI
Bodlaender, Hans L.; Gritzmann, P.; Klee, V.; van Leeuwen, J. Computational complexity of norm-maximization. (English) Zbl 0722.90080 Combinatorica 10, No. 2, 203-225 (1990). Reviewer: N.Stanoulov (Sofia) MSC: 90C60 03D15 PDFBibTeX XMLCite \textit{H. L. Bodlaender} et al., Combinatorica 10, No. 2, 203--225 (1990; Zbl 0722.90080) Full Text: DOI
Papadimitriou, C. H.; Yannakakis, M. On recognizing integer polyhedra. (English) Zbl 0718.68044 Combinatorica 10, No. 1, 107-109 (1990). Reviewer: Du Ding-Zhu (Minneapolis) MSC: 68Q25 68U05 PDFBibTeX XMLCite \textit{C. H. Papadimitriou} and \textit{M. Yannakakis}, Combinatorica 10, No. 1, 107--109 (1990; Zbl 0718.68044) Full Text: DOI
Aronov, B.; Sharir, M. Triangles in space or building (and analyzing) castles in the air. (English) Zbl 0717.68099 Combinatorica 10, No. 2, 137-173 (1990). MSC: 68U05 68Q25 PDFBibTeX XMLCite \textit{B. Aronov} and \textit{M. Sharir}, Combinatorica 10, No. 2, 137--173 (1990; Zbl 0717.68099) Full Text: DOI
Aiello, W.; Goldwasser, S.; Håstad, Johan On the power of interaction. (English) Zbl 0715.68028 Combinatorica 10, No. 1, 3-25 (1990). MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{W. Aiello} et al., Combinatorica 10, No. 1, 3--25 (1990; Zbl 0715.68028) Full Text: DOI
Tardos, G. Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? (English) Zbl 0698.68051 Combinatorica 9, No. 4, 385-392 (1989). MSC: 68Q25 68Q05 03D15 PDFBibTeX XMLCite \textit{G. Tardos}, Combinatorica 9, No. 4, 385--392 (1989; Zbl 0698.68051) Full Text: DOI
Peleg, D.; Upfal, E. Constructing disjoint paths on expander graphs. (English) Zbl 0686.68056 Combinatorica 9, No. 3, 289-313 (1989). MSC: 68R10 68Q25 03D15 68Q05 PDFBibTeX XMLCite \textit{D. Peleg} and \textit{E. Upfal}, Combinatorica 9, No. 3, 289--313 (1989; Zbl 0686.68056) Full Text: DOI
Babai, L. On Lovász’ lattice reduction and the nearest lattice point problem. (English) Zbl 0593.68030 Combinatorica 6, 1-13 (1986). MSC: 68Q25 90C10 11J99 11H06 11H55 PDFBibTeX XMLCite \textit{L. Babai}, Combinatorica 6, 1--13 (1986; Zbl 0593.68030) Full Text: DOI
Karmarkar, N. A new polynomial-time algorithm for linear programming. (English) Zbl 0557.90065 Combinatorica 4, 373-395 (1984). Reviewer: K.G.Murty MSC: 90C05 68Q25 PDFBibTeX XMLCite \textit{N. Karmarkar}, Combinatorica 4, 373--395 (1984; Zbl 0557.90065) Full Text: DOI