Search results for "NEXP"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
159	Levke Bentzien	Positive Turing and Truth-Table Completeness for NEXP Are Incomparable.	MFCS	1998	DBLP DOI BibTeX RDF
98	Valentine Kabanets, Russell Impagliazzo	Derandomizing polynomial identity tests means proving circuit lower bounds.	STOC	2003	DBLP DOI BibTeX RDF	BPP, NEXP, circuit lower bounds, derandomization, polynomial identity testing
94	Stephen A. Fenner, Lance Fortnow	Beyond P^(NP) - NEXP.	STACS	1995	DBLP DOI BibTeX RDF
65	Harry Buhrman, Lance Fortnow, Aduri Pavan	Some Results on Derandomization.	STACS	2003	DBLP DOI BibTeX RDF
61	Dror Lapidot, Adi Shamir	Fully Parallelized Multi Prover Protocols for NEXP-Time (Extended Abstract)	FOCS	1991	DBLP DOI BibTeX RDF	one-round perfect zero-knowledge protocol, fully parallelized multi prover protocols, NEXP-time, language, parallel executions
49	Valentine Kabanets, Russell Impagliazzo	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.	Comput. Complex.	2004	DBLP DOI BibTeX RDF	68Q17, 68Q15, Subject classification. 68Q10
49	Hirotada Kobayashi, Keiji Matsumoto	Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement.	ISAAC	2002	DBLP DOI BibTeX RDF
49	Russell Impagliazzo, Valentine Kabanets, Avi Wigderson	In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial Time.	CCC	2001	DBLP DOI BibTeX RDF
33	Zeev Dvir, Amir Shpilka, Amir Yehudayoff	Hardness-randomness tradeoffs for bounded depth arithmetic circuits.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, hardness-randomness tradeoffs, identity testing, lower bounds, arithmetic circuits
33	Scott Aaronson, Avi Wigderson	Algebrization: a new barrier in complexity theory.	STOC	2008	DBLP DOI BibTeX RDF	communication complexity, oracles, arithmetization, interactive proofs, query complexity, low-degree polynomials
33	Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun 0001, Andrew Chi-Chih Yao	Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems.	CCC	2008	DBLP DOI BibTeX RDF	multi-prover interactive proof systems, quantum nonlocality, Tsirelson inequality, entanglement
33	Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy	Derandomization and Distinguishing Complexity.	CCC	2003	DBLP DOI BibTeX RDF
33	Tommi Syrjänen	Omega-Restricted Logic Programs.	LPNMR	2001	DBLP DOI BibTeX RDF
33	Kousha Etessami, Moshe Y. Vardi, Thomas Wilke	First-Order Logic with Two Variables and Unary Temporal Logic.	LICS	1997	DBLP DOI BibTeX RDF
33	Harry Buhrman, Leen Torenvliet	On the Cutting Edge of Relativization: The Resource Bounded Injury Method.	ICALP	1994	DBLP DOI BibTeX RDF
29	Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon C. Marshall, Ronak Ramachandran	PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements.	CoRR	2024	DBLP DOI BibTeX RDF
29	Fa-Hsun Chen, Shen-Chang Huang, Yu-Cheng Lu, Tony Tan	Reducing NEXP-complete problems to DQBF.	CoRR	2022	DBLP DOI BibTeX RDF
29	Fa-Hsun Chen, Shen-Chang Huang, Yu-Cheng Lu, Tony Tan	Reducing NEXP-complete problems to DQBF.	FMCAD	2022	DBLP DOI BibTeX RDF
29	Anant Dhayal	On Limiting & Limited Non-determinism in NEXP Lower Bounds.		2021	RDF
29	Xiaojun Meng, Pin Sym Foong, Simon T. Perrault, Shengdong Zhao	NexP: A Beginner Friendly Toolkit for Designing and Conducting Controlled Experiments.	INTERACT (3)	2017	DBLP DOI BibTeX RDF
29	Antonis Achilleos	NEXP-completeness and Universal Hardness Results for Justification Logic.	CoRR	2015	DBLP BibTeX RDF
29	Kazuyuki Amano, Atsushi Saito	A Nonuniform Circuit Class with Multilayer of Threshold Gates Having Super Quasi Polynomial Size Lower Bounds Against NEXP.	LATA	2015	DBLP DOI BibTeX RDF
29	Antonis Achilleos	NEXP-Completeness and Universal Hardness Results for Justification Logic.	CSR	2015	DBLP DOI BibTeX RDF
29	Dung T. Nguyen, Alan L. Selman	Non-autoreducible Sets for NEXP.	STACS	2014	DBLP DOI BibTeX RDF
29	Egor Ianovski, Luke Ong	EGuaranteeNash for Boolean Games Is NEXP-Hard.	KR	2014	DBLP BibTeX RDF
29	Bin Fu	Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
29	Dung T. Nguyen, Alan L. Selman	Non-autoreducible Sets for NEXP.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
29	Egor Ianovski, Luke Ong	EGuaranteeNash for Boolean Games is NEXP-Hard.	CoRR	2013	DBLP BibTeX RDF
29	Bin Fu	Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP.	CoRR	2013	DBLP BibTeX RDF
29	Ryan Williams 0001	Towards NEXP versus BPP?	CSR	2013	DBLP DOI BibTeX RDF
29	Shlomi Dolev, Nova Fandina, Dan Gutfreund	Succinct Permanent Is NEXP-Hard with Many Hard Instances.	CIAC	2013	DBLP DOI BibTeX RDF
29	Shlomi Dolev, Nova Fandina, Dan Gutfreund	Succinct Permanent is NEXP-hard with Many Hard Instances.	Electron. Colloquium Comput. Complex.	2012	DBLP BibTeX RDF
29	Tsuyoshi Ito, Thomas Vidick	A multi-prover interactive proof for NEXP sound against entangled provers.	Electron. Colloquium Comput. Complex.	2012	DBLP BibTeX RDF
29	Tsuyoshi Ito, Thomas Vidick	A multi-prover interactive proof for NEXP sound against entangled provers	CoRR	2012	DBLP BibTeX RDF
29	Tsuyoshi Ito, Thomas Vidick	A Multi-prover Interactive Proof for NEXP Sound against Entangled Provers.	FOCS	2012	DBLP DOI BibTeX RDF
29	Fengming Wang	NEXP does not have non-uniform quasi-polynomial-size ACC circuits of o(loglog n) depth.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
29	Fengming Wang	NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth.	TAMC	2011	DBLP DOI BibTeX RDF
29	Carsten Lutz	NEXP TIME-complete description logics with concrete domains.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	NExpTime-completeness, concrete domains, domino problem, Computational complexity, description logic, post correspondence problem
29	Piotr Faliszewski	Exponential time reductions and sparse languages in NEXP	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
29	Dror Lapidot, Adi Shamir	Fully Parallelized Multi-Prover Protocols for NEXP-Time.	J. Comput. Syst. Sci.	1997	DBLP DOI BibTeX RDF
16	Baris Eker, H. Levent Akin	Using evolution strategies to solve DEC-POMDP problems.	Soft Comput.	2010	DBLP DOI BibTeX RDF	DEC-POMDP, Multi-robot decision making, Evolution control, Evolution strategies
16	Harry Buhrman, Lance Fortnow, Rahul Santhanam	Unconditional Lower Bounds against Advice.	ICALP (1)	2009	DBLP DOI BibTeX RDF
16	Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova	An axiomatic approach to algebrization.	STOC	2009	DBLP DOI BibTeX RDF	algebrization, independence, relativization
16	Christopher Amato, Shlomo Zilberstein	Achieving goals in decentralized POMDPs.	AAMAS (1)	2009	DBLP BibTeX RDF
16	Thomas Eiter, Giovambattista Ianni, Thomas Krennwallner, Roman Schindlauer	Exploiting conjunctive queries in description logic programs.	Ann. Math. Artif. Intell.	2008	DBLP DOI BibTeX RDF	Mathematics Subject Classifications (2000) 68T27, 68T35, 68T30
16	David G. Mitchell, Eugenia Ternovska	Expressive power and abstraction in Essence.	Constraints An Int. J.	2008	DBLP DOI BibTeX RDF	Essence, Constraint modelling languages, Model expansion, Abstraction, Expressive power, Descriptive complexity
16	Michael Ben-Or, Avinatan Hassidim, Haran Pilpel	Quantum Multi Prover Interactive Proofs with Communicating Provers.	FOCS	2008	DBLP DOI BibTeX RDF
16	Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor	The Power of Unentanglement.	CCC	2008	DBLP DOI BibTeX RDF	QMA, 3SAT, PCP Theorem, quantum computing, additivity, entanglement
16	Yang Xiang 0004, Franklin Hanshar	Planning in Multiagent Expedition with Collaborative Design Networks.	Canadian AI	2007	DBLP DOI BibTeX RDF
16	Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen D. Travers, Matthias Waldherr	Equivalence Problems for Circuits over Sets of Natural Numbers.	CSR	2007	DBLP DOI BibTeX RDF
16	Julien Lafaye	On the Complexity of Obtaining Optimal Watermarking Schemes.	IWDW	2007	DBLP DOI BibTeX RDF
16	Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy N. Rothblum	Verifying and decoding in constant depth.	STOC	2007	DBLP DOI BibTeX RDF	error-correcting codes, interactive proofs, constant-depth circuits
16	Stefan Göller	On the Complexity of Reasoning About Dynamic Policies.	CSL	2007	DBLP DOI BibTeX RDF
16	Philipp Weis, Neil Immerman	Structure Theorem and Strict Alternation Hierarchy for FO2 on Words.	CSL	2007	DBLP DOI BibTeX RDF
16	Kiran Lakkaraju, Les Gasser	The Complexity of Finding an Optimal Policy for Language Convergence.	SAB	2006	DBLP DOI BibTeX RDF
16	Russell Impagliazzo	Can every randomized algorithm be derandomized?	STOC	2006	DBLP DOI BibTeX RDF	algebraic circuit complexity, probabilistic algorithms, derandomization, circuit complexity, complexity classes, pseudo-randomness
16	Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran	Some Results on Average-Case Hardness Within the Polynomial Hierarchy.	FSTTCS	2006	DBLP DOI BibTeX RDF
16	Matthijs T. J. Spaan, Geoffrey J. Gordon, Nikos Vlassis	Decentralized planning under uncertainty for teams of communicating agents.	AAMAS	2006	DBLP DOI BibTeX RDF	decentralized POMDPs, artificial intelligence, planning under uncertainty, cooperative multiagent systems
16	Jianhui Wu 0006, Edmund H. Durfee	Mixed-integer linear programming for transition-independent decentralized MDPs.	AAMAS	2006	DBLP DOI BibTeX RDF	transition-independent decentralized MDP, mixed integer linear programming, MDP, piecewise linear approximation
16	Jiaying Shen, Raphen Becker, Victor R. Lesser	Agent interaction in distributed POMDPs and its implications on complexity.	AAMAS	2006	DBLP DOI BibTeX RDF	distributed POMDP, interaction, complexity
16	Konstantinos Daskalakis, Christos H. Papadimitriou	The Complexity of Games on Highly Regular Graphs.	ESA	2005	DBLP DOI BibTeX RDF
16	Gus Gutoski	Upper Bounds for Quantum Interactive Proofs with Competing Provers.	CCC	2005	DBLP DOI BibTeX RDF
16	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Short PCPs Verifiable in Polylogarithmic Time.	CCC	2005	DBLP DOI BibTeX RDF
16	Aurélie Beynier, Abdel-Illah Mouaddib	A polynomial algorithm for decentralized Markov decision processes with temporal constraints.	AAMAS	2005	DBLP DOI BibTeX RDF	multi-agent systems, uncertainty, planning, Markov decision processes
16	Eric Allender, Harry Buhrman, Michal Koucký 0001	What Can be Efficiently Reduced to the K-Random Strings?	STACS	2004	DBLP DOI BibTeX RDF
16	Ranjit Nair, Milind Tambe	Coordinating Teams in Uncertain Environments: A Hybrid BDI-POMDP Approach.	PROMAS	2004	DBLP DOI BibTeX RDF
16	Ranjit Nair, Milind Tambe, Maayan Roth, Makoto Yokoo	Communication for Improving Policy Computation in Distributed POMDPs.	AAMAS	2004	DBLP DOI BibTeX RDF
16	Raphen Becker, Shlomo Zilberstein, Victor R. Lesser, Claudia V. Goldman	Transition-independent decentralized markov decision processes.	AAMAS	2003	DBLP DOI BibTeX RDF	decentralized MDP, decision-theoretic planning
16	Iadine Chades, Bruno Scherrer, François Charpillet	A heuristic approach for solving decentralized-POMDP: assessment on the pursuit problem.	SAC	2002	DBLP DOI BibTeX RDF	decision theoretic agents, multiagent systems
16	Ranjit Nair, Milind Tambe, Stacy Marsella	Team Formation for Reformation in Multiagent Domains Like RoboCupRescue.	RoboCup	2002	DBLP DOI BibTeX RDF
16	Marcus Schaefer 0001, Eric Sedgwick, Daniel Stefankovic	Recognizing string graphs in NP.	STOC	2002	DBLP DOI BibTeX RDF
16	Harry Buhrman, Lance Fortnow	Resource-Bounded Kolmogorov Complexity Revisited.	STACS	1997	DBLP DOI BibTeX RDF
16	Stephen A. Fenner, Lance Fortnow, Lide Li	Gap-Definability as a Closure Property.	STACS	1993	DBLP DOI BibTeX RDF
16	Harry Buhrman, Albrecht Hoene, Leen Torenvliet	Splittings, Robustness and Structure of Complete Sets.	STACS	1993	DBLP DOI BibTeX RDF
16	Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan	Algebraic Methods for Interactive Proof Systems.	J. ACM	1992	DBLP DOI BibTeX RDF	interactive proof systems
16	K. Ganesan 0001	One-way Functions and Isomorphism Conjecture.	FSTTCS	1992	DBLP DOI BibTeX RDF
16	Donald Beaver, Joan Feigenbaum, Victor Shoup	Hiding Instances in Zero-Knowledge Proof Systems (Extended Abstract).	CRYPTO	1990	DBLP DOI BibTeX RDF