Search results for "conjecture"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
74	Ken-ichi Kawarabayashi, Bruce A. Reed	Hadwiger's conjecture is decidable.	STOC	2009	DBLP DOI BibTeX RDF	Hadwiger's conjecture, the four color theorem
64	Jeff Kahn 0001, Michael E. Saks, Cliff Smyth 0001	A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture.	CCC	2000	DBLP DOI BibTeX RDF	Reimer's inequality, van den Berg-Kesten conjecture, Rudich's conjecture
60	Angelo Monti, Paolo Penna, Riccardo Silvestri	An Equivalent Version of the Caccetta-Häggkvist Conjecture in an Online Load Balancing Problem.	WG	2007	DBLP DOI BibTeX RDF	Caccetta-Häggkvist conjecture, online load balancing, competitive analysis
57	Marcin Peczarski	The Gold Partition Conjecture for 6-Thin Posets.	Order	2008	DBLP DOI BibTeX RDF	1/3-2/3 conjecture, Gold partition conjecture, Poset, Linear extension
57	Miklós Ajtai	A conjecture about polynomial time computable lattice-lattice functions.	STOC	2004	DBLP DOI BibTeX RDF	axiom of choice, algorithm, lattice
54	Naoki Katoh, Shin-ichi Tanigawa	A proof of the molecular conjecture.	SCG	2009	DBLP DOI BibTeX RDF	bar-and-joint frameworks, body-and-hinge frameworks, edge-disjoint spanning trees, the molecular conjecture, rigidity
54	Bill Jackson, Tibor Jordán	Pin-Collinear Body-and-Pin Frameworks and the Molecular Conjecture.	Discret. Comput. Geom.	2008	DBLP DOI BibTeX RDF	Rigidity of frameworks, Body-and-hinge frameworks, Bar-and-joint frameworks, Molecular Conjecture
54	Marcin Peczarski	The Gold Partition Conjecture.	Order	2006	DBLP DOI BibTeX RDF	poset, linear extension, conjecture
54	Wen-tsun Wu	On Wintner's Conjecture About Central Configurations.	IWMM/GIAE	2004	DBLP DOI BibTeX RDF	Celestial Mechanics, Central Configurations, Wintner’s Conjecture, Extremal Zeroes, Finite Kernel Theorem, Extremal Values
53	Subhash Khot	On the power of unique 2-prover 1-round games.	STOC	2002	DBLP DOI BibTeX RDF
53	Subhash Khot	On the Power of Unique 2-Prover 1-Round Games.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
53	Ian Agol, Joel Hass, William P. Thurston	3-MANIFOLD KNOT GENUS is NP-complete.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
50	Tien-Yien Li, Xiaoshen Wang	Counterexamples to the Connectivity Conjecture of the Mixed Cells.	Discret. Comput. Geom.	1998	DBLP DOI BibTeX RDF
50	Ken-ichi Kawarabayashi, Bojan Mohar	Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs.	STOC	2006	DBLP DOI BibTeX RDF	Hadwiger conjecture, odd-minor, graph coloring, graph minor, list coloring
47	Gábor Czédli, Miklós Maróti, E. Tamás Schmidt	On the Scope of Averaging for Frankl's Conjecture.	Order	2009	DBLP DOI BibTeX RDF	Union-closed sets, Frankl’s conjecture, Lattice
47	Blagovest Sendov	Geometry of Polynomials and Numerical Analysis.	Numerical Methods and Application	2002	DBLP DOI BibTeX RDF	Geometry of polynomials, Gauss-Lucas Theorem, zeros of polynomials, Smale's Conjecture, Sendov's Conjecture, Mathematics Subject Classification: 30C10, critical points
46	Qi Cheng 0001	Straight-line programs and torsion points on elliptic curves.	Comput. Complex.	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000). 14H52, 68Q17
46	Albert Atserias, Phokion G. Kolaitis	First-Order Logic vs. Fixed-Point Logic in Finite Set Theory.	LICS	1999	DBLP DOI BibTeX RDF
44	Antoine Deza, Tamás Terlaky, Yuriy Zinchenko	A Continuous d -Step Conjecture for Polytopes.	Discret. Comput. Geom.	2009	DBLP DOI BibTeX RDF	Hirsch conjecture, d-Step conjecture, Diameter, Curvature, Polytopes, Central path
44	Yih-En Andrew Ban, Sergey Bereg, Nabil H. Mustafa	A Conjecture on Wiener Indices in Combinatorial Chemistry.	Algorithmica	2004	DBLP DOI BibTeX RDF	Wiener index, Combinatorial chemistry, Graph theory, Matrix searching
44	Qi Cheng 0001	Some Remarks on the L-Conjecture.	ISAAC	2002	DBLP DOI BibTeX RDF
44	Jean-Marc Deshouillers, Herman te Riele, Yannick Saouter	New Experimental Results Concerning the Goldbach Conjecture.	ANTS	1998	DBLP DOI BibTeX RDF
43	Anup Rao 0001	Parallel repetition in projection games and a concentration bound.	STOC	2008	DBLP DOI BibTeX RDF	chsh game, parallel repetition, unique games conjecture
40	Feliu Sagols, Raúl Marín	The Inscribed Square Conjecture in the Digital Plane.	IWCIA	2009	DBLP DOI BibTeX RDF	Inscribed Square Conjecture, Jordan Curve Theorem, simple closed digital curves, digital topology
40	Antoine Deza, Gabriel Indik	A counterexample to the dominating set conjecture.	Optim. Lett.	2007	DBLP DOI BibTeX RDF	Dominating set conjecture, Metric polyhedra, Cut polyhedra
40	Ken-ichi Kawarabayashi, Bjarne Toft	Any 7-Chromatic Graphs Has K7 Or K4, 4 As A Minor.	Comb.	2005	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C15, 05C83
40	Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell	Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?	FOCS	2004	DBLP DOI BibTeX RDF
37	Naoki Katoh	A Proof of the Molecular Conjecture.	ISAAC	2009	DBLP DOI BibTeX RDF
37	Rainer Feldmann, Marios Mavronicolas, Andreas Pieris	Facets of the Fully Mixed Nash Equilibrium Conjecture.	SAGT	2008	DBLP DOI BibTeX RDF
37	Navin Goyal, Neil Olver, F. Bruce Shepherd	The vpn conjecture is true.	STOC	2008	DBLP DOI BibTeX RDF	network design, robust optimization, oblivious routing
37	Shachar Lovett, Roy Meshulam, Alex Samorodnitsky	Inverse conjecture for the gowers norm is false.	STOC	2008	DBLP DOI BibTeX RDF	gowers norm, multivariate polynomials, low degree tests
37	J. C. Lagarias 0001	Bounds for Local Density of Sphere Packings and the Kepler Conjecture.	Discret. Comput. Geom.	2002	DBLP DOI BibTeX RDF
37	Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi	Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.	Algorithmica	2009	DBLP DOI BibTeX RDF	Bidimensionality, Wagner’s conjecture, Graph algorithms, Treewidth, Graph minors, Grid graphs
37	Raman Sanyal, Axel Werner, Günter M. Ziegler	On Kalai's Conjectures Concerning Centrally Symmetric Polytopes.	Discret. Comput. Geom.	2009	DBLP DOI BibTeX RDF	Centrally symmetric convex polytopes, f-vector inequalities, Flag vectors, Kalai’s 3 d -conjecture, Equivariant rigidity, Hanner polytopes, Hansen polytopes, Central hypersimplices
37	Irit Dinur, Elchanan Mossel, Oded Regev 0001	Conditional hardness for approximate coloring.	STOC	2006	DBLP DOI BibTeX RDF	graph coloring, hardness of approximation, unique games conjecture
34	Tero Harju, Dirk Nowotka	Periodicity and unbordered words: A proof of the extended duval conjecture.	J. ACM	2007	DBLP DOI BibTeX RDF	Duval's conjecture, unbordered words, periodicity, Combinatorics on words
34	Jacob Katzenelson, Shlomit S. Pinter, Eugen Schenfeld	Type Matching, Type-Graphs, and the Schanuel Conjecture.	ACM Trans. Program. Lang. Syst.	1992	DBLP DOI BibTeX RDF	Schanuel conjecture, graph hashing, mapping graphs to numbers, type matching, compilers, types, type-graphs
33	T. Birsan, Dan Tiba	One Hundred Years Since the Introduction of the Set Distance by Dimitrie Pompeiu.	System Modelling and Optimization	2005	DBLP DOI BibTeX RDF	Hausdorff-Pompeiu distance, Pompeiu functions, Pompeiu conjecture, Schiffer conjecture, Hausdorff distance
33	Tung-Ho Lin, Fan-Tien Cheng, Aeo-Juo Ye, Wei-Ming Wu, Min-Hsiung Hung	A novel key-variable sifting algorithm for virtual metrology.	ICRA	2008	DBLP DOI BibTeX RDF
33	Micah Adler, Nicholas J. A. Harvey, Kamal Jain, Robert D. Kleinberg, April Rasala Lehman	On the capacity of information networks.	SODA	2006	DBLP DOI BibTeX RDF
33	Stefan Andrei, Manfred Kudlek, Radu Stefan Niculescu	Some results on the Collatz problem.	Acta Informatica	2000	DBLP DOI BibTeX RDF
33	Alexei P. Stolboushkin, Michael A. Taitslin	Normalizable linear orders and generic computations in finite models.	Arch. Math. Log.	1999	DBLP DOI BibTeX RDF
33	Thomas C. Hales	Sphere Packings, I.	Discret. Comput. Geom.	1997	DBLP DOI BibTeX RDF
30	Asaf Shapira	Green's conjecture and testing linear-invariant properties.	STOC	2009	DBLP DOI BibTeX RDF	hypergraphs removal lemma, boolean functions, property testing
30	Julia Böttcher, Mathias Schacht, Anusch Taraz	On the bandwidth conjecture for 3-colourable graphs.	SODA	2007	DBLP BibTeX RDF
30	Tadej Kotnik, Herman te Riele	The Mertens Conjecture Revisited.	ANTS	2006	DBLP DOI BibTeX RDF
30	Subhash Khot, Nisheeth K. Vishnoi	The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l1.	FOCS	2005	DBLP DOI BibTeX RDF
30	Christos H. Papadimitriou, David Ratajczak	On a Conjecture Related to Geometric Routing.	ALGOSENSORS	2004	DBLP DOI BibTeX RDF
30	Sinisa T. Vrecica	Tverberg's Conjecture.	Discret. Comput. Geom.	2003	DBLP DOI BibTeX RDF
30	Yih-En Andrew Ban, Sergei Bespamyatnikh, Nabil H. Mustafa	On a Conjecture on Wiener Indices in Combinatorial Chemistry.	COCOON	2003	DBLP DOI BibTeX RDF
30	Daniel Richardson	The Uniformity Conjecture.	CCA	2000	DBLP DOI BibTeX RDF
30	Fred B. Holt, Victor Klee	Counterexamples to the Strong d -Step Conjecture for d ge 5.	Discret. Comput. Geom.	1998	DBLP DOI BibTeX RDF
30	J. C. Lagarias 0001, Nagabhushana Prabhu, James A. Reeds	The d-Step Conjecture and Gaussian Elimination.	Discret. Comput. Geom.	1997	DBLP DOI BibTeX RDF
30	Harry Buhrman, Montserrat Hermo	On the Sparse Set Conjecture for Sets with Low Denisty.	STACS	1995	DBLP DOI BibTeX RDF
30	Jamil Baddoura	A Conjecture on Integration in Finite Terms with Elementary Functions and Polylogarithms.	ISSAC	1994	DBLP DOI BibTeX RDF
30	Nader H. Bshouty	On the Direct Sum Conjecture in the Straight Line Model.	ESA	1993	DBLP DOI BibTeX RDF
30	Karel Culík II	On Test Sets and the Ehrenfeucht Conjecture.	ICALP	1982	DBLP DOI BibTeX RDF
30	Scott Aaronson	BQP and the polynomial hierarchy.	STOC	2010	DBLP DOI BibTeX RDF	linial-nisan conjecture, quantum complexity classes, fourier analysis, constant-depth circuits
30	Avraham Trakhtman	Some Aspects of Synchronization of DFA.	J. Comput. Sci. Technol.	2008	DBLP DOI BibTeX RDF	deterministic finite automata (DFA), aperiodic semigroup, ?erný conjecture, synchronization
30	Prasad Raghavendra	Optimal algorithms and inapproximability results for every CSP?	STOC	2008	DBLP DOI BibTeX RDF	dictatorship tests, rounding schemes, semidefinite programming, constraint satisfaction problem, unique games conjecture
30	Daniel Richardson	Zero Tests for Constants in Simple Scientific Computation.	Math. Comput. Sci.	2007	DBLP DOI BibTeX RDF	Exp-Log constants, zero test, Schanuel conjecture
30	Takashi Matsuhisa	Communication Leading to Nash Equilibrium Through Robust Messages - S5 -Knowledge Model Case -.	COCOA	2007	DBLP DOI BibTeX RDF	Robust message, Non-corporative game, S5-knowledge model, Communication, Protocol, Nash equilibrium, Conjecture
30	S. M. Nazrul Alam, Zygmunt J. Haas	Coverage and connectivity in three-dimensional networks.	MobiCom	2006	DBLP DOI BibTeX RDF	3D networks, Kelvin's conjecture, hexagonal prism, rhombic dodecahedron, three-dimensional networks, truncated octahedron, wireless networks, connectivity, coverage, polyhedron, underwater networks
30	Takashi Matsuhisa, Paul Strokan	Bayesian Communication Leading to a Nash Equilibrium in Belief.	WINE	2005	DBLP DOI BibTeX RDF	p-Belief system, Bayesian communication, Non-corporative game, Protocol, Nash equilibrium, Conjecture
30	Takashi Matsuhisa	Communication Leading to Nash Equilibrium without Acyclic Condition (S4-Knowledge Model Case).	International Conference on Computational Science	2004	DBLP DOI BibTeX RDF	Modal logic S4, Mutual learning, Non-corporative game, Communication, Protocol, Nash equilibrium, Knowledge, Information, Conjecture
30	Takashi Matsuhisa	p-Belief Communication Leading to a Nash Equilibrium.	CIS	2004	DBLP DOI BibTeX RDF	p-Belief system, Non-corporative game, Communication, Protocol, Nash equilibrium, Conjecture
30	Josep M. Brunat, Antonio Montes	The characteristic ideal of a finite, connected, regular graph.	ISSAC	2004	DBLP DOI BibTeX RDF	characteristic ideal, galois graph, polynomial digraph, polynomial graph, strongly polynomial graph, variety of a pairing, pairing, connected component, conjecture
30	Olivier Baudon, Guillaume Fertin, Ivan Havel	Routing Permutations in the Hypercube.	WG	1999	DBLP DOI BibTeX RDF	routing permutations, Szymanski's conjecture, 2-1 routing requests, Hypercubes
27	Rade T. Zivaljevic	Combinatorial Groupoids, Cubical Complexes, and the Lovász Conjecture.	Discret. Comput. Geom.	2009	DBLP DOI BibTeX RDF	Combinatorial groupoids, Lovász conjecture, Discrete differential geometry, Cubical complexes
27	Miguel Cárdenas-Montes, Antonio Gómez-Iglesias, Miguel A. Vega-Rodríguez, Enrique Morales-Ramos	Exploration of the Conjecture of Bateman Using Particle Swarm Optimisation and Grid Computing.	ISPDC	2009	DBLP DOI BibTeX RDF	Conjecture of Bateman, Recreational Mathematics, Particle Swarm Optimisation
27	Arnold Beckmann, Martin Goldstern, Norbert Preining	Continuous Fraïssé Conjecture.	Order	2008	DBLP DOI BibTeX RDF	Better quasi order, Gödel logic, Wellquasiorder, Fraisse conjecture, Continuous embeddings
27	Wolfram Koepf	Power series, Bieberbach conjecture and the de Branges and Weinstein functions.	ISSAC	2003	DBLP DOI BibTeX RDF	Askey-Gasper inequality, Bieberbach conjecture, FPS algorithm, Sturm sequences, Weinstein functions, algorithmic computation of formal power series, de Branges functions
27	Clifford D. Smyth	Reimer's inequality and tardos' conjecture.	STOC	2002	DBLP DOI BibTeX RDF	Reimer's inequality, certificate complexity, correlation inequalities, decision tree complexity, van den Berg-Kesten conjecture
27	Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer	The Isomorphism Conjecture Fails Relative to a Random Oracle.	J. ACM	1995	DBLP DOI BibTeX RDF	randomness, isomorphism, conjecture
27	Jin-yi Cai, D. Sivakumar	The Resolution of a Hartmanis Conjecture.	FOCS	1995	DBLP DOI BibTeX RDF	Hartmanis conjecture, sparse sets, logspace many-one reductions, sparse hard set, computational complexity
27	Anil Kamath, Rajeev Motwani 0001, Krishna V. Palem, Paul G. Spirakis	Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture	FOCS	1994	DBLP DOI BibTeX RDF	tail bounds, satisfiability threshold conjecture, random allocation, random 3-SAT formulas, randomized algorithms, upper bound, probabilistic analysis, structural property, occupancy
27	Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz	The Isomorphism Conjecture Holds Relative to an Oracle	FOCS	1992	DBLP DOI BibTeX RDF	symmetric perfect generic sets, isomorphism conjecture, NP completeness, oracle
27	Rajamani Sundar	Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem	FOCS	1989	DBLP DOI BibTeX RDF	turns, deque conjecture, scanning theorem, inverse Ackerman bound, binary tree, cascades, splay tree
27	Ken-ichi Kawarabayashi, Bojan Mohar	List-color-critical graphs on a fixed surface.	SODA	2009	DBLP DOI BibTeX RDF	critical graphs, surface, list-coloring
27	Friedrich Eisenbrand, Gianpaolo Oriolo, Gautier Stauffer, Paolo Ventura	The stable set polytope of quasi-line graphs.	Comb.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 90C57, 90C10
27	Thomas C. Hales	Sphere Packing, IV. Detailed Bounds.	Discret. Comput. Geom.	2006	DBLP DOI BibTeX RDF
27	Mario Szegedy	The DLT priority sampling is essentially optimal.	STOC	2006	DBLP DOI BibTeX RDF	integral formula, priority sampling, subset sum estimate, telescopic sums, network measurement, Internet traffic
27	Moses Charikar, Konstantin Makarychev, Yury Makarychev	Near-optimal algorithms for unique games.	STOC	2006	DBLP DOI BibTeX RDF	unique games, approximation algorithms, semidefinite programming, constraint satisfaction problems
27	Friedrich Eisenbrand, Gianpaolo Oriolo, Gautier Stauffer, Paolo Ventura	Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs.	IPCO	2005	DBLP DOI BibTeX RDF
27	Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz	Noise stability of functions with low in.uences invariance and optimality.	FOCS	2005	DBLP DOI BibTeX RDF
27	Robert Krauthgamer, James R. Lee	The intrinsic dimensionality of graphs.	STOC	2003	DBLP DOI BibTeX RDF	growth restricted graphs, low-dimensional, embeddings, graph decomposition, lovasz local lemma, finite metric spaces
27	Khaled El Emam, Saïda Benlarbi, Nishith Goel, Walcélio L. Melo, Hakim Lounis, Shesh N. Rai	The Optimal Class Size for Object-Oriented Software.	IEEE Trans. Software Eng.	2002	DBLP DOI BibTeX RDF	quality prediction, optimal size, software quality, quality models, object-oriented metrics, software size
27	Ron Aharoni, Ron Holzman, Michael Krivelevich, Roy Meshulam	Fractional Planks.	Discret. Comput. Geom.	2002	DBLP DOI BibTeX RDF
27	Miklós Ajtai	Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties.	FOCS	2002	DBLP DOI BibTeX RDF
27	Károly J. Böröczky	About the Error Term for Best Approximation with Respect to the Hausdorff Related Metrics.	Discret. Comput. Geom.	2001	DBLP DOI BibTeX RDF
27	Thomas C. Hales	Sphere packings and generative.	SCG	2001	DBLP DOI BibTeX RDF
27	Howard Straubing	Circuit Complexity and the Expressive Power of Generalized First-Order Formulas.	ICALP	1992	DBLP DOI BibTeX RDF
24	Subhas Kumar Ghosh, Koushik Sinha	On Convex Greedy Embedding Conjecture for 3-Connected Planar Graphs.	FCT	2009	DBLP DOI BibTeX RDF
24	Gábor Kun, Mario Szegedy	A new line of attack on the dichotomy conjecture.	STOC	2009	DBLP DOI BibTeX RDF	term operations, computational complexity, constraint satisfaction problems, fourier analysis, NP, dichotomy
24	Xu Xiang	On the Minimum Distance Conjecture for Schubert Codes.	IEEE Trans. Inf. Theory	2008	DBLP DOI BibTeX RDF
24	Maxime Crochemore, Lucian Ilie, Liviu Tinta	Towards a Solution to the "Runs" Conjecture.	CPM	2008	DBLP DOI BibTeX RDF
24	Philippe Langevin, Gregor Leander, Gary McGuire	A Counterexample to a Conjecture of Niho.	IEEE Trans. Inf. Theory	2007	DBLP DOI BibTeX RDF
24	Roman N. Karasev	Tverberg's Transversal Conjecture and Analogues of Nonembeddability Theorems for Transversals.	Discret. Comput. Geom.	2007	DBLP DOI BibTeX RDF
24	Giancarlo Mauri, Mario J. Pérez-Jiménez, Claudio Zandron	On a Paun's Conjecture in Membrane Systems.	IWINAC (1)	2007	DBLP DOI BibTeX RDF
24	Károly Bezdek	From the Kneser-Poulsen conjecture to ball-polyhedra via Voronoi diagrams.	ISVD	2007	DBLP DOI BibTeX RDF